The sharp threshold for bootstrap percolation in all dimensions

Abstract:

In $r$-neighbour bootstrap percolation on a graph $G$, a (typically random) set $A$ of initially ‘infected’ vertices spreads by infecting (at each time step) vertices with at least $r$ already-infected neighbours. This process may be viewed as a monotone version of the Glauber dynamics of the Ising model, and has been extensively studied on the $d$-dimensional grid $[n]^d$. The elements of the set $A$ are usually chosen independently, with some density $p$, and the main question is to determine $p_c([n]^d,r)$, the density at which percolation (infection of the entire vertex set) becomes likely.

In this paper we prove, for every pair $d,r \in \mathbb {N}$ with $d \geqslant r \geqslant 2$, that \[ p_c\big ( [n]^d,r \big ) = \left ( \frac {\lambda (d,r) + o(1)}{\log _{(r-1)} (n)} \right )^{d-r+1}\] as $n \to \infty$, for some constant $\lambda (d,r) > 0$, and thus prove the existence of a sharp threshold for percolation in any (fixed) number of dimensions. We moreover determine $\lambda (d,r)$ for every $d \geqslant r \geqslant 2$.