Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T19:14:50.962Z Has data issue: false hasContentIssue false
  • English
  • Français

Tree limits and limits of random trees

Part of: Graph theory Markov processes Combinatorial probability

Published online by Cambridge University Press:  31 March 2021

Svante Janson
Svante Janson*
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, SE-751 06Uppsala, Sweden
*
Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We explore the tree limits recently defined by Elek and Tardos. In particular, we find tree limits for many classes of random trees. We give general theorems for three classes of conditional Galton–Watson trees and simply generated trees, for split trees and generalized split trees (as defined here), and for trees defined by a continuous-time branching process. These general results include, for example, random labelled trees, ordered trees, random recursive trees, preferential attachment trees, and binary search trees.

MSC classification

Primary: 60C05: Combinatorial probability 05C05: Trees
Secondary: 05C12: Distance in graphs 60J80: Branching processes (Galton-Watson, birth-and-death, etc.)
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 6 , November 2021 , pp. 849 - 893
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Footnotes

†

Supported by the Knut and AliceWallenberg Foundation

References

Abraham, Romain & Delmas, Jean-François: Local limits of conditioned Galton-Watson trees: the condensation case. Electron. J. Probab. 19 (2014), no. 56, 29 pp.Google Scholar
Louigi, Addario-Berry, Broutin, Nicolas & Holmgren, Cecilia: Cutting down trees with a Markov chainsaw. Ann. Appl. Probab. 24 (2014), no. 6, 2297–2339.Google Scholar
Michael, Albert, Cecilia, Holmgren, Tony Johansson & Fiona Skerman: Embedding small digraphs and permutations in binary trees and split trees. Algorithmica 82 (2020), no. 3, 589–615.Google Scholar
Aldous, David: Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228–266.Google Scholar
Aldous, David: The continuum random tree I. Ann. Probab. 19 1 (1991), 1–28.CrossRefGoogle Scholar
Aldous, David: The continuum random tree II: an overview. Stochastic Analysis (Durham, 1990), 23–70, London Math. Soc. Lecture Note Ser. 167, Cambridge Univ. Press, Cambridge, 1991.CrossRefGoogle Scholar
Aldous, David: The continuum random tree III. Ann. Probab. 21 (1993), no. 1, 248–289.CrossRefGoogle Scholar
Gabriel, Berzunza, Cai, Xing Shi & Holmgren, Cecilia: The asymptotic non-normality of the giant cluster for percolation on random split trees. Preprint, 2019. arXiv:1902.08109v4Google Scholar
Biggins, J. D.: The growth and spread of the general branching random walk. Ann. Appl. Probab. 5 (1995), no. 4, 1008–1024.CrossRefGoogle Scholar
Biggins, J. D.: How fast does a general branching random walk spread? Classical and Modern Branching Processes (Minneapolis, MN, 1994), 19–39, Springer, New York, 1997.CrossRefGoogle Scholar
Billingsley, Patrick: Convergence of Probability Measures. Wiley, New York, 1968.Google Scholar
Bogachev, Vladimir I.: Measure theory. Vol. I, II. Springer-Verlag, Berlin, 2007.CrossRefGoogle Scholar
Broutin, N., Devroye, L., McLeish, E. & de la Salle, M.: The height of increasing trees. Random Structures Algorithms 32 (2008), no. 4, 494–518.CrossRefGoogle Scholar
Devroye, Luc: Universal limit laws for depths in random trees. SIAM J. Comput. 28 (1999), no. 2, 409–432.CrossRefGoogle Scholar
Diaconis, Persi & Janson, Svante: Graph limits and exchangeable random graphs. Rend. Mat. Appl. (7) 28 (2008), no. 1, 33–61.Google Scholar
Doney, R. A.: A limit theorem for a class of supercritical branching processes. Journal of Applied Probability 9 (1972), no. 4, 707–724.CrossRefGoogle Scholar
Andreas, 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 Mathematics 53:3 (1984), 321–402.Google Scholar
Andreas, Dress, Vincent Moulton & Werner Terhalle: T-theory: an overview. European J. Combin. 17 (1996), no. 2-3, 161–175.Google Scholar
Duquesne, Thomas: A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31 (2003), no. 2, 996–1027.Google Scholar
Elek, Gábor & Tardos, Gábor: Convergence and limits of finite trees. Preprint, 2020. arXiv: 2001.00905Google Scholar
Andreas, Greven, Pfaffelhuber, Peter & Winter, Anita: Convergence in distribution of random metric measure spaces (Λ-coalescent measure trees). Prob. Theo. Rel. Fields 145 (2009), no. 1-2, 285–322.Google Scholar
Gromov, Misha: Metric Structures for Riemannian and Non-Riemannian Spaces. Birkhäuser, Boston, MA, 1999, 2001.Google Scholar
Allan, Gut. Probability: A Graduate Course, 2nd ed., Springer, New York, 2013.Google Scholar
Haas, Bénédicte & Miermont, Grégory: Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees. Ann. Probab. 40 (2012), no. 6, 2589–2666.CrossRefGoogle Scholar
Holmgren, Cecilia: Novel characteristic of split trees by use of renewal theory. Electron. J. Probab. 17 (2012), no. 5, 27 pp.CrossRefGoogle Scholar
Holmgren, Cecilia & Janson, Svante: Fringe trees, Crump–Mode–Jagers branching processes and m-ary search trees. Probab. Surv. 14 (2017), 53–154.CrossRefGoogle Scholar
Holmgren, Cecilia & Janson, Svante: Fringe trees, Crump–Mode–Jagers branching processes and m-ary search trees. Preprint version of [26], 2016. arXiv: 1601.03691CrossRefGoogle Scholar
Jagers, Peter: Branching Processes with Biological Applications. John Wiley & Sons, London, 1975.Google Scholar
Janson, Svante: Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation. Probab. Surv. 9 (2012), 103–252.CrossRefGoogle Scholar
Janson, Svante: Random recursive trees and preferential attachment trees are random split trees. Combin. Probab. Comput. 28 (2019), no. 1, 81–99.CrossRefGoogle Scholar
Janson, Svante: On the Gromov–Prohorov distance. Preprint, 2020. arXiv: 2005.13505Google Scholar
Svante, Janson, Jonsson, Thordur & Stefánsson, Sigurdur Örn: Random trees with superexponential branching weights. J. Phys. A 44 (2011), no. 48, 485002, 16 pp.Google Scholar
Jonsson, Thordur & Stefánsson, Sigurdur Örn: Condensation in nongeneric trees. J. Stat. Phys. 142 (2011), no. 2, 277–313.CrossRefGoogle Scholar
Kallenberg, Olav: Foundations of Modern Probability. 2nd ed., Springer, New York, 2002.CrossRefGoogle Scholar
Kortchemski, Igor: Limit theorems for conditioned non-generic Galton–Watson trees. Ann. Inst. Henri Poincaré Probab. Stat. 51 (2015), no. 2, 489–511.CrossRefGoogle Scholar
Le Gall, Jean-François: Random trees and applications. Probab. Surv. 2 (2005), 245–311.CrossRefGoogle Scholar
Le Gall, Jean-François: Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), no. 1, 35–62.CrossRefGoogle Scholar
Löhr, Wolfgang: Equivalence of Gromov–Prohorov– and Gromov’s $\underline{\square}_{\lambda}$ -metric on the space of metric measure spaces. Electron. Commun. Probab. 18 (2013), no. 17, 10 pp.Google Scholar
Lovász, László: Large Networks and Graph Limits. American Mathematical Society, Providence, RI, 2012.CrossRefGoogle Scholar
Mahmoud, Hosam M. & Neininger, Ralph: Distribution of distances in random binary search trees. Ann. Appl. Probab. 13 (2003), no. 1, 253–276.CrossRefGoogle Scholar
Miermont, Grégory: Tessellations of random maps of arbitrary genus. Ann. Sci. Éc. Norm. Supér. (4) 42 (2009), no. 5, 725–781.Google Scholar
Morris, Kate, Alois Panholzer & Helmut Prodinger: On some parameters in heap ordered trees. Combin. Probab. Comput. 13 (2004), no. 4-5, 677–696.CrossRefGoogle Scholar
Munsonius, Götz Olaf; Rüschendorf, Ludger: Limit theorems for depths and distances in weighted random b-ary recursive trees. J. Appl. Probab. 48 (2011), no. 4, 1060–1080.CrossRefGoogle Scholar
Nerman, Olle: On the convergence of supercritical general (C-M-J) branching processes. Z. Wahrsch. Verw. Gebiete 57 (1981), no. 3, 365–395.Google Scholar
Panholzer, Alois: The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees. Random Structures Algorithms 25 (2004), no. 2, 179–207.CrossRefGoogle Scholar
Panholzer, Alois & Prodinger, Helmut: Spanning tree size in random binary search trees. Ann. Appl. Probab. 14 (2004), no. 2, 718–733.CrossRefGoogle Scholar
Panholzer, Alois & Prodinger, Helmut: Analysis of some statistics for increasing tree families. Discrete Math. Theor. Comput. Sci. 6 (2004), no. 2, 437–460.Google Scholar
Ryvkina, Jelena: Ein universeller zentraler Grenzwertsatz für den Abstand zweier Kugeln in zufälligen Splitbäumen. Diploma Thesis, Johann Wolfgang Goethe-Universität, Frankfurt, 2008. urn:nbn:de:hebis:30-57448Google Scholar
Stufler, Benedikt: Local limits of large Galton-Watson trees rerooted at a random vertex. Ann. Inst. Henri Poincaré Probab. Stat. 55 (2019), no. 1, 155–183.CrossRefGoogle Scholar
Villani, Cédric: Optimal transport. Springer-Verlag, Berlin, 2009.CrossRefGoogle Scholar