Subcritical bootstrap percolation via Toom contours. (English) Zbl 1515.60313

Summary: In this note we provide an alternative proof of the fact that subcritical bootstrap percolation models have a positive critical probability in any dimension. The proof relies on a recent extension of the classical framework of Toom. This approach is not only simpler than the original multi-scale renormalisation proof of the result in two and more dimensions, but also gives significantly better bounds. As a byproduct, we improve the best known bounds for the stability threshold of Toom’s North-East-Center majority rule cellular automaton.


60K35 Interacting random processes; statistical mechanics type models; percolation theory
60C05 Combinatorial probability
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
Full Text: DOI arXiv


[1] P. Balister, B. Bollobás, R. Morris, and P. Smith, The critical length for growing a droplet, arXiv e-prints (2022).
[2] P. Balister, B. Bollobás, R. Morris, and P. Smith, Subcritical monotone cellular automata, arXiv e-prints (2022).
[3] P. Balister, B. Bollobás, R. Morris, and P. Smith, Universality for monotone cellular automata, arXiv e-prints (2022).
[4] P. Balister, B. Bollobás, M. Przykucki, and P. Smith, \[ Subcritical \mathcal{U} \]-bootstrap percolation models have non-trivial phase transitions, Trans. Amer. Math. Soc. 368 (2016), no. 10, 7385-7411. · Zbl 1342.60159
[5] S. Banerjee, M. Jenamani, and D. K. Pratihar, A survey on influence maximization in a social network, Knowl. Inf. Syst. 62 (2020), no. 9, 3417-3455.
[6] P. Berman and J. Simon, Investigations of fault-tolerant networks of computers, Proc. Twent. Annu. ACM Symp. Theory Comput. (Chicago, Illinois), STOC ‘88, Association for Computing Machinery, New York, NY, 1988, pp. 66-77.
[7] B. Bollobás, H. Duminil-Copin, R. Morris, and P. Smith, Universality of two-dimensional critical cellular automata, Proc. Lond. Math. Soc. (To appear).
[8] B. Bollobás, P. Smith, and A. Uzzell, Monotone cellular automata in a random environment, Combin. Probab. Comput. 24 (2015), no. 4, 687-722. · Zbl 1371.60170
[9] M. Bramson and L. Gray, A useful renormalization argument, Random walks, Brownian motion, and interacting particle systems, Progr. Probab., vol. 28, Birkhäuser, Boston, MA, 1991, pp. 113-152. · Zbl 0745.60103
[10] J. Chalupa, P. L. Leath, and G. R. Reich, Bootstrap percolation on a Bethe lattice, J. Phys. C 12 (1979), no. 1, L31-L35.
[11] R. Durrett, Oriented percolation in two dimensions, Ann. Probab. 12 (1984), no. 4, 999-1040. · Zbl 0567.60095
[12] P. Gács, A new version of Toom’s proof, Tech. report, Computer Science Department, Boston University, 1995, Technical Report BUCS-1995-009 available at https://open.bu.edu/handle/2144/1570.
[13] P. Gács, A new version of Toom’s proof, arXiv e-prints (2021).
[14] P. Gács and J. Reif, A simple three-dimensional real-time reliable cellular array, J. Comput. Syst. Sci. 36 (1988), no. 2, 125-147. · Zbl 0646.68072
[15] L. Gray, J. 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. · Zbl 0464.60098
[16] I. Hartarsky, \[ \mathcal{U} \]-bootstrap percolation: critical probability, exponential decay and applications, Ann. Inst. Henri Poincaré Probab. Stat. 57 (2021), no. 3, 1255-1280. · Zbl 1480.60292
[17] I. Hartarsky, Refined universality for critical KCM: upper bounds, arXiv e-prints (2021).
[18] I. Hartarsky, Bootstrap percolation, probabilistic cellular automata and sharpness, J. Stat. Phys. 187 (2022), no. 3, Article No. 21, 17. · Zbl 1492.60276
[19] R. Morris, Bootstrap percolation, and other automata, European J. Combin. 66 (2017), 250-263. · Zbl 1376.82090
[20] R. H. Schonmann, Critical points of two-dimensional bootstrap percolation-like cellular automata, J. Stat. Phys. 58 (1990), no. 5-6, 1239-1244. · Zbl 0712.68071
[21] R. H. Schonmann, On the behavior of some cellular automata related to bootstrap percolation, Ann. Probab. 20 (1992), no. 1, 174-193. · Zbl 0742.60109
[22] J. M. Swart, R. Szabó, and C. Toninelli, Peierls bounds from Toom contours, arXiv e-prints (2022).
[23] A. L. Toom, Nonergodic multidimensional systems of automata, Probl. Peredači Inf. 10 (1974), no. 3, 70-79. · Zbl 0315.94053
[24] A. L. Toom, Stable and attractive trajectories in multicomponent systems, Multicomponent random systems, Adv. Probab. Related topics, vol. 6, Dekker, New York, 1980, pp. 549-575. · Zbl 0441.68053
[25] N. B. Vasil’ev, M. B. Petrovskaya, and I. I. Pyatetskij-Shapiro, Modelling of voting with random error, Autom. Remote Control 10 (1969), 1639-1642. · Zbl 0205.17803
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.