Abstract
Two-dimensional bootstrap percolation is a cellular automaton in which sites become ‘infected’ by contact with two or more already infected nearest neighbours. We consider these dynamics, which can be interpreted as a monotone version of the Ising model, on an n × n square, with sites initially infected independently with probability p. The critical probability p c is the smallest p for which the probability that the entire square is eventually infected exceeds 1/2. Holroyd determined the sharp first-order approximation: p c ~ π 2/(18 log n) as n → ∞. Here we sharpen this result, proving that the second term in the expansion is −(log n)−3/2+o(1), and moreover determining it up to a poly(log log n)-factor. The exponent −3/2 corrects numerical predictions from the physics literature.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adler J., Lev U.: Bootstrap percolation: visualizations and applications. Braz. J. Phys. 33, 641–644 (2003)
Aizenman M., Lebowitz J.L.: Metastability effects in bootstrap percolation. J. Phys. A. 21, 3801–3813 (1988)
Balogh, J.: Graph parameters and bootstrap percolation. Ph.D. Dissertation, Memphis (2001)
Balogh J., Bollobás B.: Bootstrap percolation on the hypercube. Prob. Theory Relat. Fields 134, 624–648 (2006)
Balogh J., Bollobás B., Morris R.: Majority bootstrap percolation on the hypercube. Combin. Probab. Comput. 18, 17–51 (2009)
Balogh J., Bollobás B., Morris R.: Bootstrap percolation in three dimensions. Ann. Probab. 37, 1329–1380 (2009)
Balogh, J., Bollobás, B., Morris, R.: Bootstrap percolation in high dimensions. Combin. Probab. Comput. arXiv:0907.3097 (2010, to appear)
Balogh, J., Bollobás, B., Duminil-Copin, H., Morris, R.: The sharp threshold for bootstrap percolation in all dimensions. arXiv:1010.3326 (2010, submitted)
Balogh J., Peres Y., Pete G.: Bootstrap percolation on infinite trees and non-amenable groups. Combin. Probab. Comput. 15, 715–730 (2006)
Balogh J., Pittel B.: Bootstrap percolation on random regular graphs. Random Struct. Algorithms 30, 257–286 (2007)
Baxter, G.J., Dorogovtsev, S.N., Goltsev, A.V., Mendes, J.F.F.: Bootstrap percolation on complex networks. Phys. Rev. E 82. arXiv:1003.5583 (2010, to appear)
van den Berg J., Kesten H.: Inequalities with applications to percolation and reliability. J. Appl. Probab. 22, 556–589 (1985)
Biskup M., Schonmann R.H.: Metastable behavior for bootstrap percolation on regular trees. J. Stat. Phys. 136(4), 667–676 (2009)
Bollobás, B.: The Art of Mathematics: Coffee Time in Memphis. Cambridge University Press, Cambridge (2006)
Bringmann, K., Mahlburg, K.: Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation. arXiv:1001.1977 (2010)
Cerf R., Cirillo E.N.M.: Finite size scaling in three-dimensional bootstrap percolation. Ann. Probab. 27, 1837–1850 (1999)
Cerf R., Manzo F.: The threshold regime of finite volume bootstrap percolation. Stoch. Proc. Appl. 101, 69–82 (2002)
Cerf, R., Manzo, F.: A d-dimensional nucleation and growth model. arXiv:1001.3990 (2010)
Chalupa J., Leath P.L., Reich G.R.: Bootstrap percolation on a Bethe latice. J. Phys. C. 12, L31–L35 (1979)
Dehghanpour P., Schonmann R.H.: Metropolis dynamics relaxation via nucleation and growth. Commun. Math. Phys. 188, 89–119 (1997)
Dehghanpour P., Schonmann R.H.: A nucleation-and-growth model. Probab. Theory Relat. Fields 107, 123–135 (1997)
Duminil-Copin, H., Holroyd, A.: Sharp metastability for threshold growth models. (2010, in preparation)
Fontes L.R., Schonmann R.H.: Bootstrap percolation on homogeneous trees has 2 phase transitions. J. Stat. Phys. 132, 839–861 (2008)
Fontes L.R., Schonmann R.H., Sidoravicius V.: Stretched exponential fixation in stochastic Ising models at zero temperature. Commun. Math. Phys. 228, 495–518 (2002)
Froböse K.: Finite-size effects in a cellular automaton for diffusion. J. Stat. Phys. 55(5–6), 1285–1292 (1989)
Granovetter M.: Threshold models of collective behavior. Am. J. Sociol. 83, 1420–1443 (1978)
Gravner J., Griffeath D.: Threshold growth dynamics. Trans. Am. Math. Soc. 340, 837–870 (1993)
Gravner J., Holroyd A.E.: Slow convergence in bootstrap percolation. Ann. Appl. Probab. 18, 909–928 (2008)
Gravner J., Holroyd A.E.: Local bootstrap percolation. Electron. J. Probab. 14, 385–399 (2009)
De Gregorio P., Lawlor A., Bradley P., Dawson K.A.: Exact solution of a jamming transition: closed equations for a bootstrap percolation problem. Proc. Natl. Acad. Sci. USA 102(16), 5669–5673 (2005)
Holroyd A.: Sharp metastability threshold for two-dimensional bootstrap percolation. Prob. Theory Relat. Fields 125, 195–224 (2003)
Holroyd A.: The metastability threshold for modified bootstrap percolation in d dimensions. Electron. J. Probab. 11, 418–433 (2006)
Holroyd A.E., Liggett T.M., Romik D.: Integrals, partitions, and cellular automata. Trans. Am. Math. Soc. 356(8), 3349–3368 (2004)
Janson S.: On percolation in Random Graphs with given vertex degrees. Electron. J. Probab. 14, 86–118 (2009)
Janson, S., Łuczak, T., Turova, T., Vallier, T.: Bootstrap percolation on the random graph G n,p . arXiv:1012.3535
Kesten H., Schonmann R.H.: On some growth models with a small parameter. Probab. Theory Relat. Fields 101, 435–468 (1995)
Morris, R.: Minmal percolating sets in bootstrap percolation. Electron. J. Combin. 16, Research Paper 2, 20 pp (2009)
Morris, R.: Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\). Probab. Theory Relat. Fields. arXiv:0809.0353 (2010, to appear)
Richardson D.: Random growth in a tessellation. Proc. Cambridge Philos. Soc. 74, 515–528 (1973)
Schonmann R.H.: On the behaviour of some cellular automata related to bootstrap percolation. Ann. Probab. 20, 174–193 (1992)
Watts D.J.: A simple model of global cascades on random networks. Proc. Natl. Acad. Sci. 99, 5766–5771 (2002)
Winkler P.: Mathematical Puzzles: A Connoisseur’s Collection. A K Peters Ltd., Natick (2004)
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSF grant DMS 0204376 and the Republic of Slovenia Ministry of Science program P1-285 (JG); NSERC and Microsoft Research (AEH); a JSPS Fellowship and a Research Fellowship from Murray Edwards College, Cambridge (RM).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Gravner, J., Holroyd, A.E. & Morris, R. A sharper threshold for bootstrap percolation in two dimensions. Probab. Theory Relat. Fields 153, 1–23 (2012). https://doi.org/10.1007/s00440-010-0338-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-010-0338-z