Supercritical percolation on large scale-free random trees. (English) Zbl 1309.60094

Bertoin, Jean; Bravo, Gerónimo Uribe

Ann. Appl. Probab. 25, No. 1, 81-103 (2015).

Summary: We consider Bernoulli bond percolation on a large scale-free tree in the supercritical regime, meaning informally that there exists a giant cluster with high probability. We obtain a weak limit theorem for the sizes of the next largest clusters, extending a recent result in [J. Bertoin, Random Struct. Algorithms 44, No. 1, 29–44 (2014; Zbl 1280.05117)] for large random recursive trees. The approach relies on the analysis of the asymptotic behavior of branching processes subject to rare neutral mutations, which may be of independent interest.

MSC:

60K35	Interacting random processes; statistical mechanics type models; percolation theory
60J80	Branching processes (Galton-Watson, birth-and-death, etc.)
60J27	Continuous-time Markov processes on discrete state spaces
60F05	Central limit and other weak theorems
05C80	Random graphs (graph-theoretic aspects)
05C05	Trees

Keywords:

supercritical percolation; random trees; branching processes; weak limit theorem

Citations:

Zbl 1280.05117

References:

[1]	Athreya, K. B., Ghosh, A. P. and Sethuraman, S. (2008). Growth of preferential attachment random graphs via continuous-time branching processes. Proc. Indian Acad. Sci. Math. Sci. 118 473-494. · Zbl 1153.05020 · doi:10.1007/s12044-008-0036-2
[2]	Athreya, K. B. and Ney, P. E. (1972). Branching Processes. Die Grundlehren der mathematischen Wissenschaften 196 . Springer, New York. · Zbl 0259.60002
[3]	Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[4]	Bertoin, J. (2010). A limit theorem for trees of alleles in branching processes with rare neutral mutations. Stochastic Process. Appl. 120 678-697. · Zbl 1193.60099 · doi:10.1016/j.spa.2010.01.017
[5]	Bertoin, J. (2014). Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Structures Algorithms 44 29-44. · Zbl 1280.05117 · doi:10.1002/rsa.20448
[6]	Bollobás, B. and Riordan, O. (2003). Robustness and vulnerability of scale-free random graphs. Internet Math. 1 1-35. · Zbl 1062.05080 · doi:10.1080/15427951.2004.10129080
[7]	Chauvin, B. (1991). Product martingales and stopping lines for branching Brownian motion. Ann. Probab. 19 1195-1205. · Zbl 0738.60079 · doi:10.1214/aop/1176990340
[8]	Devroye, L. (1998). Branching processes and their applications in the analysis of tree structures and tree algorithms. In Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin. 16 249-314. Springer, Berlin. · Zbl 0924.60077 · doi:10.1007/978-3-662-12788-9_7
[9]	Dorogovtsev, S. N., Mendes, J. F. F. and Samukhin, A. N. (2000). Structure of growing networks with preferential linking. Phys. Rev. Lett. 85 4633-4636.
[10]	Drmota, M. (2009). Random Trees : An Interplay between Combinatorics and Probability . Springer, Berlin. · Zbl 1170.05022 · doi:10.1007/978-3-211-75357-6
[11]	Durrett, R. (2010). Probability : Theory and Examples , 4th ed. Cambridge Univ. Press, Cambridge. · Zbl 1202.60001 · doi:10.1017/CBO9780511779398
[12]	Iksanov, A. and Möhle, M. (2007). A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Commun. Probab. 12 28-35. · Zbl 1133.60012 · doi:10.1214/ECP.v12-1253
[13]	Jagers, P. (1989). General branching processes as Markov fields. Stochastic Process. Appl. 32 183-212. · Zbl 0678.92009 · doi:10.1016/0304-4149(89)90075-6
[14]	Kimura, M. (1971). Theoretical foundation of population genetics at the molecular level. Theor. Popul. Biol. 2 174-208. · Zbl 0234.92005 · doi:10.1016/0040-5809(71)90014-1
[15]	Riordan, O. (2005). The small giant component in scale-free random graphs. Combin. Probab. Comput. 14 897-938. · Zbl 1079.05092 · doi:10.1017/S096354830500708X
[16]	Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31 186-202. · Zbl 1144.60051 · doi:10.1002/rsa.20137
[17]	Smythe, R. T. and Mahmoud, H. M. (1994). A survey of recursive trees. Teor. Ĭmovīr. Mat. Stat. 51 1-29. · Zbl 0933.05038
[18]	Szymański, J. (1987). On a nonuniform random recursive tree. In Random Graphs ’ 85 ( Poznań , 1985). North-Holland Math. Stud. 144 297-306. North-Holland, Amsterdam.
[19]	Yule, G. U. (1925). A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, F.R.S. Philos. Trans. R. Soc. Lond. Ser. B 213 21-87.