# Random real trees

Jean-François Le Gall^{[1]}

- [1] D.M.A., Ecole normale supérieure, 45 rue d’Ulm, 75005 Paris (France).

Annales de la faculté des sciences de Toulouse Mathématiques (2006)

- Volume: 15, Issue: 1, page 35-62
- ISSN: 0240-2963

## Access Full Article

top## Abstract

top## How to cite

topLe Gall, Jean-François. "Random real trees." Annales de la faculté des sciences de Toulouse Mathématiques 15.1 (2006): 35-62. <http://eudml.org/doc/10035>.

@article{LeGall2006,

abstract = {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.},

affiliation = {D.M.A., Ecole normale supérieure, 45 rue d’Ulm, 75005 Paris (France).},

author = {Le Gall, Jean-François},

journal = {Annales de la faculté des sciences de Toulouse Mathématiques},

language = {eng},

number = {1},

pages = {35-62},

publisher = {Université Paul Sabatier, Toulouse},

title = {Random real trees},

url = {http://eudml.org/doc/10035},

volume = {15},

year = {2006},

}

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

PB - Université Paul Sabatier, Toulouse

VL - 15

IS - 1

SP - 35

EP - 62

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

LA - eng

UR - http://eudml.org/doc/10035

ER -

## References

top- D. Aldous, The continuum random tree I, Ann. Probab. 19 (1991), 1-28 Zbl0722.60013MR1085326
- D. Aldous, The continuum random tree. II. An overview, Stochastic analysis (Durham, 1990) 167 (1991), 23-70, Cambridge Univ. Press, Cambridge Zbl0791.60008MR1166406
- D. Aldous, The continuum random tree III, Ann. Probab. 21 (1993), 248-289 Zbl0791.60009MR1207226
- D. Aldous, Tree-based models for random distribution of mass, J. Stat. Phys. 73 (1993), 625-641 Zbl1102.60318MR1251658
- D. Aldous, Brownian excursion conditioned on its local time, Electr. Comm. Probab. 3 (1998), 79-90 Zbl0914.60049MR1650567
- D. Aldous, G. Miermont, J. Pitman, The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity, Probab. Th. Rel. Fields 129 (2004), 182-218 Zbl1056.60011MR2063375
- J. Bennies, G. Kersting, A random walk approach to Galton-Watson trees, J. Theoret. Probab. 113 (2000), 777-803 Zbl0977.60083MR1785529
- M. Bousquet-Mélou, Limit laws for embedded trees. Applications to the integrated super-Brownian excursion, (2005) Zbl1107.60302
- J. Bouttier, P. Di Francesco, E. Guitter, Geodesic distance in planar graphs, Nuclear Phys. B 663 (2003), 535-567 Zbl1022.05022MR1987861
- J. Bouttier, P. Di Francesco, E. Guitter, Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nuclear Phys. B 675 (2003), 631-660 Zbl1027.05021MR2018892
- J. Bouttier, P. Di Francesco, E. Guitter, Planar maps as labeled mobiles, Electronic J. Combinatorics 11 (2004) Zbl1060.05045MR2097335
- N.G. De Bruijn, D.E. Knuth, S.O. Rice, The average height of planted plane trees, Graph theory and computing (1972), 15-22, Academic Press, New York Zbl0247.05106MR505710
- P. Chassaing, G. Schaeffer, Random planar lattices and integrated superBrownian excursion, Probab. Th. Rel. Fields 128 (2004), 161-212 Zbl1041.60008MR2031225
- K.L. Chung, Excursions in Brownian motion, Ark. Mat. 14 (1976), 155-177 Zbl0356.60033MR467948
- D.A. Dawson, E.A. Perkins, Historical Processes, Memoirs Amer. Math. Soc. 454 (1991) Zbl0754.60062MR1079034
- J.F. Delmas, Computation of moments for the length of the one dimensional ISE support, Electron. J. Probab. 8 (2003) Zbl1064.60169MR2041818
- E. Derbez, G. Slade, The scaling limit of lattice trees in high dimensions, Comm. Math. Phys. 198 (1998), 69-104 Zbl0915.60076MR1620301
- A. Dress, V. Moulton, W. Terhalle, $T$-theory: An overview, Europ. J. Combinatorics 17 (1996), 161-175 Zbl0853.54027MR1379369
- M. Drmota, B. Gittenberger, On the profile of random trees, Random Structures Algorithms 10 (1997), 321-451 Zbl0882.60084MR1608230
- T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab. 31 (2003), 996-1027 Zbl1025.60017MR1964956
- T. Duquesne, J.-F. Le Gall, Random trees, Lévy processes and spatial branching processes, Astérisque 281 (2002) Zbl1037.60074MR1954248
- T. Duquesne, J.-F. Le Gall, Probabilistic and fractal aspects of Lévy trees, Probab. Th. Rel. Fields 131 (2005), 553-603 Zbl1070.60076MR2147221
- T. Duquesne, J.-F. Le Gall, The Hausdorff measure of stable trees, (2005) Zbl1128.60072
- B. Durhuus, Probabilistic aspects of infinite trees and surfaces, Acta Physica Polonica B 34 (2003), 4795-4811
- E.B. Dynkin, A probabilistic approach to one class of nonlinear differential equations, Probab. Th. Rel. Fields 89 (1991), 89-115 Zbl0722.60062MR1109476
- E.B. Dynkin, S.E. Kuznetsov, $\mathbb{N}$-measures for branching exit Markov systems and their applications to differential equations, Probab. Theory Related Fields 130 (2004), 135-150 Zbl1068.31002MR2092876
- S.N. Evans, J.W. Pitman, A. Winter, Rayleigh processes, real trees and root growth with re-grafting, (2003) Zbl1086.60050
- S.N. Evans, A. Winter, Subtree prune and re-graft: A reversible real tree valued Markov process, (2005)
- P. Flajolet, A.M Odlyzko, The average height of binary trees and other simple trees, J. Comput. Systs. Sci. 25 (1982), 171-213 Zbl0499.68027MR680517
- J. Geiger, L. Kauffmann, The shape of large Galton-Watson trees with possibly infinite variance, Random Structures Algorithms 25 (2004), 311-335 Zbl1071.60078MR2086163
- Geiger J., G. Kersting, The Galton-Watson tree conditioned on its height, Proceedings 7th Vilnius Conference 1998 (1999), 277-286, GrigelionisB.B. Zbl1021.60065
- M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, (1999), Birkhäuser, Boston Zbl0953.53002MR1699320
- B. Haas, G. Miermont, The genealogy of self-similar fragmentations with negative index as a continuum random tree, Electron. J. Probab. 9 (2004), 57-97 (electronic) Zbl1064.60076MR2041829
- T. Hara, G. Slade, 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. 41 (2000), 1244-1293 Zbl0977.82022MR1757958
- R. van der Hofstad, G. Slade, Convergence of critical oriented percolation to super-Brownian motion above $4+1$ dimensions, Ann. Inst. H. Poincaré Probab. Statist. 20 (2003), 413-485 Zbl1020.60099MR1978987
- K. Itô, H.P. McKean, Diffusion Processes and their Sample Paths, (1965), Academic Press Inc., Publishers, New York Zbl0285.60063MR199891
- D.P. Kennedy, The distribution of the maximum Brownian excursion, J. Appl. Probab. 13 (1976), 371-376 Zbl0338.60048MR402955
- H. Kesten, Branching random walk with a critical branching part, J. Theoret. Probability 8 (1995), 921-962 Zbl0857.60087MR1353560
- S. Janson, J.F. Marckert, Convergence of discrete snakes, J. Theoret. Probab. 18 (2005), 615-647 Zbl1084.60049MR2167644
- J. Lamperti, The limit of a sequence of branching processes, Z. Wahrsch. verw. Gebiete 7 (1967), 271-288 Zbl0154.42603MR217893
- M. Ledoux, M. Talagrand, Probability in Banach Spaces, (1991), Springer, Berlin Zbl0748.60004MR1102015
- J.F. Le Gall, Brownian excursions, trees and measure-valued branching processes, Ann. Probab. 19 (1991), 1399-1439 Zbl0753.60078MR1127710
- J.F. Le Gall, A class of path-valued Markov processes and its applications to superprocesses, Probab. Th. Rel. Fields 96 (1993), 25-46 Zbl0794.60076MR1207305
- J.F. Le Gall, The Brownian snake and solutions of $\Delta u={u}^{2}$ in a domain, Probab. Th. Rel. Fields 102 (1995), 393-432 Zbl0826.60062MR1339740
- J.F. Le Gall, Spatial Branching Processes, Random Snakes and Partial Differential Equations, Lectures in Mathematics ETH Zürich (1999), Birkhäuser, Boston Zbl0938.60003MR1714707
- J.F. Le Gall, An invariance principle for conditioned trees, (2005)
- J.F. Le Gall, Y. Le Jan, Branching processes in Lévy processes: The exploration process, Ann. Probab. 26 (1998), 213-252 Zbl0948.60071MR1617047
- J.F. Le Gall, Y. Le Jan, Branching processes in Lévy processes: Laplace functionals of snakes and superprocesses, Probab. 26 (1998), 1407-1432 Zbl0945.60090MR1675019
- J.F. Le Gall, E.A. Perkins, The Hausdorff measure of the support of two-dimensional super-Brownian motion, Ann. Probab. 23 (1995), 1719-1747 Zbl0856.60055MR1379165
- J.F. Le Gall, M. Weill, Conditioned Brownian trees, Ann. Institut H. Poincaré, to appear (2004) Zbl1107.60053
- J.F. Marckert, A. Mokkadem, The depth first processes of Galton-Watson processes converge to the same Brownian excursion, Ann. Probab. 31 (2003), 1655-1678 Zbl1049.05026MR1989446
- J.F. Marckert, A. Mokkadem, Limits of normalized quadrangulations. The Brownian map. Preprint, (2004) Zbl1117.60038
- G. Miermont, Self-similar fragmentations derived from the stable tree: Spliting at heights, Probab. Th. Rel. Fields 127 (2003), 423-454 Zbl1042.60043MR2018924
- J. Neveu, Arbres et processus de Galton-Watson, Ann. Inst. Henri Poincaré 22 (1986), 199-207 Zbl0601.60082MR850756
- F. Paulin, The Gromov topology on $\mathbb{R}$-trees, Topology Appl. 32 (1989), 197-221 Zbl0675.20033MR1007101
- E.A. Perkins, A space-time property of a class of measure-valued branching diffusions, Trans. Amer. Math. Soc. 305 (1988), 743-795 Zbl0641.60060MR924777
- J. Pitman, 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. 27 (1999), 261-283 Zbl0954.60060MR1681110
- J. Pitman, Combinatorial stochastic processes, (2002) Zbl1103.60004MR1897932
- D. Revuz, M. Yor, Continuous Martingales and Brownian Motion, (1991), Springer, Berlin-Heidelberg-New York Zbl0731.60002MR1083357
- W. Vervaat, A relation between Brownian bridge and Brownian excursion, Ann. Probab. 10 (1982), 234-239 MR515820

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.