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 : 2015-04-06
Accepté le : 2016-10-19
Publié le : 2016-11-02
DOI : https://doi.org/10.5802/jep.36
Classification : 60J80,  60G18,  60B10
Mots clés: Arbres aléatoires, processus autosimilaires, topologie de Gromov-Hausdorff-Prokhorov
@article{JEP_2016__3__365_0,
     author = {Olivier H\'enard and Pascal Maillard},
     title = {On trees invariant under edge contraction},
     journal = {Journal de l'\'Ecole polytechnique --- 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 = {jep.centre-mersenne.org/item/JEP_2016__3__365_0/}
}
Hénard, Olivier; Maillard, Pascal. 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/item/JEP_2016__3__365_0/

[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 3035742 | Zbl 1285.60004

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

[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 | Article | MR 3522292 | Zbl 1384.60016

[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 | Article | Numdam | MR 1641670 | Zbl 0917.60082

[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 753872 | Zbl 0562.54041

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

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

[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 | Article | MR 2221786 | Zbl 1086.60050

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

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

[FS09] Ph. Flajolet & R. Sedgewick - Analytic combinatorics, Cambridge University Press, Cambridge, 2009 | Article | Zbl 1165.05001

[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 | Article | MR 2520129 | Zbl 1215.05161

[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 | Article | MR 2886098 | Zbl 1265.06002

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

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

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

[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 770626 | Zbl 0567.60052

[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 0565.05037

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

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