Scientific article
English

The sharp threshold for bootstrap percolation in all dimensions

Published inTransactions of the American Mathematical Society, vol. 364, p. 2667-2701
Publication date2012
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 ge r ge 2$, that there is a constant L(d,r) such that $p_c([n]^d,r) = [(L(d,r) + o(1)) / log_(r-1) (n)]^{d-r+1}$ as $n o infty$, where $log_r$ denotes an r-times iterated logarithm. We thus prove the existence of a sharp threshold for percolation in any (fixed) number of dimensions. Moreover, we determine L(d,r) for every pair (d,r).

Citation (ISO format)
BALOGH, József et al. The sharp threshold for bootstrap percolation in all dimensions. In: Transactions of the American Mathematical Society, 2012, vol. 364, p. 2667–2701. doi: 10.1090/s0002-9947-2011-05552-2
Main files (2)
Article (Submitted version)
accessLevelPublic
Article (Published version)
accessLevelRestrictedaccessLevelPublic 31/12/2040
Identifiers
Journal ISSN0002-9947
699views
1018downloads

Technical informations

Creation20/10/2013 21:12:00
First validation20/10/2013 21:12:00
Update28/10/2026 14:53:08
Status update28/10/2026 14:53:08
Last indexation28/10/2026 14:53:10
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack
Open AIRE Indexed & Validated