On trees invariant under edge contraction
[Au sujet des arbres invariants par contraction de leurs arêtes]
Hénard, Olivier1 ; Maillard, Pascal1
1 Laboratoire de Mathématiques d’Orsay, Université Paris-Sud, CNRS, Université Paris-Saclay 91405 Orsay, France
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
Hénard, Olivier 1 ; Maillard, Pascal 1

1 Laboratoire de Mathématiques d’Orsay, Université Paris-Sud, CNRS, Université Paris-Saclay 91405 Orsay, France 
@article{JEP_2016__3__365_0,
     author = {H\'enard, Olivier and Maillard, Pascal},
     title = {On trees invariant under edge contraction},
     journal = {Journal de l{\textquoteright}\'Ecole polytechnique - Math\'ematiques},
     pages = {365--400},
     publisher = {ole polytechnique},
     volume = {3},
     year = {2016},
     doi = {10.5802/jep.36},
     mrnumber = {3580038},
     zbl = {1364.60105},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/jep.36/}
}
TY  - JOUR
AU  - Hénard, Olivier
AU  - Maillard, Pascal
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://www.numdam.org/articles/10.5802/jep.36/
DO  - 10.5802/jep.36
LA  - en
ID  - JEP_2016__3__365_0
ER  - 
%0 Journal Article
%A Hénard, Olivier
%A Maillard, Pascal
%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://www.numdam.org/articles/10.5802/jep.36/
%R 10.5802/jep.36
%G en
%F 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://www.numdam.org/articles/10.5802/jep.36/

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

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

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

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

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

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

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

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

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

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

[FS09] Flajolet, Ph.; Sedgewick, R. Analytic combinatorics, Cambridge University Press, Cambridge, 2009 | DOI | Zbl

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :