## Combinatorics, Probability and Computing

### Bootstrap Percolation in High Dimensions

a1 Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL 61801 and Department of Mathematics, University of California, San Diego, La Jolla, CA 92093 (e-mail: jobal@math.uiuc.edu)

a2 Trinity College, Cambridge CB2 1TQ, England and Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA (e-mail: B.Bollobas@dpmms.cam.ac.uk)

a3 IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil (e-mail: rob@impa.br)

Abstract

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices AV(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]d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t → ∞. The main question is to determine the critical probability pc([n]d, 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]d when d is a fixed constant and 2 ⩽ rd, and in these cases pc([n]d, r) has recently been determined up to a factor of 1 + o(1) as n → ∞. At the other end of the scale, Balogh and Bollobás determined pc([2]d, 2) up to a constant factor, and Balogh, Bollobás and Morris determined pc([n]d, 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

so λ ≈ 1.166. Then

if d is sufficiently large, and moreover

as d → ∞, for every function n = n(d) with d ≫ log n.