Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T12:59:29.292Z Has data issue: false hasContentIssue false
  • English
  • Français

The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees

Part of: Graph theory Special processes Markov processes

Published online by Cambridge University Press:  29 April 2020

G. Berzunza
G. Berzunza*
Affiliation:
Department of Mathematics, Uppsala University
*
*Postal address: Lägerhyddsvägen 1, Hus 1, 6 och 7, Box 480, 751 06 Uppsala, Sweden. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider random trees associated with the genealogy of Crump–Mode–Jagers processes and perform Bernoulli bond-percolation whose parameter depends on the size of the tree. Our purpose is to show the existence of a giant percolation cluster for appropriate regimes as the size grows. We stress that the family trees of Crump–Mode–Jagers processes include random recursive trees, preferential attachment trees, binary search trees for which this question has been answered by Bertoin [7], as well as (more general) m-ary search trees, fragmentation trees, and median-of-( $2\ell+1$ ) binary search trees, to name a few, where to our knowledge percolation has not yet been studied.

Keywords

Random treepercolationgiant componentCrump–Mode–Jagers processes

MSC classification

Primary: 60J80: Branching processes (Galton-Watson, birth-and-death, etc.)
Secondary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory 05C05: Trees
Type
Original Article
Information
Advances in Applied Probability , Volume 52 , Issue 1 , March 2020 , pp. 266 - 290
Copyright
© Applied Probability Trust 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D. (1991). Asymptotic fringe distributions for general families of random trees. Ann. Appl. Prob. 1, 228–266.CrossRefGoogle Scholar
Athreya, K. B. (2007). Preferential attachment random graphs with general weight function. Internet Math. 4, 401–418.CrossRefGoogle Scholar
Bartle, R. G. (1995). The Elements of Integration and Lebesgue Measure (Wiley ClassicsLibrary). John Wiley, New York.Google Scholar
Baur, E. (2016). Percolation on random recursive trees. Random Structures Algorithms 48, 655–680.CrossRefGoogle Scholar
Baur, E. and Bertoin, J. (2017). Weak limits for the largest subpopulations in Yule processes with high mutation probabilities. Adv. Appl. Prob. 49, 877–902.CrossRefGoogle Scholar
Bertoin, J. (2006). Random Fragmentation and Coagulation Processes (Cambridge Studies in Advanced Mathematics 102). Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Bertoin, J. (2013). Almost giant clusters for percolation on large trees with logarithmic heights. J. Appl. Prob. 50, 603–611.CrossRefGoogle Scholar
Bertoin, J. (2014). On the non-Gaussian fluctuations of the giant cluster for percolation on random recursive trees. Electron. J. Prob. 19, 24, 15 pp.CrossRefGoogle Scholar
Bertoin, J. (2014). Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Structures Algorithms 44, 29–44.CrossRefGoogle Scholar
Bertoin, J. andUribe Bravo, G. (2015). Supercritical percolation on large scale-free random trees. Ann. Appl. Prob. 25, 81–103.CrossRefGoogle Scholar
Berzunza, G. (2015). Yule processes with rare mutation and their applications to percolation on b-ary trees. Electron. J. Prob. 20, 43, 23 pp.CrossRefGoogle Scholar
Bollobás, B. (2001). Random Graphs, 2nd edn (Cambridge Studies in Advanced Mathematics). Cambridge University Press.CrossRefGoogle Scholar
Devroye, L. (1993). On the expected height of fringe-balanced trees. Acta Inform. 30, 459–466.CrossRefGoogle Scholar
Devroye, L. (1999). Universal limit laws for depths in random trees. SIAM J. Comput. 28, 409–432.CrossRefGoogle Scholar
Drmota, M. (2009). Random Trees: An Interplay Between Combinatorics and Probability. Springer, New York and Vienna.CrossRefGoogle Scholar
Durrett, R. (2010). Random Graph Dynamics (Cambridge Series in Statistical and Probabilistic Mathematics 20). Cambridge University Press, Cambridge.Google Scholar
Geiger, J. (1996). Size-biased and conditioned random splitting trees. Stoch. Process. Appl. 65, 187–207.CrossRefGoogle Scholar
Geiger, J. and Kersting, G. (1997). Depth-first search of random trees, and Poisson point processes. In Classical and Modern Branching Processes (Minneapolis, MN, 1994) (IMA Vol. Math. Appl. 84), pp. 111–126. Springer, New York.CrossRefGoogle Scholar
Holmgren, C. and Janson, S. (2017). Fringe trees, Crump–Mode–Jagers branching processes and m-ary search trees. Prob. Surv. 14, 53–154.CrossRefGoogle Scholar
Jagers, P. (1975). Branching Processes with Biological Applications (Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics). Wiley-Interscience, London, New York and Sydney.Google Scholar
Jagers, P. and Nerman, O. (1984). The growth and composition of branching populations. Adv. Appl. Prob. 16, 221–259.CrossRefGoogle Scholar
Janson, S. and Neininger, R. (2008). The size of random fragmentation trees. Prob. Theory Related Fields 142, 399–442.CrossRefGoogle Scholar
Kallenberg, O. (2002). Foundations of Modern Probability, 2nd edn (Probability and its Applications (New York)). Springer, New York.CrossRefGoogle Scholar
Kolmogoroff, A. N. (1941). Über das logarithmisch normale Verteilungsgesetz der Dimensionen der Teilchen bei Zerstückelung. C.R. (Doklady) Acad. Sci. URSS (N.S.) 31, 99–101.Google Scholar
Lambert, A. (2010). The contour of splitting trees is a Lévy process. Ann. Prob. 38, 348–395.CrossRefGoogle Scholar
Mahmoud, H. M. (1994). A strong law for the height of random binary pyramids. Ann. Appl. Prob. 4, 923–932.CrossRefGoogle Scholar
Muntz, R. and Uzgalis, R. (1971). Dynamic storage allocation for binary search trees in a two-level memory. In Proceedings of 4th Annual Princeton Conference on Information Sciences and Systems, pp. 345–349.Google Scholar
Nerman, O. (1981). On the convergence of supercritical general (C-M-J) branching processes. Z. Wahrsch. Verw. Gebiete 57, 365–395.CrossRefGoogle Scholar
Nerman, O. and Jagers, P. (1984). The stable double infinite pedigree process of supercritical branching populations. Z. Wahrsch. Verw. Gebiete 65, 445–460.CrossRefGoogle Scholar
Pitman, J. (1999). Coalescent random forests. J. Combinatorial Theory A 85, 165–193.CrossRefGoogle Scholar
Pitman, J. (2006). Combinatorial Stochastic Processes (Lecture Notes Math. 1875). Springer, Berlin.Google Scholar
Pittel, B. (1994). Note on the heights of random recursive trees and random m-ary search trees. Random Structures Algorithms 5, 337–347.CrossRefGoogle Scholar
Richard, M. (2011). Arbres, processus de branchement non markoviens et processus de Lévy. Doctoral thesis, Université Pierre et Marie Curie–Paris VI.Google Scholar
Rudas, A. and Tóth, B. (2009). Random tree growth with branching processes: a survey. In Handbook of Large-Scale Random Networks (Bolyai Soc. Math. Stud. 18), pp. 171–202. Springer, Berlin.CrossRefGoogle Scholar
Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31, 186–202.CrossRefGoogle Scholar
Szymański, J. (1987). On a nonuniform random recursive tree. In Random Graphs ’85 (Poznań, 1985) (North-Holland Math. Stud. 144), pp. 297–306. North-Holland, Amsterdam.CrossRefGoogle Scholar
Tsirelson, B. (2013). From uniform renewal theorem to uniform large and moderate deviations for renewal-reward processes. Electron. Commun. Prob. 18, 52, 13 pp.CrossRefGoogle Scholar