×
Balogh, József; Bollobás, Béla; Morris, Robert

Bootstrap percolation in three dimensions. (English) Zbl 1187.60082

Ann. Probab. 37, No. 4, 1329-1380 (2009).
Author’s abstract: By bootstrap percolation we mean the following deterministic process on a graph \(G\). Given a set \(A\) of vertices “infected” at time 0, new vertices are subsequently infected, at each time step, if they have at least \(r\in \mathbb N\) previously infected neighbors. When the set \(A\) is chosen at random, the main aim is to determine the critical probability \(p_c(G,r)\) at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the \(d\)-dimensional grid \([n]^d\): with \(2\leq r\leq d\) fixed, it was proved by R. Cerf and E. N. M. Cirillo [Ann. Probab. 27, No. 4, 1837–1850 (1999; Zbl 0960.60088)] (for \(d=r=3\)), and by R. Cerf and F. Manzo [Stochastic Processes Appl. 101, No. 1, 69-82 (2002; Zbl 1075.82010)] (in general), that \[ p_c([n]^d,r) = \Theta \left(\frac {1}{\log _{r-1}^n}\right)^{d-r+1}, \] where \(\log _{(r)}\) is an \(r\)-times iterated logarithm. However, the exact threshold function is only known in the case \(d=r=2\), where it was shown by Holroyd to be \((1+o(1))\frac{\pi ^2}{18\log n}\). In this paper we shall determine the exact threshold in the crucial case \(d=r=3\), and lay the groundwork for solving the problem for all fixed \(d\) and \(r\).
Reviewer: Jonathan Peterson (Ithaca)

Cited in 2 Reviews
Cited in 57 Documents

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60C05 Combinatorial probability
82B43 Percolation

Keywords:

bootstrap percolation; sharp threshold

Citations:

Zbl 0960.60088; Zbl 1075.82010
Cite Review PDF
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Decimal expansion of ’mu’, a percolation constant associated with the asymptotic threshold for 3-dimensional bootstrap percolation.

References:

[1] Adler, J. and Lev, U. (2003). Bootstrap percolation: Visualizations and applications. Braz. J. Phys. 33 641-644.
[2] 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
[3] 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
[4] Balogh, J. and Bollobás, B. (2003). Sharp thresholds in bootstrap percolation. Phys. A 326 305-312. · Zbl 1025.60042 · doi:10.1016/S0378-4371(03)00364-9
[5] Balogh, J., Bollobás, B. and Morris, R. (2009). Bootstrap percolation on the hypercube. Unpublished manuscript. · Zbl 1198.60041
[6] 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
[7] Balogh, J., Bollobás, B., Duminil-Copin, H. and Morris, R. (2009). The sharp metastability threshold for r -neighbour bootstrap percolation. Unpublished manuscript. · Zbl 1238.60108
[8] 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
[9] Balogh, J. and Pete, G. (1998). Random disease on the square grid. Random Structures Algorithms 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
[10] 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
[11] van den Berg, J. and Kesten, H. (1985). Inequalities with applications to percolation and reliability. J. Appl. Probab. 22 556-569. JSTOR: · Zbl 0571.60019 · doi:10.2307/3213860
[12] 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
[13] 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
[14] Chalupa, J., Leath, P. L. and Reich, G. R. (1979). Bootstrap percolation on a Bethe latice. J. Phys. C 12 L31-L35.
[15] 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
[16] Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971). Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22 89-103. · Zbl 0346.06011 · doi:10.1007/BF01651330
[17] Friedgut, E. and Kalai, G. (1996). Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993-3002. JSTOR: · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[18] Gradshteyn, I. S. and Ryzhik, I. M. (1965). Table of Integrals , Series , and Products . Academic Press, New York. · Zbl 0918.65002
[19] 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
[20] Holroyd, A. E. (2006). The metastability threshold for modified bootstrap percolation in d dimensions. Electron. J. Probab. 11 418-433 (electronic). · Zbl 1112.60080
[21] Janson, S. (2009). On percolation in random graphs with given vertex degrees. Electron. J. Probab. 14 87-118. · Zbl 1189.60179
[22] Morris, R. (2009). Glauber dynamics in high dimensions. Unpublished manuscript.
[23] Reimer, D. (2000). Proof of the van den Berg-Kesten conjecture. Combin. Probab. Comput. 9 27-32. · Zbl 0947.60093 · doi:10.1017/S0963548399004113
[24] Schonmann, R. H. (1990). Finite size scaling behavior of a biased majority rule cellular automaton. Phys. A 167 619-627. · doi:10.1016/0378-4371(90)90280-6
[25] 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
[26] van Enter, A. C. D. (1987). Proof of Straley’s argument for bootstrap percolation. J. Statist. Phys. 48 943-945. · Zbl 1084.82548 · doi:10.1007/BF01019705
[27] van Enter, A. C. D., Adler, J. and Duarte, J. A. M. S. (1990). Finite-size effects for some bootstrap percolation models. J. Statist. Phys. 60 323-332. · doi:10.1007/BF01314923
[28] von Neumann, J. (1966). Theory of Self-Reproducing Automata . Univ. Illinois Press, Urbana.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.