×

zbMATH — the first resource for mathematics

Bootstrap percolation on the random graph \(G_{n,p}\). (English) Zbl 1254.05182
Summary: Bootstrap percolation on the random graph \(G_{n,p}\) is a process of spread of “activation” on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least \(r\geq2\) active neighbors become active as well.
We study the size \(A^{\ast}\) of the final active set. The parameters of the model are, besides \(r\) (fixed) and \(n (\text{tending to} \infty)\), the size \(a=a(n)\) of the initially active set and the probability \(p=p(n)\) of the edges in the graph. We show that the model exhibits a sharp phase transition: depending on the parameters of the model, the final size of activation with a high probability is either \(n-o(n)\) or it is \(o(n)\).
We provide a complete description of the phase diagram on the space of the parameters of the model. In particular, we find the phase transition and compute the asymptotics (in probability) for \(A^{\ast}\); we also prove a central limit theorem for \(A^{\ast}\) in some ranges. Furthermore, we provide the asymptotics for the number of steps until the process stops.

MSC:
05C80 Random graphs (graph-theoretic aspects)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Aizenman, M. and Lebowitz, J. L. (1988). Metastability effects in bootstrap percolation. J. Phys. A 21 3801-3813. · Zbl 0656.60106 · doi:10.1088/0305-4470/21/19/017
[2] Amini, H. (2010). Bootstrap percolation and diffusion in random graphs with given vertex degrees. Electron. J. Combin. 17 Research Paper 25, 20. · Zbl 1215.05152 · emis:journals/EJC/Volume_17/Abstracts/v17i1r25.html · eudml:231997
[3] Ball, F. and Britton, T. (2005). An epidemic model with exposure-dependent severities. J. Appl. Probab. 42 932-949. · Zbl 1090.92041 · doi:10.1239/jap/1134587807
[4] Ball, F. and Britton, T. (2009). An epidemic model with infector and exposure dependent severity. Math. Biosci. 218 105-120. · Zbl 1160.92034 · doi:10.1016/j.mbs.2009.01.003
[5] Balogh, J. and Bollobás, B. (2006). Bootstrap percolation on the hypercube. Probab. Theory Related Fields 134 624-648. · Zbl 1087.60068 · doi:10.1007/s00440-005-0451-6
[6] Balogh, J., Bollobás, B., Duminil-Copin, H. and Morris, R. (2012). The sharp threshold for bootstrap percolation in all dimensions. Trans. Amer. Math. Soc. 364 2667-2701. · Zbl 1238.60108 · doi:10.1090/S0002-9947-2011-05552-2
[7] Balogh, J., Bollobás, B. and Morris, R. (2009). Majority bootstrap percolation on the hypercube. Combin. Probab. Comput. 18 17-51. · Zbl 1198.60041 · doi:10.1017/S0963548308009322
[8] Balogh, J., Bollobás, B. and Morris, R. (2009). Bootstrap percolation in three dimensions. Ann. Probab. 37 1329-1380. · Zbl 1187.60082 · doi:10.1214/08-AOP433
[9] Balogh, J., Bollobás, B. and Morris, R. (2010). Bootstrap percolation in high dimensions. Combin. Probab. Comput. 19 643-692. · Zbl 1263.60082 · doi:10.1017/S0963548310000271
[10] Balogh, J., Bollobás, B. and Morris, R. (2011). Graph bootstrap percolation. Preprint. Available at . 1107.1381 · Zbl 1279.68243 · arxiv.org
[11] Balogh, J., Bollobás, B., Morris, R. and Riordan, O. (2011). Linear algebra and bootstrap percolation. Preprint. Available at . 1107.1410 · Zbl 1242.05190 · doi:10.1016/j.jcta.2012.03.005 · arxiv.org
[12] Balogh, J., Peres, Y. and Pete, G. (2006). Bootstrap percolation on infinite trees and non-amenable groups. Combin. Probab. Comput. 15 715-730. · Zbl 1102.60086 · doi:10.1017/S0963548306007619
[13] Balogh, J. and Pete, G. (1998). Random disease on the square grid. In Proceedings of the Eighth International Conference “Random Structures and Algorithms” ( Poznan , 1997) 13 409-422. · Zbl 0964.60006 · doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<409::AID-RSA11>3.0.CO;2-U
[14] Balogh, J. and Pittel, B. G. (2007). Bootstrap percolation on the random regular graph. Random Structures Algorithms 30 257-286. · Zbl 1106.60076 · doi:10.1002/rsa.20158
[15] Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford Studies in Probability 2 . Oxford Univ. Press, Oxford. · Zbl 0746.60002
[16] Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201
[17] Bollobás, B. (1968). Weakly \(k\)-saturated graphs. In Beiträge zur Graphentheorie ( Kolloquium , Manebach , 1967) 25-31. Teubner, Leipzig. · Zbl 0172.48905
[18] Bollobás, B. (2006). The Art of Mathematics : Coffee Time in Memphis . Cambridge Univ. Press, New York. · Zbl 1238.00002
[19] Carroll, L. (1876). The Hunting of the Snark . Macmillan, London.
[20] Cerf, R. and Cirillo, E. N. M. (1999). Finite size scaling in three-dimensional bootstrap percolation. Ann. Probab. 27 1837-1850. · Zbl 0960.60088 · doi:10.1214/aop/1022677550
[21] Cerf, R. and Manzo, F. (2002). The threshold regime of finite volume bootstrap percolation. Stochastic Process. Appl. 101 69-82. · Zbl 1075.82010 · doi:10.1016/S0304-4149(02)00124-2
[22] Cerf, R. and Manzo, F. (2010). A \(d\)-dimensional nucleation and growth model. Preprint. Available at . 1001.3990 · Zbl 1259.82058 · arxiv.org
[23] Cerf, R. and Manzo, F. (2011). Nucleation and growth for the Ising model in \(d\) dimensions at very low temperatures. Preprint. Available at . 1102.1741 · Zbl 1286.60091 · arxiv.org
[24] Chalupa, J., Leath, P. L. and Reich, G. R. (1979). Bootstrap percolation on a Bethe lattice. J. Phys. C 12 L31-L35.
[25] Duminil-Copin, H. and Van Enter, A. C. D. (2010). Sharp metastability threshold for an anisotropic bootstrap percolation model. Preprint. Available at . 1010.4691 · Zbl 1356.60166 · arxiv.org
[26] Fontes, L. R., Schonmann, R. H. and Sidoravicius, V. (2002). Stretched exponential fixation in stochastic Ising models at zero temperature. Comm. Math. Phys. 228 495-518. · Zbl 1004.82013 · doi:10.1007/s002200200658
[27] Gravner, J., Holroyd, A. E. and Morris, A. (2012). A sharper threshold for bootstrap percolation in two dimensions. Probab. Theory Related Fields . To appear. Available at . 1002.3881v2 · Zbl 1254.60092 · arxiv.org
[28] Gut, A. (2005). Probability : A Graduate Course . Springer, New York. · Zbl 1076.60001
[29] Holroyd, A. E. (2003). Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Related Fields 125 195-224. · Zbl 1042.60065 · doi:10.1007/s00440-002-0239-x
[30] Holroyd, A. E., Liggett, T. M. and Romik, D. (2004). Integrals, partitions, and cellular automata. Trans. Amer. Math. Soc. 356 3349-3368 (electronic). · Zbl 1095.60003 · doi:10.1090/S0002-9947-03-03417-2
[31] Janson, S. (1994). Orthogonal decompositions and functional limit theorems for random graph statistics. Mem. Amer. Math. Soc. 111 vi+78. · Zbl 0810.05001
[32] Janson, S. (2009). On percolation in random graphs with given vertex degrees. Electron. J. Probab. 14 87-118. · Zbl 1189.60179 · doi:10.1214/EJP.v14-603 · emis:journals/EJP-ECP/_ejpecp/viewarticle7812.html · eudml:227720
[33] Janson, S. (2009). Probability asymptotics: Notes on notation. Institute Mittag-Leffler Report 12.
[34] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York.
[35] Kallenberg, O. (2002). Foundations of Modern Probability , 2nd ed. Springer, New York. · Zbl 0996.60001
[36] Kozma, R., Puljic, M., Balister, P., Bollobás, B. and Freeman, W. J. (2005). Phase transitions in the neuropercolation model of neural populations with mixed local and non-local interactions. Biol. Cybernet. 92 367-379. · Zbl 1112.92011 · doi:10.1007/s00422-005-0565-z
[37] Martin-Löf, A. (1986). Symmetric sampling procedures, general epidemic processes and their threshold limit theorems. J. Appl. Probab. 23 265-282. · Zbl 0605.92009 · doi:10.2307/3214172
[38] Martin-Löf, A. (1998). The final size of a nearly critical epidemic, and the first passage time of a Wiener process to a parabolic barrier. J. Appl. Probab. 35 671-682. · Zbl 0919.92034 · doi:10.1239/jap/1032265215
[39] Morris, R. (2009). Minimal percolating sets in bootstrap percolation. Electron. J. Combin. 16 Research Paper 2, 20. · Zbl 1178.60070 · emis:journals/EJC/Volume_16/Abstracts/v16i1r2.html · eudml:117288
[40] Morris, R. (2011). Zero-temperature Glauber dynamics on \(\mathbb{Z}^{d}\). Probab. Theory Related Fields 149 417-434. · Zbl 1236.60095 · doi:10.1007/s00440-009-0259-x
[41] Scalia-Tomba, G.-P. (1985). Asymptotic final-size distribution for some chain-binomial processes. Adv. in Appl. Probab. 17 477-495. · Zbl 0581.92023 · doi:10.2307/1427116
[42] Schonmann, R. H. (1992). On the behavior of some cellular automata related to bootstrap percolation. Ann. Probab. 20 174-193. · Zbl 0742.60109 · doi:10.1214/aop/1176989923
[43] Sellke, T. (1983). On the asymptotic distribution of the size of a stochastic epidemic. J. Appl. Probab. 20 390-394. · Zbl 0526.92024 · doi:10.2307/3213811
[44] Tlusty, T. and Eckmann, J. P. (2009). Remarks on bootstrap percolation in metric networks. J. Phys. A 42 205004, 11. · Zbl 1168.82014 · doi:10.1088/1751-8113/42/20/205004
[45] Turova, T. (2012). The emergence of connectivity in neuronal networks: From bootstrap percolation to auto-associative memory. Brain Research 1434 277-284.
[46] Turova, T. S. and Villa, A. E. P. (2007). On a phase diagram for random neural networks with embedded spike timing dependent plasticity. BioSystems 89 280-286.
[47] Vallier, T. (2007). Random graph models and their applications. Ph.D. thesis, Lund Univ.
[48] von Bahr, B. and Martin-Löf, A. (1980). Threshold limit theorems for some epidemic processes. Adv. in Appl. Probab. 12 319-349. · Zbl 0425.60074 · doi:10.2307/1426600
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.