On trees invariant under edge contraction

Olivier Hénard; Pascal Maillard

doi:10.5802/jep.36

On trees invariant under edge contraction
[Au sujet des arbres invariants par contraction de leurs arêtes]

Olivier Hénard ¹ ; Pascal Maillard ¹

¹ 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.

Résumé
Abstract

Nous étudions les arbres aléatoires dont la loi est invariante par la contraction indépendante de leurs arêtes avec probabilité $p \in (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 \in (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-05
Accepté le : 2016-10-18
Publié le : 2016-11-01

MR Zbl

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

Affiliations des auteurs :

Olivier Hénard ¹ ; Pascal Maillard ¹

¹ 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/

Bibliographie
Cité par

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