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 :I 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 4-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 is an element of N with d >= r >= 2, that p(c)([n](d), r) = (lambda(d, r) + o(1)/log((r-1))(n))(d-r+1) as n -> infinity, 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 >= r >= 2.