The second term for two-neighbour bootstrap percolation in two dimensions
HTML articles powered by AMS MathViewer
- by Ivailo Hartarsky and Robert Morris PDF
- Trans. Amer. Math. Soc. 372 (2019), 6465-6505 Request permission
Abstract:
In the $r$-neighbour bootstrap process on a graph $G$, vertices are infected (in each time step) if they have at least $r$ already-infected neighbours. Motivated by its close connections to models from statistical physics, such as the Ising model of ferromagnetism and kinetically constrained spin models of the liquid-glass transition, the most extensively studied case is the two-neighbour bootstrap process on the two-dimensional grid $[n]^2$. Around 15 years ago, in a major breakthrough, Holroyd determined the sharp threshold for percolation in this model, and his bounds were subsequently sharpened further by Gravner and Holroyd, and by Gravner, Holroyd, and Morris.
In this paper we strengthen the lower bound of Gravner, Holroyd, and Morris by proving that the critical probability $p_c\big ( [n]^2,2 \big )$ for percolation in the two-neighbour model on $[n]^2$ satisfies \[ p_c\big ( [n]^2,2 \big ) = \frac {\pi ^2}{18\log n} - \frac {\Theta (1)}{(\log n)^{3/2}} .\] The proof of this result requires a very precise understanding of the typical growth of a critical droplet and involves a number of technical innovations. We expect these to have other applications, for example, to the study of more general two-dimensional cellular automata and to the $r$-neighbour process in higher dimensions.
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, MichałPrzykucki, and Paul Smith, Subcritical $\mathcal {U}$-bootstrap percolation models have non-trivial phase transitions, Trans. Amer. Math. Soc. 368 (2016), no. 10, 7385–7411. MR 3471095, DOI 10.1090/tran/6586
- J. Balogh and B. Bollobás, Sharp thresholds in bootstrap percolation, Phys. A 326 (2003), 305–312.
- 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
- J. van den Berg and U. Fiebig, On a combinatorial conjecture concerning disjoint occurrences of events, Ann. Probab. 15 (1987), no. 1, 354–374. MR 877608
- J. van den Berg and H. Kesten, Inequalities with applications to percolation and reliability, J. Appl. Probab. 22 (1985), no. 3, 556–569. MR 799280, DOI 10.1017/s0021900200029326
- Béla Bollobás, The art of mathematics, Cambridge University Press, New York, 2006. Coffee time in Memphis. MR 2285090, DOI 10.1017/CBO9780511816574
- Béla Bollobás, Hugo Duminil-Copin, Robert Morris, and Paul Smith, The sharp threshold for the Duarte model, Ann. Probab. 45 (2017), no. 6B, 4222–4272. MR 3737910, DOI 10.1214/16-AOP1163
- Béla Bollobás, Hugo Duminil-Copin, Robert Morris, and Paul Smith, Universality of two-dimensional critical cellular automata, Proc. Lond. Math. Soc. (to appear).
- Béla Bollobás, Paul Smith, and Andrew Uzzell, Monotone cellular automata in a random environment, Combin. Probab. Comput. 24 (2015), no. 4, 687–722. MR 3350030, DOI 10.1017/S0963548315000012
- 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 lattice, J. Stat. Phys. 12 (1979), no. 1, L31–L35.
- H. Duminil-Copin and A. Holroyd, Finite volume bootstrap percolation with balanced threshold rules on $\mathbb {Z}^2$, preprint available at http://www.ihes.fr/~duminil/, 2012.
- H. Duminil-Copin and A. C. D. Van Enter, Sharp metastability threshold for an anisotropic bootstrap percolation model, Ann. Probab. 41 (2013), no. 3A, 1218–1242. MR 3098677, DOI 10.1214/11-AOP722
- Hugo Duminil-Copin, Aernout C. D. van Enter, and Tim Hulshof, Higher order corrections for anisotropic bootstrap percolation, Probab. Theory Related Fields 172 (2018), no. 1-2, 191–243. MR 3851832, DOI 10.1007/s00440-017-0808-7
- Anne Fey, Lionel Levine, and Yuval Peres, Growth rates and explosions in sandpiles, J. Stat. Phys. 138 (2010), no. 1-3, 143–159. MR 2594895, DOI 10.1007/s10955-009-9899-6
- 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. MR 1918786, DOI 10.1007/s002200200658
- Janko Gravner and Alexander E. Holroyd, Slow convergence in bootstrap percolation, Ann. Appl. Probab. 18 (2008), no. 3, 909–928. MR 2418233, DOI 10.1214/07-AAP473
- 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
- I. Hartarsky and R. Morris, The second term for two-neighbour bootstrap percolation in two dimensions, arXiv.1806.08931, 2018.
- 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
- Fabio Martinelli, Robert Morris, and Cristina Toninelli, Universality results for kinetically constrained spin models in two dimensions, Comm. Math. Phys. 369 (2019), no. 2, 761–809. MR 3962008, DOI 10.1007/s00220-018-3280-z
- Robert Morris, Zero-temperature Glauber dynamics on $\Bbb Z^d$, Probab. Theory Related Fields 149 (2011), no. 3-4, 417–434. MR 2776621, DOI 10.1007/s00440-009-0259-x
- Robert Morris, Bootstrap percolation, and other automata, European J. Combin. 66 (2017), 250–263. MR 3692148, DOI 10.1016/j.ejc.2017.06.024
- David Reimer, Proof of the van den Berg-Kesten conjecture, Combin. Probab. Comput. 9 (2000), no. 1, 27–32. MR 1751301, DOI 10.1017/S0963548399004113
- A. Uzzell, An improved upper bound for bootstrap percolation in all dimensions, Combin. Probab. Comput. (to appear).
Additional Information
- Ivailo Hartarsky
- Affiliation: Département de Mathématiques et Applications, École Normale Supérieure, CNRS, PSL Research University, 45 rue d’Ulm, Paris, France
- MR Author ID: 1287028
- Email: ivailo.hartarsky@ens.fr
- Robert Morris
- Affiliation: IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, Brazil
- MR Author ID: 777846
- Email: rob@impa.br
- Received by editor(s): July 2, 2018
- Received by editor(s) in revised form: January 14, 2019
- Published electronically: August 1, 2019
- Additional Notes: Both authors were partially supported by ERC Starting Grant 680275 MALIG
The research of the second author was also partially supported by CNPq (Proc. 303275/2013-8), by FAPERJ (Proc. 201.598/2014), and by JSPS - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 372 (2019), 6465-6505
- MSC (2010): Primary 60C05; Secondary 60K35, 82B20
- DOI: https://doi.org/10.1090/tran/7828
- MathSciNet review: 4024528