The sharp threshold for bootstrap percolation in all dimensions

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\ge r\ge 2$, that there is a constant L(d,r) such that $p_c([n]^d,r) = [(L(d,r) + o(1)) / log_(r-1) (n)]^{d-r+1}$as$n \to \infty$,where$log_r$ denotes an r-times iterated logarithm. We thus prove the existence of a sharp threshold for percolation in any (fixed) number of dimensions. Moreover, we determine L(d,r) for every pair (d,r).