On trees invariant under edge contraction
[Au sujet des arbres invariants par contraction de leurs arêtes]
Journal de l’École polytechnique — Mathématiques, Tome 3 (2016), pp. 365-400.

Nous étudions les arbres aléatoires dont la loi est invariante par la contraction indépendante de leurs arêtes avec probabilité p(0,1). Nous montrons que ces arbres peuvent être construits par échantillonnage poissonnien à partir d’une classe de -arbres aléatoires mesurés qui satisfont à une propriété d’invariance naturelle. Cette étude est liée aux ordres partiels échangeables, aux processus autosimilaires croissants à valeurs réelles et aux distributions quasi-stationnaires de processus de Galton-Watson.

We study random trees which are invariant in law under the operation of contracting each edge independently with probability p(0,1). We show that all such trees can be constructed through Poisson sampling from a certain class of random measured -trees satisfying a natural scale invariance property. This has connections to exchangeable partially ordered sets, real-valued self-similar increasing processes and quasi-stationary distributions of Galton–Watson processes.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/jep.36
Classification : 60J80, 60G18, 60B10
Keywords: Random tree, self-similar processes, Gromov-Hausdorff-Prokhorov topology
Mot clés : Arbres aléatoires, processus autosimilaires, topologie de Gromov-Hausdorff-Prokhorov
Olivier Hénard 1 ; Pascal Maillard 1

1 Laboratoire de Mathématiques d’Orsay, Université Paris-Sud, CNRS, Université Paris-Saclay 91405 Orsay, France
Licence : CC-BY-ND 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{JEP_2016__3__365_0,
     author = {Olivier H\'enard and Pascal Maillard},
     title = {On trees invariant under edge contraction},
     journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
     pages = {365--400},
     publisher = {ole polytechnique},
     volume = {3},
     year = {2016},
     doi = {10.5802/jep.36},
     zbl = {1364.60105},
     mrnumber = {3580038},
     language = {en},
     url = {https://jep.centre-mersenne.org/articles/10.5802/jep.36/}
}
TY  - JOUR
AU  - Olivier Hénard
AU  - Pascal Maillard
TI  - On trees invariant under edge contraction
JO  - Journal de l’École polytechnique — Mathématiques
PY  - 2016
SP  - 365
EP  - 400
VL  - 3
PB  - ole polytechnique
UR  - https://jep.centre-mersenne.org/articles/10.5802/jep.36/
DO  - 10.5802/jep.36
LA  - en
ID  - JEP_2016__3__365_0
ER  - 
%0 Journal Article
%A Olivier Hénard
%A Pascal Maillard
%T On trees invariant under edge contraction
%J Journal de l’École polytechnique — Mathématiques
%D 2016
%P 365-400
%V 3
%I ole polytechnique
%U https://jep.centre-mersenne.org/articles/10.5802/jep.36/
%R 10.5802/jep.36
%G en
%F JEP_2016__3__365_0
Olivier Hénard; Pascal Maillard. On trees invariant under edge contraction. Journal de l’École polytechnique — Mathématiques, Tome 3 (2016), pp. 365-400. doi : 10.5802/jep.36. https://jep.centre-mersenne.org/articles/10.5802/jep.36/

[ADH13] R. Abraham, J.-F. Delmas & P. Hoscheit - “A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces”, Electron. Comm. Probab. 18 (2013) no. 14, p. 1-21 | MR | Zbl

[Ald93] D. Aldous - “The continuum random tree III”, Ann. Probability 21 (1993) no. 1, p. 248-289 | MR | Zbl

[ALW16] S. Athreya, W. Löhr & A. Winter - “The gap between Gromov-vague and Gromov–Hausdorff-vague topology”, Stochastic Processes Appl. 126 (2016) no. 9, p. 2527-2553 | DOI | MR | Zbl

[AP98] D. Aldous & J. Pitman - “Tree-valued Markov chains derived from Galton-Watson processes”, Ann. Inst. H. Poincaré Probab. Statist. 34 (1998) no. 5, p. 637-686 | DOI | Numdam | MR | Zbl

[Dre84] A. W. M. Dress - “Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces”, Advances in Math. 53 (1984) no. 3, p. 321-402 | MR | Zbl

[Drm09] M. Drmota - Random trees, SpringerWienNewYork, Vienna, 2009 | DOI

[Dug66] J. Dugundji - Topology, Allyn and Bacon, Inc., Boston, 1966 | Zbl

[EPW06] S. N. Evans, J. Pitman & A. Winter - “Rayleigh processes, real trees, and root growth with re-grafting”, Probab. Theory Related Fields 134 (2006) no. 1, p. 81-126 | DOI | MR | Zbl

[Eva08] S. N. Evans - Probability and real trees, Lect. Notes in Math., vol. 1920, Springer, Berlin, 2008 | MR

[FHP11] N. Forman, C. Haulk & J. Pitman - “A representation of exchangeable hierarchies by sampling from real trees” (2011), arXiv:1101.5619

[FS09] P. Flajolet & R. Sedgewick - Analytic combinatorics, Cambridge University Press, Cambridge, 2009 | DOI | Zbl

[GPW09] A. Greven, P. Pfaffelhuber & A. Winter - “Convergence in distribution of random metric measure spaces (Λ-coalescent measure trees)”, Probab. Theory Related Fields 145 (2009) no. 1-2, p. 285-322 | DOI | MR | Zbl

[Gro07] M. Gromov - Metric structures for Riemannian and non-Riemannian spaces, Modern Birkhäuser Classics, Birkhäuser Boston Inc., Boston, MA, 2007

[HBS65] H. E. Hurst, R. P. Black & Y. M. Simaika - Long-term storage: an experimental study, Constable, London, 1965

[Jan11] S. Janson - “Poset limits and exchangeable random posets”, Combinatorica 31 (2011) no. 5, p. 529-563 | DOI | MR | Zbl

[LS06] L. Lovász & B. Szegedy - “Limits of dense graph sequences”, J. Combinatorial Theory Ser. B 96 (2006) no. 6, p. 933-957 | DOI | MR | Zbl

[Maiar] P. Maillard - “The λ-invariant measures of subcritical Bienaymé–Galton–Watson processes”, Bernoulli (to appear), arXiv:1508.00845 | MR | Zbl

[MVN68] B. B. Mandelbrot & J. W. Van Ness - “Fractional Brownian motions, fractional noises and applications”, SIAM Rev. 10 (1968) no. 4, p. 422-437 | DOI | MR | Zbl

[OV85] G. L. O’Brien & W. Vervaat - “Self-Similar Processes with Stationary Increments Generated by Point Processes”, Ann. Probability 13 (1985) no. 1, p. 28-52 | MR | Zbl

[Rém85] J.-L. Rémy - “Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire”, RAIRO Inform. Théor. 19 (1985) no. 2, p. 179-195 | Zbl

[Sta97] R. P. Stanley - Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997 | MR | Zbl

[Ver85] W. Vervaat - “Sample Path Properties of Self-Similar Processes with Stationary Increments”, Ann. Probability 13 (1985) no. 1, p. 1-27 | MR | Zbl

Cité par Sources :