×

The sharp threshold for bootstrap percolation in all dimensions. (English) Zbl 1238.60108

Summary: In \( r\)-neighbour bootstrap percolation on a graph \( G\), a (typically random) set \( A\) of initially ‘infected’ vertices spreads by infecting (at each time step) vertices with at least \( r\) already-infected neighbours. This process may be viewed as a monotone version of the Glauber dynamics of the Ising model, and has been extensively studied on the \( d\)-dimensional grid \( [n]^d\). The elements of the set \( A\) are usually chosen independently, with some density \( p\), and the main question is to determine \( p_c([n]^d,r)\), the density at which percolation (infection of the entire vertex set) becomes likely. In this paper we prove, for every pair \( d,r \in \mathbb{N}\) with \( d \geq r \geq 2\), that \[ p_c( [n]^d,r ) = \left ( \frac {\lambda (d,r) + o(1)}{\log _{(r-1)} (n)} \right )^{d-r+1} \] as \( n \to \infty \), for some constant \( \lambda (d,r) > 0\), and thus prove the existence of a sharp threshold for percolation in any (fixed) number of dimensions. We moreover determine \( \lambda (d,r)\) for every \( d \geq r \geq 2\).

MSC:

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

References:

[1] J. Adler and U. Lev, Bootstrap Percolation: Visualizations and applications, Braz. J. Phys., 33 (2003), 641-644.
[2] M. Aizenman and J. L. Lebowitz, Metastability effects in bootstrap percolation, J. Phys. A 21 (1988), no. 19, 3801 – 3813. · Zbl 0656.60106
[3] J. Balogh and B. Bollobás, Sharp thresholds in bootstrap percolation, Physica A, 326 (2003), 305-312. · Zbl 1025.60042
[4] József Balogh and Béla Bollobás, Bootstrap percolation on the hypercube, Probab. Theory Related Fields 134 (2006), no. 4, 624 – 648. · Zbl 1087.60068 · doi:10.1007/s00440-005-0451-6
[5] József Balogh, Béla Bollobás, and Robert Morris, Majority bootstrap percolation on the hypercube, Combin. Probab. Comput. 18 (2009), no. 1-2, 17 – 51. · Zbl 1198.60041 · doi:10.1017/S0963548308009322
[6] József Balogh, Béla Bollobás, and Robert Morris, Bootstrap percolation in three dimensions, Ann. Probab. 37 (2009), no. 4, 1329 – 1380. · Zbl 1187.60082 · doi:10.1214/08-AOP433
[7] József Balogh, Béla Bollobás, and Robert Morris, Bootstrap percolation in high dimensions, Combin. Probab. Comput. 19 (2010), no. 5-6, 643 – 692. · Zbl 1263.60082 · doi:10.1017/S0963548310000271
[8] József Balogh, Yuval Peres, and Gábor Pete, Bootstrap percolation on infinite trees and non-amenable groups, Combin. Probab. Comput. 15 (2006), no. 5, 715 – 730. · Zbl 1102.60086 · doi:10.1017/S0963548306007619
[9] József Balogh and Boris G. Pittel, Bootstrap percolation on the random regular graph, Random Structures Algorithms 30 (2007), no. 1-2, 257 – 286. · Zbl 1106.60076 · doi:10.1002/rsa.20158
[10] J. van den Berg and H. Kesten, Inequalities with applications to percolation and reliability, J. Appl. Probab. 22 (1985), no. 3, 556 – 569. · Zbl 0571.60019
[11] Marek Biskup and Roberto H. Schonmann, Metastable behavior for bootstrap percolation on regular trees, J. Stat. Phys. 136 (2009), no. 4, 667 – 676. · Zbl 1177.82048 · doi:10.1007/s10955-009-9798-x
[12] N.S. Branco, S.L.A. de Queiroz and R.R. Dos Santos, Critical exponents for high density and bootstrap percolation, J. Phys. C, 19 (1986), 1909-1921.
[13] Raphaël Cerf and Emilio N. M. Cirillo, Finite size scaling in three-dimensional bootstrap percolation, Ann. Probab. 27 (1999), no. 4, 1837 – 1850. · Zbl 0960.60088 · doi:10.1214/aop/1022677550
[14] R. Cerf and F. Manzo, The threshold regime of finite volume bootstrap percolation, Stochastic Process. Appl. 101 (2002), no. 1, 69 – 82. · Zbl 1075.82010 · doi:10.1016/S0304-4149(02)00124-2
[15] R. Cerf and F. Manzo, A \( d\)-dimensional nucleation and growth model, arXiv:1001.3990. · Zbl 1259.82058
[16] J. Chalupa, P. L. Leath and G. R. Reich, Bootstrap percolation on a Bethe latice, J. Phys. C., 12 (1979), L31-L35.
[17] Paul A. Dreyer Jr. and Fred S. Roberts, Irreversible \?-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math. 157 (2009), no. 7, 1615 – 1627. · Zbl 1163.92035 · doi:10.1016/j.dam.2008.09.012
[18] H. Duminil-Copin and A. Holroyd, Sharp metastability for threshold growth models. In preparation.
[19] Aernout C. D. van Enter, Proof of Straley’s argument for bootstrap percolation, J. Statist. Phys. 48 (1987), no. 3-4, 943 – 945. · Zbl 1084.82548 · doi:10.1007/BF01019705
[20] Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, and Nicola Santoro, Dynamic monopolies in tori, Discrete Appl. Math. 137 (2004), no. 2, 197 – 212. 1st International Workshop on Algorithms, Combinatorics, and Optimization in Interconnection Networks (IWACOIN ’99). · Zbl 1104.90050 · doi:10.1016/S0166-218X(03)00261-0
[21] L. R. G. Fontes and R. H. Schonmann, Bootstrap percolation on homogeneous trees has 2 phase transitions, J. Stat. Phys. 132 (2008), no. 5, 839 – 861. · Zbl 1158.82007 · doi:10.1007/s10955-008-9583-2
[22] L. R. Fontes, R. H. Schonmann, and V. Sidoravicius, Stretched exponential fixation in stochastic Ising models at zero temperature, Comm. Math. Phys. 228 (2002), no. 3, 495 – 518. · Zbl 1004.82013 · doi:10.1007/s002200200658
[23] Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993 – 3002. · Zbl 0864.05078
[24] M. Granovetter, Threshold models of collective behavior, American J. Sociology, 83 (1978), 1420-1443.
[25] Janko Gravner and David Griffeath, Threshold growth dynamics, Trans. Amer. Math. Soc. 340 (1993), no. 2, 837 – 870. · Zbl 0791.58053
[26] Janko Gravner and David Griffeath, Cellular automaton growth on \?²: theorems, examples, and problems, Adv. in Appl. Math. 21 (1998), no. 2, 241 – 304. · Zbl 0919.68090 · doi:10.1006/aama.1998.0599
[27] Janko Gravner and Alexander E. Holroyd, Slow convergence in bootstrap percolation, Ann. Appl. Probab. 18 (2008), no. 3, 909 – 928. · Zbl 1141.60062 · doi:10.1214/07-AAP473
[28] Janko Gravner and Alexander E. Holroyd, Local bootstrap percolation, Electron. J. Probab. 14 (2009), no. 14, 385 – 399. · Zbl 1190.60094 · doi:10.1214/EJP.v14-607
[29] J. Gravner, A.E. Holroyd and R. Morris, A sharper threshold for bootstrap percolation in two dimensions, to appear in Prob. Theory Rel. Fields. · Zbl 1254.60092
[30] Paolo De Gregorio, Aonghus Lawlor, Phil Bradley, and Kenneth A. Dawson, Exact solution of a jamming transition: closed equations for a bootstrap percolation problem, Proc. Natl. Acad. Sci. USA 102 (2005), no. 16, 5669 – 5673. · Zbl 1112.82023 · doi:10.1073/pnas.0408756102
[31] Alexander E. Holroyd, Sharp metastability threshold for two-dimensional bootstrap percolation, Probab. Theory Related Fields 125 (2003), no. 2, 195 – 224. · Zbl 1042.60065 · doi:10.1007/s00440-002-0239-x
[32] Alexander E. Holroyd, The metastability threshold for modified bootstrap percolation in \? dimensions, Electron. J. Probab. 11 (2006), no. 17, 418 – 433. · Zbl 1112.60080 · doi:10.1214/EJP.v11-326
[33] Alexander E. Holroyd, Thomas M. Liggett, and Dan Romik, Integrals, partitions, and cellular automata, Trans. Amer. Math. Soc. 356 (2004), no. 8, 3349 – 3368. · Zbl 1095.60003
[34] Svante Janson, On percolation in random graphs with given vertex degrees, Electron. J. Probab. 14 (2009), no. 5, 87 – 118. · Zbl 1189.60179 · doi:10.1214/EJP.v14-603
[35] S. Janson, T. Łuczak, T. Turova and T. Vallier, Bootstrap percolation on the random graph \( G_{n,p}\), arXiv:1012.3535. · Zbl 1254.05182
[36] M.A. Khan, H. Gould and J. Chalupa, Monte Carlo renormalization group study of bootstrap percolation, J. Phys. C, 18 (1985), L223-L228.
[37] Robert Morris, Zero-temperature Glauber dynamics on \Bbb Z^{\?}, Probab. Theory Related Fields 149 (2011), no. 3-4, 417 – 434. · Zbl 1236.60095 · doi:10.1007/s00440-009-0259-x
[38] J. von Neumann, Theory of Self-Reproducing Automata, Univ. Illinois Press, Urbana, 1966.
[39] Roberto H. Schonmann, On the behavior of some cellular automata related to bootstrap percolation, Ann. Probab. 20 (1992), no. 1, 174 – 193. · Zbl 0742.60109
[40] S. Ulam, Random processes and transformations, Proceedings of the International Congress of Mathematicians, Vol. 2, Cambridge, Mass., 1950, Amer. Math. Soc., Providence, R. I., 1952, pp. 264 – 275.
[41] Duncan J. Watts, A simple model of global cascades on random networks, Proc. Natl. Acad. Sci. USA 99 (2002), no. 9, 5766 – 5771. · Zbl 1022.90001 · doi:10.1073/pnas.082090499
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.