Random real trees
Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 15 (2006) no. 1, p. 35-62

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.

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.

@article{AFST_2006_6_15_1_35_0,
     author = {Le Gall, Jean-Fran\c cois},
     title = {Random real trees},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 15},
     number = {1},
     year = {2006},
     pages = {35-62},
     doi = {10.5802/afst.1112},
     mrnumber = {2225746},
     zbl = {1129.60047},
     language = {en},
     url = {http://www.numdam.org/item/AFST_2006_6_15_1_35_0}
}
Le Gall, Jean-François. Random real trees. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 15 (2006) no. 1, pp. 35-62. doi : 10.5802/afst.1112. http://www.numdam.org/item/AFST_2006_6_15_1_35_0/

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

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

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

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

[5] Aldous, D. Brownian excursion conditioned on its local time, Electr. Comm. Probab., Tome 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, Tome 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., Tome 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, Tome 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, Tome 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, Tome 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, Tome 128 (2004), pp. 161-212 | MR 2031225 | Zbl 1041.60008

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

[15] Dawson, D.A.; Perkins, E.A. Historical Processes, Memoirs Amer. Math. Soc., Tome 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., Tome 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., Tome 198 (1998), pp. 69-104 | MR 1620301 | Zbl 0915.60076

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

[19] Drmota, M.; Gittenberger, B. On the profile of random trees, Random Structures Algorithms, Tome 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., Tome 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, Tome 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, Tome 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, Tome 34 (2003), pp. 4795-4811

[25] Dynkin, E.B. A probabilistic approach to one class of nonlinear differential equations, Probab. Th. Rel. Fields, Tome 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, Tome 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., Tome 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, Tome 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., Tome 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., Tome 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., Tome 20 (2003), pp. 413-485 | Numdam | MR 1978987 | Zbl 1020.60099

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

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

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

[39] Janson, S.; Marckert, J.F. Convergence of discrete snakes, J. Theoret. Probab., Tome 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, Tome 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., Tome 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, Tome 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, Tome 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., Tome 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., Tome 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., Tome 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., Tome 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, Tome 127 (2003), pp. 423-454 | MR 2018924 | Zbl 1042.60043

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

[55] Paulin, F. The Gromov topology on -trees, Topology Appl., Tome 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., Tome 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., Tome 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., Tome 10 (1982), pp. 234-239 | MR 515820