Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The sharp threshold for bootstrap percolation in all dimensions

Authors: József Balogh, Béla Bollobás, Hugo Duminil-Copin and Robert Morris
Journal: Trans. Amer. Math. Soc. 364 (2012), 2667-2701
MSC (2010): Primary 60K35, 60C05
Published electronically: December 7, 2011
MathSciNet review: 2888224
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ p_c([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 \in \mathbb{N}$ with $ d \ge r \ge 2$, that

$\displaystyle p_c\big ( [n]^d,r \big ) = \left ( \frac {\lambda (d,r) + o(1)}{\log _{(r-1)} (n)} \right )^{d-r+1}$

as $ n \to \infty $, for some constant $ \lambda (d,r) > 0$, and thus prove the existence of a sharp threshold for percolation in any (fixed) number of dimensions. We moreover determine $ \lambda (d,r)$ for every $ d \ge r \ge 2$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60K35, 60C05

Retrieve articles in all journals with MSC (2010): 60K35, 60C05

Additional Information

József Balogh
Affiliation: Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, Illinois 61801 – and – Department of Mathematics, University of California, San Diego, La Jolla, California 92093

Béla Bollobás
Affiliation: Department of Mathematics, Trinity College, Cambridge CB2 1TQ, England – and – Department of Mathematical Sciences, The University of Memphis, Memphis, Tennessee 38152

Hugo Duminil-Copin
Affiliation: Département de Mathématiques, Université de Genève, 2-4 rue du Lièvre, 1211 Genvève, Suisse

Robert Morris
Affiliation: IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil

Keywords: Bootstrap percolation, sharp threshold
Received by editor(s): October 15, 2010
Published electronically: December 7, 2011
Additional Notes: The first author was supported by NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grants 09072 and 08086, and OTKA Grant K76099.
The second author was supported by NSF grants CNS-0721983, CCF-0728928 and DMS-0906634, and ARO grant W911NF-06-1-0076.
The third author was supported by ANR grant BLAN-3-134462 and the Swiss NSF
The fourth author was supported by MCT grant PCI EV-8C, ERC Advanced grant DMMCA, and a Research Fellowship from Murray Edwards College, Cambridge
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.