Combinatorics, Probability and Computing

Paper

Bootstrap Percolation in High Dimensions

JÓZSEF BALOGHa1, BÉLA BOLLOBÁSa2 and ROBERT MORRISa3§

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

\[\sum_{k=0}^\infty \frac{(-1)^k \lambda^k}{2^{k^2-k} k!} = 0,\]

so λ ≈ 1.166. Then
\[ \frac{16\lambda}{d^2} \biggl(1 + \frac{\log d}{\sqrt{d}} \biggr)\: 2^{-2\sqrt{d}} \leq p_c([2]^d,2) \leq \frac{16\lambda}{d^2} \biggl(1 + \frac{5(\log d)^2}{\sqrt{d}} \biggr) \: 2^{-2\sqrt{d}}\]

if d is sufficiently large, and moreover
\[p_c\bigl([n]^d,2 \bigr) = \bigl(4\lambda + o(1) \bigr) \biggl(\frac{n}{n-1} \biggr)^2 \, \frac{1}{d^2} \, 2^{-2\sqrt{d \log_2 n}}\]

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

(Received July 22 2009)

(Revised July 07 2010)

(Online publication August 12 2010)

Footnotes

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.