Bootstrap percolation in three dimensions

Abstract

By bootstrap percolation we mean the following deterministic process on a graph $G$. Given a set $A$ of vertices "infected" at time 0, new vertices are subsequently infected, at each time step, if they have at least $r\in \mathbb{N}$ previously infected neighbors. When the set $A$ is chosen at random, the main aim is to determine the critical probability $p_c(G,r)$ at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the $d$-dimensional grid $[n{]}^d$: with $2\le r\le d$ fixed, it was proved by Cerf and Cirillo (for $d=r=3$), and by Cerf and Manzo (in general), that \[p_c([n]^d,r)=Θ\biggl(\frac{1}{\log_{(r-1)}n}\biggr)^{d-r+1},\] where ${\log }_{(r)}$ is an $r$-times iterated logarithm. However, the exact threshold function is only known in the case $d=r=2$, where it was shown by Holroyd to be $(1+o(1))\frac{{\pi }^2}{18\log n}$. In this paper we shall determine the exact threshold in the crucial case $d=r=3$, and lay the groundwork for solving the problem for all fixed $d$ and $r$.

Published in at http://dx.doi.org/10.1214/08-AOP433 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Bootstrap percolation in three dimensions

Cited by in corpus (29)

• Bootstrap percolation on the random graph $G_{n,p}$
• Bootstrap percolation in three dimensions
• Monotone cellular automata in a random environment
• Bootstrap percolation in inhomogeneous random graphs
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• The second term for two-neighbour bootstrap percolation in two dimensions
• Sharp threshold for the FA-2f kinetically constrained model
• Metastability threshold for anisotropic bootstrap percolation in three dimensions
• $\mathcal{U}$-bootstrap percolation: critical probability, exponential decay and applications
• Thresholds for contagious sets in random graphs
• Zero-temperature Glauber dynamics on Z^d
• Bootstrap percolation on the Hamming torus
• The time of bootstrap percolation for dense initial sets
• Bootstrap and diffusion percolation transitions in three-dimensional lattices
• A sharp threshold for a modified bootstrap percolation with recovery
• An Improved Upper Bound for Bootstrap Percolation in All Dimensions
• The time of bootstrap percolation with dense initial sets for all thresholds
• The time of bootstrap percolation in two dimensions
• The Saturation Time of Graph Bootstrap Percolation
• Noise sensitivity in bootstrap percolation
• Subcritical $\mathcal{U}$-bootstrap percolation models have non-trivial phase transitions
• Evidence for bootstrap percolation dynamics in a photo-induced phase transition
• A sharper threshold for bootstrap percolation in two dimensions
• A simple proof of almost percolation on G(n;p)
• A Note on Bootstrap Percolation Thresholds in Plane Tilings using Regular Polygons
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results
• Strict majority bootstrap percolation in the r-wheel
• Bootstrap percolation in power-law random graphs
• Errata and Addenda to Mathematical Constants