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: firstname.lastname@example.org)
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: email@example.com)
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]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 ⩽ r ⩽ d, 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(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
(Received July 22 2009)
(Revised July 07 2010)
(Online publication August 12 2010)
† Supported by NSF CAREER Grant DMS-0745185 and DMS-0600303, UIUC Campus Research Board Grants 09072 and 08086, and OTKA Grant K76099.
‡ Supported by ARO grant W911NF-06-1-0076, and and NSF grants CNS-0721983, CCF-0728928 and DMS-0906634.
§ Supported by MCT grant PCI EV-8C, ERC Advanced grant DMMCA, and a Research Fellowship from Murray Edwards College, Cambridge.