2010/10/16 by Balogh, József, Bollobás, Béla, Duminil-Copin, Hugo +1 · 4 citations
#60C05 #60K35 #Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR)
paper · doi:10.48550/arxiv.1010.3326
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 pc([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 ≥ 2, that there is a constant L(d,r) such that pc([n]d,r) = [(L(d,r) + o(1)) / log_(r-1) (n)]d-r+1 as n → ∞, where logr 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).