Papers › Bootstrap percolation is local
Bootstrap percolation is local
Ivailo Hartarsky, Augusto Teixeira
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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\"ose, upper bounds are sharp to essentially arbitrary precision, by linking them to their local counterparts. In Frob\"ose bootstrap percolation, iteratively, any vertex of the square lattice that is the only healthy vertex of a 1×1 square becomes infected and infections never heal. We prove that if vertices are initially infected independently with probability p→0, then with high probability the origin becomes infected after exp(π²/6p-(π√(2+√(2)))/(√(p))+(O(log²(1/p)))/(√(p))) time steps. We achieve this by proposing a new paradigmatic view on bootstrap percolation based on locality. Namely, we show that studying the Frob\"ose 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections