Subcritical $\mathcal {U}$-bootstrap percolation models have non-trivial phase transitions
HTML articles powered by AMS MathViewer
- by Paul Balister, Béla Bollobás, Michał Przykucki and Paul Smith PDF
- Trans. Amer. Math. Soc. 368 (2016), 7385-7411 Request permission
Abstract:
We prove that there exist natural generalizations of the classical bootstrap percolation model on $\mathbb {Z}^2$ that have non-trivial critical probabilities, and moreover we characterize all homogeneous, local, monotone models with this property.
Van Enter (1987) (in the case $d=r=2$) and Schonmann (1992) (for all $d \geqslant r \geqslant 2$) proved that $r$-neighbour bootstrap percolation models have trivial critical probabilities on $\mathbb {Z}^d$ for every choice of the parameters $d \geqslant r \geqslant 2$: that is, an initial set of density $p$ almost surely percolates $\mathbb {Z}^d$ for every $p>0$. These results effectively ended the study of bootstrap percolation on infinite lattices.
Recently Bollobás, Smith and Uzzell introduced a broad class of percolation models called $\mathcal {U}$-bootstrap percolation, which includes $r$-neighbour bootstrap percolation as a special case. They divided two-dimensional $\mathcal {U}$-bootstrap percolation models into three classes – subcritical, critical and supercritical – and they proved that, like classical 2-neighbour bootstrap percolation, critical and supercritical $\mathcal {U}$-bootstrap percolation models have trivial critical probabilities on $\mathbb {Z}^2$. They left open the question as to what happens in the case of subcritical families. In this paper we answer that question: we show that every subcritical $\mathcal {U}$-bootstrap percolation model has a non-trivial critical probability on $\mathbb {Z}^2$. This is new except for a certain ‘degenerate’ subclass of symmetric models that can be coupled from below with oriented site percolation. Our results re-open the study of critical probabilities in bootstrap percolation on infinite lattices, and they allow one to ask many questions of subcritical bootstrap percolation models that are typically asked of site or bond percolation.
References
- M. Aizenman and J. L. Lebowitz, Metastability effects in bootstrap percolation, J. Phys. A 21 (1988), no. 19, 3801–3813. MR 968311
- Paul Balister, Béla Bollobás, and Alan Stacey, Improved upper bounds for the critical probability of oriented percolation in two dimensions, Random Structures Algorithms 5 (1994), no. 4, 573–589. MR 1293080, DOI 10.1002/rsa.3240050407
- József Balogh, Béla Bollobás, Hugo Duminil-Copin, and Robert Morris, The sharp threshold for bootstrap percolation in all dimensions, Trans. Amer. Math. Soc. 364 (2012), no. 5, 2667–2701. MR 2888224, DOI 10.1090/S0002-9947-2011-05552-2
- József Balogh, Béla Bollobás, and Robert Morris, Bootstrap percolation in three dimensions, Ann. Probab. 37 (2009), no. 4, 1329–1380. MR 2546747, DOI 10.1214/08-AOP433
- Itai Benjamini, Gil Kalai, and Oded Schramm, Noise sensitivity of Boolean functions and applications to percolation, Inst. Hautes Études Sci. Publ. Math. 90 (1999), 5–43 (2001). MR 1813223
- B. Bollobás, H. Duminil-Copin, R. Morris, and P. J. Smith, Universality of two-dimensional critical cellular automata, Preprint, http://arxiv.org/abs/1406.6680.
- Béla Bollobás and Oliver Riordan, Percolation, Cambridge University Press, New York, 2006. MR 2283880, DOI 10.1017/CBO9781139167383
- B. Bollobás, P. J. Smith, and A. J. Uzzell, Monotone cellular automata in a random environment, To appear, Combin. Probab. Comput.
- Kathrin Bringmann and Karl Mahlburg, Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation, Trans. Amer. Math. Soc. 364 (2012), no. 7, 3829–3859. MR 2901236, DOI 10.1090/S0002-9947-2012-05610-8
- Raphaël Cerf and Emilio N. M. Cirillo, Finite size scaling in three-dimensional bootstrap percolation, Ann. Probab. 27 (1999), no. 4, 1837–1850. MR 1742890, DOI 10.1214/aop/1022677550
- R. Cerf and F. Manzo, The threshold regime of finite volume bootstrap percolation, Stochastic Process. Appl. 101 (2002), no. 1, 69–82. MR 1921442, DOI 10.1016/S0304-4149(02)00124-2
- J. Chalupa, P. L. Leath, and G. R. Reich, Bootstrap percolation on a Bethe latice, J. Phys. C 12 (1979), L31–L35.
- Peter Gács, Clairvoyant scheduling of random walks, Random Structures Algorithms 39 (2011), no. 4, 413–485. MR 2846299, DOI 10.1002/rsa.20368
- Christophe Garban, Gábor Pete, and Oded Schramm, The Fourier spectrum of critical percolation, Acta Math. 205 (2010), no. 1, 19–104. MR 2736153, DOI 10.1007/s11511-010-0051-x
- Janko Gravner and David Griffeath, Threshold growth dynamics, Trans. Amer. Math. Soc. 340 (1993), no. 2, 837–870. MR 1147400, DOI 10.1090/S0002-9947-1993-1147400-3
- Janko Gravner, Alexander E. Holroyd, and Robert Morris, A sharper threshold for bootstrap percolation in two dimensions, Probab. Theory Related Fields 153 (2012), no. 1-2, 1–23. MR 2925568, DOI 10.1007/s00440-010-0338-z
- Lawrence Gray, John C. Wierman, and R. T. Smythe, Lower bounds for the critical probability in percolation models with oriented bonds, J. Appl. Probab. 17 (1980), no. 4, 979–986. MR 587198, DOI 10.2307/3213207
- Alexander E. Holroyd, Sharp metastability threshold for two-dimensional bootstrap percolation, Probab. Theory Related Fields 125 (2003), no. 2, 195–224. MR 1961342, DOI 10.1007/s00440-002-0239-x
- Alexander E. Holroyd, Thomas M. Liggett, and Dan Romik, Integrals, partitions, and cellular automata, Trans. Amer. Math. Soc. 356 (2004), no. 8, 3349–3368. MR 2052953, DOI 10.1090/S0002-9947-03-03417-2
- M. Jeng and J. M. Schwarz, On the study of jamming percolation, J. Stat. Phys. 131 (2008), no. 4, 575–595. MR 2398943, DOI 10.1007/s10955-008-9514-2
- M. Jeng and J. M. Schwarz, Force-balance percolation, Phys. Rev. E 81 (2010), 01134.
- R. Morris, The second term for bootstrap percolation in two dimensions, In preparation, http://w3.impa.br/~rob/boot2d_sharp.pdf.
- T. S. Mountford, Critical length for semi-oriented bootstrap percolation, Stochastic Process. Appl. 56 (1995), no. 2, 185–205. MR 1325219, DOI 10.1016/0304-4149(94)00061-W
- Roberto H. Schonmann, Critical points of two-dimensional bootstrap percolation-like cellular automata, J. Statist. Phys. 58 (1990), no. 5-6, 1239–1244. MR 1049067, DOI 10.1007/BF01026574
- Roberto H. Schonmann, On the behavior of some cellular automata related to bootstrap percolation, Ann. Probab. 20 (1992), no. 1, 174–193. MR 1143417
- Oded Schramm and Jeffrey E. Steif, Quantitative noise sensitivity and exceptional times for percolation, Ann. of Math. (2) 171 (2010), no. 2, 619–672. MR 2630053, DOI 10.4007/annals.2010.171.619
- Cristina Toninelli and Giulio Biroli, A new class of cellular automata with a discontinuous glass transition, J. Stat. Phys. 130 (2008), no. 1, 83–112. MR 2375957, DOI 10.1007/s10955-007-9420-z
- Aernout C. D. van Enter, Proof of Straley’s argument for bootstrap percolation, J. Statist. Phys. 48 (1987), no. 3-4, 943–945. MR 914911, DOI 10.1007/BF01019705
- Aernout C. D. van Enter and Tim Hulshof, Finite-size effects for anisotropic bootstrap percolation: logarithmic corrections, J. Stat. Phys. 128 (2007), no. 6, 1383–1389. MR 2352015, DOI 10.1007/s10955-007-9377-y
Additional Information
- Paul Balister
- Affiliation: Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee 38152
- MR Author ID: 340031
- Email: pbalistr@memphis.edu
- Béla Bollobás
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom – and – Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee 38152 – and – London Institute for Mathematical Sciences, 35a South Street, Mayfair, London W1K 2XF, United Kingdom
- MR Author ID: 38980
- Email: b.bollobas@dpmms.cam.ac.uk
- Michał Przykucki
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom – and – London Institute for Mathematical Sciences, 35a South Street, Mayfair, London W1K 2XF, United Kingdom
- MR Author ID: 897671
- Email: mp@lims.ac.uk
- Paul Smith
- Affiliation: IMPA, 110 Estrada Dona Castorina, Jardim Botânico, Rio de Janeiro, 22460-320, Brazil
- Email: psmith@impa.br
- Received by editor(s): November 22, 2013
- Received by editor(s) in revised form: September 8, 2014, and October 6, 2014
- Published electronically: January 27, 2016
- Additional Notes: The first author was partially supported by NSF grant DMS 1301614. The second author was partially supported by NSF grant DMS 1301614 and MULTIPLEX no. 317532. The third author was supported by MULTIPLEX no. 317532. The fourth author was supported by a CNPq bolsa PDJ
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 7385-7411
- MSC (2010): Primary 60K35, 82B26, 60C05
- DOI: https://doi.org/10.1090/tran/6586
- MathSciNet review: 3471095