On the non-Gaussian fluctuations of the giant cluster for percolation on random recursive trees
Abstract
We consider a Bernoulli bond percolation on a random recursive tree of size $n\gg 1$, with supercritical parameter $p_n=1-c/\ln n$ for some $c>0$ fixed. It is known that with high probability, there exists then a unique giant cluster of size $G_n\sim e^{-c}n$, and it follows from a recent result of Schweinsberg that $G_n$ has non-Gaussian fluctuations. We provide an explanation of this by analyzing the effect of percolation on different phases of the growth of recursive trees. This alternative approach may be useful for studying percolation on other classes of trees, such as for instance regular trees.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-15
Publication Date: February 27, 2014
DOI: 10.1214/EJP.v19-2822
References
- Barraez, D.; Boucheron, S.; Fernandez de la Vega, W. On the fluctuations of the giant component. Combin. Probab. Comput. 9 (2000), no. 4, 287--304. MR1786919
- Behrisch, Michael; Coja-Oghlan, Amin; Kang, Mihyun. The order of the giant component of random hypergraphs. Random Structures Algorithms 36 (2010), no. 2, 149--184. MR2583059
- Bertoin, J. Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Struct. Alg. 44 (2014), 29--44.
- Bertoin, Jean. Almost giant clusters for percolation on large trees with logarithmic heights. J. Appl. Probab. 50 (2013), no. 3, 603--611. MR3102504
- Bertoin, J. and Uribe Bravo, G. Supercritical percolation on large scale--free random trees. To appear in Ann. Appl. Probab.
- Bollobas, Bela; Riordan, Oliver. Asymptotic normality of the size of the giant component in a random hypergraph. Random Structures Algorithms 41 (2012), no. 4, 441--450. MR2993129
- de La Fortelle, Arnaud. Yule process sample path asymptotics. Electron. Comm. Probab. 11 (2006), 193--199 (electronic). MR2266709
- Devroye, Luc. Applications of the theory of records in the study of random trees. Acta Inform. 26 (1988), no. 1-2, 123--130. MR0969872
- Drmota, Michael. Random trees. An interplay between combinatorics and probability. SpringerWienNewYork, Vienna, 2009. xviii+458 pp. ISBN: 978-3-211-75355-2 MR2484382
- Drmota, Michael; Iksanov, Alex; Moehle, Martin; Roesler, Uwe. A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Structures Algorithms 34 (2009), no. 3, 319--336. MR2504401
- Geluk, J. L.; de Haan, L. Stable probability distributions and their domains of attraction: a direct approach. Probab. Math. Statist. 20 (2000), no. 1, Acta Univ. Wratislav. No. 2246, 169--188. MR1785245
- Goldschmidt, Christina; Martin, James B. Random recursive trees and the Bolthausen-Sznitman coalescent. Electron. J. Probab. 10 (2005), no. 21, 718--745 (electronic). MR2164028
- Holmgren, Cecilia. A weakly 1-stable distribution for the number of random records and cuttings in split trees. Adv. in Appl. Probab. 43 (2011), no. 1, 151--177. MR2761152
- Iksanov, Alex; Möhle, Martin. A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Comm. Probab. 12 (2007), 28--35. MR2407414
- Kemp, Adrienne W. Comments on the Luria-Delbrück distribution. J. Appl. Probab. 31 (1994), no. 3, 822--828. MR1285519
- Kuba, Markus; Panholzer, Alois. Isolating nodes in recursive trees. Aequationes Math. 76 (2008), no. 3, 258--280. MR2461893
- Janson, Svante. Random records and cuttings in complete binary trees. Mathematics and computer science. III, 241--253, Trends Math., Birkhäuser, Basel, 2004. MR2090513
- Meir, A.; Moon, J. W. Cutting down random trees. J. Austral. Math. Soc. 11 1970 313--324. MR0284370
- Meir, A. and Moon, J. W. Cutting down recursive trees. Mathematical Biosciences 21 (1974), 173--181.
- Möhle, M. Convergence results for compound Poisson distributions and applications to the standard Luria-Delbrück distribution. J. Appl. Probab. 42 (2005), no. 3, 620--631. MR2157509
- Pakes, Anthony G. Remarks on the Luria-Delbrück distribution. Comment on: "Analysis
of the Luria-Delbrück distribution using discrete convolution powers'' [J.
Appl. Probab. 29 (1992), no. 2, 255–267; MR1165212 (93c:60014)] by W. T. Ma, G. v. H. Sandri and S. Sarkar.
J. Appl. Probab. 30 (1993), no. 4, 991--994. MR1242029
- Pittel, Boris. On tree census and the giant component in sparse random graphs. Random Structures Algorithms 1 (1990), no. 3, 311--342. MR1099795
- Schweinsberg, Jason. Dynamics of the evolving Bolthausen-Sznitman coalecent. [Dynamics of the evolving Bolthausen-Sznitman coalescent] Electron. J. Probab. 17 (2012), no. 91, 50 pp. MR2988406
- Seierstad, Taral Guldahl. On the normality of giant components. Random Structures Algorithms 43 (2013), no. 4, 452--485. MR3124692
- Stepanov, V. E. The probability of the connectedness of a random graph ${\cal G}_{m}\,(t)$. (Russian) Teor. Verojatnost. i Primenen 15 1970 58--68. MR0270406
This work is licensed under a Creative Commons Attribution 3.0 License.