Abstract
In the bootstrap percolation on the n-dimensional hypercube, in the initial position each of the 2n sites is occupied with probability p and empty with probability 1−p, independently of the state of the other sites. Every occupied site remains occupied for ever, while an empty site becomes occupied if at least two of its neighbours are occupied. If at the end of the process every site is occupied, we say that the (initial) position spans the hypercube. We shall show that there are constants c 1,c 2>0 such that for the probability of spanning tends to 1 as n→∞, while for the probability tends to 0. Furthermore, we shall show that for each n the transition has a sharp threshold function.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Achlioptas, D., Friedgut, E.: A sharp threshold for k-colorability. Random Structures Algorithm 14, 63–70 (1999)
Allouche, J.-P., Courbage, M., Skordev, G.: Notes on cellular automata. Cubo Matemática Educacional 3, 213–244 (2001)
Aizenman, M., Lebowitz, J.L.: Metastability effects in bootstrap percolation. J. Phys. A 21, 3801–3813 (1988)
Andjel, E.D.: Characteristic exponents for two-dimensional bootstrap percolation. Ann. Probab. 21, 926–935 (1993)
Balogh, J.: Graph Parameters and Bootstrap Percolation, Ph.D. Dissertation, Memphis, 2001 May
Balogh, J., Bollobás, B.: Sharp thresholds in bootstrap percolation. Physics A 326, 305–312 (2003)
Balogh, J., Pete, G.: Random disease on the square grid. Random Structures Algorithms 13, 409–422 (1998)
van den Berg, J., Kesten, H.: Inequalities with applications to percolation and reliability. J. Appl. Probab. 22, 556–569 (1985)
Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays. Vol. 2, Academic Press. London, 1982
Bollobás, B.: Random Graphs. 2nd edition, Cambridge University Press, Cambridge, 2001, xviii + 498 pp.
Burks, A.W. (ed.): Essays on Cellular Automata. University of Illinois Press, 1970
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. Stochastic Process. Appl. 101, 69–82 (2002)
van Enter, A.C.D., Adler, J., Duarte, J.A.M.S.: Finite-size effects for some bootstrap percolation models. J. Statist. Phys. 60, 323–332 (1990)
van Enter, A.C.D., Adler, J., Duarte, J.A.M.S.: Addendum: ``Finite size effects for some bootstrap percolation models''. J. Statist. Phys. 62, 505–506 (1991)
Friedgut, E.: Sharp thresholds of graph properties, and the k-sat problem. With an appendix by J. Bourgain. J. Am. Math. Soc. 12, 1017–1054 (1999)
Friedgut, E., Kalai, G.: Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc. 124, 2993–3002 (1996)
Gardner, M.: Wheels, Life and Other Mathematical Amusements. W. H. Freeman and Co., 1983
Gravner, J., McDonald, E.: Bootstrap percolation in a polluted environment, J. Statist. Phys. 87, 915–927 (1997)
Holroyd, A.E.: Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Rela. Fields 125, 195–224 (2003)
Mountford, T.S.: Rates for the probability of large cubes being non-internally spanned in modified bootstrap percolation. Probab. Theory Related Fields 93, 159–167 (1992)
Mountford, T.S.: Critical length for semi-oriented bootstrap percolation. Stochastic Process. Appl. 56, 185–205 (1995)
Reimer, D.: Proof of the van den Berg-Kesten conjecture. Combin. Probab. Comput. 9, 27–32 (2000)
Schonmann, R.H.: Critical points of two-dimensional bootstrap percolation-like cellular automata. J. Statist. Phys. 58, 1239–1244 (1990)
Schonmann, R.H.: On the behavior of some cellular automata related to bootstrap percolation. Ann. Probab. 20, 174–193 (1992)
Ulam, S.: Random processes and transformations. In: Proceedings of the International Congress of Mathematicians. Cambridge, Mass., 1950, Am. Math. Soc., Providence, R.I., 2, 264–275 (1952)
Author information
Authors and Affiliations
Corresponding author
Additional information
J. Balogh: work was done while at The University of Memphis, USA
Research supported in part by NSF grant DMS0302804
Research supported in part by NSF grant ITR 0225610 and DARPA grant F33615-01-C-1900
Rights and permissions
About this article
Cite this article
Balogh, J., Bollobás, B. Bootstrap percolation on the hypercube. Probab. Theory Relat. Fields 134, 624–648 (2006). https://doi.org/10.1007/s00440-005-0451-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-005-0451-6