Bootstrap percolation in high dimensions

Original · EN

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A ⊂ V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]ᵈ, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t -> infinity. The main question is to determine the critical probability pc([n]ᵈ,r) at which percolation becomes likely, and to give bounds on the size of the critical window. In this paper we study this problem when r = 2, for all functions n and d satisfying d ≫ log n. The bootstrap process has been extensively studied on [n]ᵈ when d is a fixed constant and 2 ≤ r ≤ d, and in these cases pc([n]ᵈ,r) has recently been determined up to a factor of 1 + o(1) as n -> infinity. At the other end of the scale, Balogh and Bollobas determined pc([2]ᵈ,2) up to a constant factor, and Balogh, Bollobas and Morris determined pc([n]ᵈ,d) asymptotically if d > (log log n)2+, and gave much sharper bounds for the hypercube. Here we prove the following result: let λbe the smallest positive root of the equation ∑ₖ₌₀∞ (-1)ᵏ λᵏ / (2ᵏ²⁻ᵏ k!) = 0, so λ≈ 1.166. Then (16λ/ d²) (1 + (log d / √d)) 2-2√d < pc([2]ᵈ,2) < (16λ/ d²) (1 + (5(log d)² / √d)) 2-2√d if d is sufficiently large, and moreover we determine a sharp threshold for the critical probability pc([n]ᵈ,2) for every function n = n(d) with d ≫ log n.