Bootstrap percolation is local
Preprint
Abstract
Metastability thresholds lie at the heart of bootstrap percolation theory. Yet proving precise lower bounds is notoriously hard. We show that for two of the most classical models, two-neighbour and Froböse, upper bounds are sharp to essentially arbitrary precision, by linking them to their local counterparts. In Froböse bootstrap percolation, iteratively, any vertex of the square lattice that is the only healthy vertex of a $1\times1$ square becomes infected and infections never heal. We prove that if vertices are initially infected independently with probability $p\to0$, then with high probability the origin becomes infected after \[\exp\left(\frac{π^2}{6p}-\frac{π\sqrt{2+\sqrt2}}{\sqrt p}+\frac{O(\log^2(1/p))}{\sqrt[3]p}\right)\] time steps. We achieve this by proposing a new paradigmatic view on bootstrap percolation based on locality. Namely, we show that studying the Froböse model is equivalent in an extremely strong sense to studying its local version. As a result, we completely bypass Holroyd's classical but technical hierarchy method, yielding the first term above and systematically used throughout bootstrap percolation for the last two decades. Instead, the proof features novel links to large deviation theory, eigenvalue perturbations and others. We also use the locality viewpoint to resolve the so-called bootstrap percolation paradox. Indeed, we propose and implement an exact (deterministic) algorithm which exponentially outperforms previous Monte Carlo approaches. This allows us to clearly showcase and quantify the slow convergence we prove rigorously. The same approach applies, with more extensive computations, to the two-neighbour model, in which vertices are infected when they have at least two infected neighbours and do not recover. We expect it to be applicable to a wider range of models and correspondingly conclude with a number of open problems.
Keywords
All Related Versions
This publication has 65 references indexed in Scilit:
- Sharp threshold for the FA-2f kinetically constrained modelProbability Theory and Related Fields, 2022
- A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphsRandom Structures & Algorithms, 2017
- A sharper threshold for bootstrap percolation in two dimensionsProbability Theory and Related Fields, 2010
- Bootstrap percolation on the hypercubeProbability Theory and Related Fields, 2005
- Sharp metastability threshold for two-dimensional bootstrap percolationProbability Theory and Related Fields, 2003
- Size dependence of self-diffusion in the hard-square lattice gasJournal of Statistical Physics, 1991
- Finite-size effects for some bootstrap percolation modelsJournal of Statistical Physics, 1990
- Finite-size effects in a cellular automaton for diffusionJournal of Statistical Physics, 1989
- Proof of Straley's argument for bootstrap percolationJournal of Statistical Physics, 1987
- Application of percolation theory to 2D‐3D heisenberg ferromagnetsPhysica Status Solidi (b), 1975