Random real trees
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 15 (2006) no. 1, pp. 35-62.

Nous discutons certains développements récents de la théorie des arbres réels aléatoires, dont le prototype est le CRT introduit par Aldous en 1991. Nous introduisons le formalisme d’arbre réel, qui fournit une présentation élégante de la théorie, et en particulier des relations entre les arbres de Galton-Watson discrets et les arbres continus aléatoires. Nous discutons ensuite la classe des arbres auto-similaires appelés arbres stables, qui généralisent le CRT. Nous présentons plusieurs résultats importants au sujet des arbres stables, notamment leur propriété de branchement, analogue continu d’une propriété bien connue pour les arbres de Galton-Watson, et le calcul de leurs dimensions fractales. Nous considérons ensuite les arbres spatiaux, qui combinent la structure généalogique d’un arbre réel avec des déplacements dans l’espace, et nous expliquons leurs liens avec les superprocessus. Dans la dernière partie, nous traitons un conditionnement particulier des arbres spatiaux, qui est étroitement lié à certains résultats asymptotiques pour les quadrangulations planes aléatoires.

We survey recent developments about random real trees, whose prototype is the Continuum Random Tree (CRT) introduced by Aldous in 1991. We briefly explain the formalism of real trees, which yields a neat presentation of the theory and in particular of the relations between discrete Galton-Watson trees and continuous random trees. We then discuss the particular class of self-similar random real trees called stable trees, which generalize the CRT. We review several important results concerning stable trees, including their branching property, which is analogous to the well-known property of Galton-Watson trees, and the calculation of their fractal dimension. We then consider spatial trees, which combine the genealogical structure of a real tree with spatial displacements, and we explain their connections with superprocesses. In the last section, we deal with a particular conditioning problem for spatial trees, which is closely related to asymptotics for random planar quadrangulations.

@article{AFST_2006_6_15_1_35_0,
     author = {Le Gall, Jean-Fran\c{c}ois},
     title = {Random real trees},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {35--62},
     publisher = {Universit\'e Paul Sabatier, Institut de math\'ematiques},
     address = {Toulouse},
     volume = {Ser. 6, 15},
     number = {1},
     year = {2006},
     doi = {10.5802/afst.1112},
     mrnumber = {2225746},
     zbl = {1129.60047},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/afst.1112/}
}
TY  - JOUR
AU  - Le Gall, Jean-François
TI  - Random real trees
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2006
DA  - 2006///
SP  - 35
EP  - 62
VL  - Ser. 6, 15
IS  - 1
PB  - Université Paul Sabatier, Institut de mathématiques
PP  - Toulouse
UR  - http://www.numdam.org/articles/10.5802/afst.1112/
UR  - https://www.ams.org/mathscinet-getitem?mr=2225746
UR  - https://zbmath.org/?q=an%3A1129.60047
UR  - https://doi.org/10.5802/afst.1112
DO  - 10.5802/afst.1112
LA  - en
ID  - AFST_2006_6_15_1_35_0
ER  - 
Le Gall, Jean-François. Random real trees. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 15 (2006) no. 1, pp. 35-62. doi : 10.5802/afst.1112. http://www.numdam.org/articles/10.5802/afst.1112/

[1] Aldous, D. The continuum random tree I, Ann. Probab., Volume 19 (1991), pp. 1-28 | MR 1085326 | Zbl 0722.60013

[2] Aldous, D. The continuum random tree. II. An overview, Stochastic analysis (Durham, 1990) (London Math. Soc. Lecture Note Ser.), Volume 167, Cambridge Univ. Press, Cambridge, 1991, pp. 23-70 | MR 1166406 | Zbl 0791.60008

[3] Aldous, D. The continuum random tree III, Ann. Probab., Volume 21 (1993), pp. 248-289 | MR 1207226 | Zbl 0791.60009

[4] Aldous, D. Tree-based models for random distribution of mass, J. Stat. Phys., Volume 73 (1993), pp. 625-641 | MR 1251658 | Zbl 1102.60318

[5] Aldous, D. Brownian excursion conditioned on its local time, Electr. Comm. Probab., Volume 3 (1998), pp. 79-90 | MR 1650567 | Zbl 0914.60049

[6] Aldous, D.; Miermont, G.; Pitman, J. The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity, Probab. Th. Rel. Fields, Volume 129 (2004), pp. 182-218 | MR 2063375 | Zbl 1056.60011

[7] Bennies, J.; Kersting, G. A random walk approach to Galton-Watson trees, J. Theoret. Probab., Volume 113 (2000), pp. 777-803 | MR 1785529 | Zbl 0977.60083

[8] Bousquet-Mélou, M. Limit laws for embedded trees. Applications to the integrated super-Brownian excursion (2005) (Preprint, arXiv:math.CO/0501266)

[9] Bouttier, J.; Di Francesco, P.; Guitter, E. Geodesic distance in planar graphs, Nuclear Phys. B, Volume 663 (2003), pp. 535-567 | MR 1987861 | Zbl 1022.05022

[10] Bouttier, J.; Di Francesco, P.; Guitter, E. Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nuclear Phys. B, Volume 675 (2003), pp. 631-660 | MR 2018892 | Zbl 1027.05021

[11] Bouttier, J.; Di Francesco, P.; Guitter, E. Planar maps as labeled mobiles, Electronic J. Combinatorics, Volume 11 (2004), pp. Research Paper 69, 27 pp. (electronic) | MR 2097335 | Zbl 1060.05045

[12] De Bruijn, N.G.; Knuth, D.E.; Rice, S.O. The average height of planted plane trees, Graph theory and computing, Academic Press, New York, 1972, pp. 15-22 | MR 505710 | Zbl 0247.05106

[13] Chassaing, P.; Schaeffer, G. Random planar lattices and integrated superBrownian excursion, Probab. Th. Rel. Fields, Volume 128 (2004), pp. 161-212 | MR 2031225 | Zbl 1041.60008

[14] Chung, K.L. Excursions in Brownian motion, Ark. Mat., Volume 14 (1976), pp. 155-177 | MR 467948 | Zbl 0356.60033

[15] Dawson, D.A.; Perkins, E.A. Historical Processes, Memoirs Amer. Math. Soc., Volume 454 (1991), pp. iv+179 | MR 1079034 | Zbl 0754.60062

[16] Delmas, J.F. Computation of moments for the length of the one dimensional ISE support, Electron. J. Probab., Volume 8 (2003) no. 17, pp. 15 pp. (electronic) | MR 2041818 | Zbl 1064.60169

[17] Derbez, E.; Slade, G. The scaling limit of lattice trees in high dimensions, Comm. Math. Phys., Volume 198 (1998), pp. 69-104 | MR 1620301 | Zbl 0915.60076

[18] Dress, A.; Moulton, V.; Terhalle, W. T-theory: An overview, Europ. J. Combinatorics, Volume 17 (1996), pp. 161-175 | MR 1379369 | Zbl 0853.54027

[19] Drmota, M.; Gittenberger, B. On the profile of random trees, Random Structures Algorithms, Volume 10 (1997), pp. 321-451 | MR 1608230 | Zbl 0882.60084

[20] Duquesne, T. A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab., Volume 31 (2003), pp. 996-1027 | MR 1964956 | Zbl 1025.60017

[21] Duquesne, T.; Le Gall, J.-F. Random trees, Lévy processes and spatial branching processes, Astérisque, Volume 281 (2002), pp. vi+147 | MR 1954248 | Zbl 1037.60074

[22] Duquesne, T.; Le Gall, J.-F. Probabilistic and fractal aspects of Lévy trees, Probab. Th. Rel. Fields, Volume 131 (2005), pp. 553-603 | MR 2147221 | Zbl 1070.60076

[23] Duquesne, T.; Le Gall, J.-F. The Hausdorff measure of stable trees (2005) (In preparation)

[24] Durhuus, B. Probabilistic aspects of infinite trees and surfaces, Acta Physica Polonica B, Volume 34 (2003), pp. 4795-4811

[25] Dynkin, E.B. A probabilistic approach to one class of nonlinear differential equations, Probab. Th. Rel. Fields, Volume 89 (1991), pp. 89-115 | MR 1109476 | Zbl 0722.60062

[26] Dynkin, E.B.; Kuznetsov, S.E. -measures for branching exit Markov systems and their applications to differential equations, Probab. Theory Related Fields, Volume 130 (2004) no. 1, pp. 135-150 | MR 2092876 | Zbl 1068.31002

[27] Evans, S.N.; Pitman, J.W.; Winter, A. Rayleigh processes, real trees and root growth with re-grafting (2003) (48 Pages. Minor revision of version of Feb 2004. To appear in Probab. Th. and Rel. Fields) | Zbl 1086.60050

[28] Evans, S.N.; Winter, A. Subtree prune and re-graft: A reversible real tree valued Markov process (2005) (Preprint, arXiv:math.PR/05022266)

[29] Flajolet, P.; Odlyzko, A.M The average height of binary trees and other simple trees, J. Comput. Systs. Sci., Volume 25 (1982) no. 2, pp. 171-213 | MR 680517 | Zbl 0499.68027

[30] Geiger, J.; Kauffmann, L. The shape of large Galton-Watson trees with possibly infinite variance, Random Structures Algorithms, Volume 25 (2004), pp. 311-335 | MR 2086163 | Zbl 1071.60078

[31] J., Geiger; Kersting, G.; Grigelionis, B. The Galton-Watson tree conditioned on its height, Proceedings 7th Vilnius Conference 1998 (1999), pp. 277-286 (VSP) | Zbl 1021.60065

[32] Gromov, M. Metric Structures for Riemannian and Non-Riemannian Spaces, Birkhäuser, Boston, 1999 | MR 1699320 | Zbl 0953.53002

[33] Haas, B.; Miermont, G. The genealogy of self-similar fragmentations with negative index as a continuum random tree, Electron. J. Probab., Volume 9 (2004) no. 4, p. 57-97 (electronic) | MR 2041829 | Zbl 1064.60076

[34] Hara, T.; Slade, G. The scaling limit of the incipient infinite cluster in high-dimensional percolation. II. Integrated super-Brownian excursion. Probabilistic techniques in equilibrium and nonequilibrium statistical physics, J. Math. Phys., Volume 41 (2000), pp. 1244-1293 | MR 1757958 | Zbl 0977.82022

[35] van der Hofstad, R.; Slade, G. Convergence of critical oriented percolation to super-Brownian motion above 4+1 dimensions, Ann. Inst. H. Poincaré Probab. Statist., Volume 20 (2003), pp. 413-485 | Numdam | MR 1978987 | Zbl 1020.60099

[36] Itô, K.; McKean, H.P. Diffusion Processes and their Sample Paths, Die Grundlehren der Mathematischen Wissenschaften, Band 125, Academic Press Inc., Publishers, New York, 1965 | MR 199891 | Zbl 0285.60063

[37] Kennedy, D.P. The distribution of the maximum Brownian excursion, J. Appl. Probab., Volume 13 (1976), pp. 371-376 | MR 402955 | Zbl 0338.60048

[38] Kesten, H. Branching random walk with a critical branching part, J. Theoret. Probability, Volume 8 (1995), pp. 921-962 | MR 1353560 | Zbl 0857.60087

[39] Janson, S.; Marckert, J.F. Convergence of discrete snakes, J. Theoret. Probab., Volume 18 (2005) no. 3, pp. 615-647 | MR 2167644 | Zbl 02238755

[40] Lamperti, J. The limit of a sequence of branching processes, Z. Wahrsch. verw. Gebiete, Volume 7 (1967), pp. 271-288 | MR 217893 | Zbl 0154.42603

[41] Ledoux, M.; Talagrand, M. Probability in Banach Spaces, Springer, Berlin, 1991 | MR 1102015 | Zbl 0748.60004

[42] Le Gall, J.F. Brownian excursions, trees and measure-valued branching processes, Ann. Probab., Volume 19 (1991), pp. 1399-1439 | MR 1127710 | Zbl 0753.60078

[43] Le Gall, J.F. A class of path-valued Markov processes and its applications to superprocesses, Probab. Th. Rel. Fields, Volume 96 (1993), pp. 25-46 | MR 1207305 | Zbl 0794.60076

[44] Le Gall, J.F. The Brownian snake and solutions of Δu=u 2 in a domain, Probab. Th. Rel. Fields, Volume 102 (1995), pp. 393-432 | MR 1339740 | Zbl 0826.60062

[45] Le Gall, J.F. Spatial Branching Processes, Random Snakes and Partial Differential Equations, Lectures in Mathematics ETH Zürich, Birkhäuser, Boston, 1999 | MR 1714707 | Zbl 0938.60003

[46] Le Gall, J.F. An invariance principle for conditioned trees (2005) (Preprint)

[47] Le Gall, J.F.; Le Jan, Y. Branching processes in Lévy processes: The exploration process, Ann. Probab., Volume 26 (1998), pp. 213-252 | MR 1617047 | Zbl 0948.60071

[48] Le Gall, J.F.; Le Jan, Y. Branching processes in Lévy processes: Laplace functionals of snakes and superprocesses, Probab., Volume 26 (1998), pp. 1407-1432 | MR 1675019 | Zbl 0945.60090

[49] Le Gall, J.F.; Perkins, E.A. The Hausdorff measure of the support of two-dimensional super-Brownian motion, Ann. Probab., Volume 23 (1995), pp. 1719-1747 | MR 1379165 | Zbl 0856.60055

[50] Le Gall, J.F.; Weill, M. Conditioned Brownian trees, Ann. Institut H. Poincaré, to appear, 2004 (arXiv:math.PR/0501066)

[51] Marckert, J.F.; Mokkadem, A. The depth first processes of Galton-Watson processes converge to the same Brownian excursion, Ann. Probab., Volume 31 (2003), pp. 1655-1678 | MR 1989446 | Zbl 1049.05026

[52] Marckert, J.F.; Mokkadem, A. Limits of normalized quadrangulations. The Brownian map. Preprint (2004) (arXiv:math.PR/0403398)

[53] Miermont, G. Self-similar fragmentations derived from the stable tree: Spliting at heights, Probab. Th. Rel. Fields, Volume 127 (2003), pp. 423-454 | MR 2018924 | Zbl 1042.60043

[54] Neveu, J. Arbres et processus de Galton-Watson, Ann. Inst. Henri Poincaré, Volume 22 (1986), pp. 199-207 | Numdam | MR 850756 | Zbl 0601.60082

[55] Paulin, F. The Gromov topology on -trees, Topology Appl., Volume 32 (1989), pp. 197-221 | MR 1007101 | Zbl 0675.20033

[56] Perkins, E.A. A space-time property of a class of measure-valued branching diffusions, Trans. Amer. Math. Soc., Volume 305 (1988), pp. 743-795 | MR 924777 | Zbl 0641.60060

[57] Pitman, J. The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest, Ann. Probab., Volume 27 (1999), pp. 261-283 | MR 1681110 | Zbl 0954.60060

[58] Pitman, J. Combinatorial stochastic processes (2002) (Lectures from the Saint-Flour probability summer school. To appear) | MR 1897932 | Zbl 1103.60004

[59] Revuz, D.; Yor, M. Continuous Martingales and Brownian Motion, Springer, Berlin-Heidelberg-New York, 1991 | MR 1083357 | Zbl 0731.60002

[60] Vervaat, W. A relation between Brownian bridge and Brownian excursion, Ann. Probab., Volume 10 (1982), pp. 234-239 | MR 515820

Cité par Sources :