Bootstrap percolation is a class of cellular‑automaton models used in statistical physics, probability theory, and combinatorics to study the spread of activity (often called “infection” or “occupation”) on a lattice or graph under deterministic local rules. The process is defined by an initial random set of occupied sites and a deterministic updating rule that adds new occupied sites whenever a site has at least a specified number $k$ of occupied neighbors. Once a site becomes occupied it remains so forever; the dynamics therefore “bootstrap” from the initial configuration.
Formal definition
- Underlying structure: Typically a regular lattice $\mathbb{Z}^d$ or a finite graph $G=(V,E)$.
- Parameter $k$: A positive integer called the threshold.
- Initial state: Each vertex is independently occupied with probability $p$ (Bernoulli‑$p$ product measure) or an arbitrary deterministic set $A_0\subseteq V$.
- Update rule: For discrete time steps $t=0,1,2,\dots$, define the occupied set recursively: $$ A_{t+1}=A_t;\cup;{v\in V\setminus A_t : |{u\in N(v):u\in A_t}|\ge k}, $$ where $N(v)$ denotes the set of neighbors of $v$. The process stops when $A_{t+1}=A_t$; the final set is denoted $A_\infty$.
The model is called $k$-bootstrap percolation; the case $k=2$ on $\mathbb{Z}^2$ is the historically first and most studied variant.
Historical background
Bootstrap percolation was introduced in 1979 by J. Chalupa, P. L. Leath, and G. R. Reich in the paper “Bootstrap percolation on a Bethe lattice” (J. Phys. C: Solid State Phys. 12, 1979). Their work motivated subsequent rigorous and non‑rigorous studies of threshold dynamics on lattices, random graphs, and hypercubes.
Key results
- Critical probability $p_c$: For infinite lattices, there exists a sharp threshold $p_c(d,k)$ such that for $p>p_c$ the occupied set eventually fills the entire lattice (percolates) with probability 1, whereas for $p<p_c$ it remains finite with probability 1. On $\mathbb{Z}^2$ with $k=2$, $p_c$ scales as $\Theta(1/\log n)$ for an $n\times n$ box.
- Finite‑size scaling: For a box of side length $L$, the probability of complete occupation transitions rapidly from near 0 to near 1 as $p$ passes a window of width $O(1/(\log L)^2)$ (Aizenman–Lebowitz, 1988).
- Higher dimensions: In $\mathbb{Z}^d$ with threshold $k\ge 2$, the critical probability decays as a power of $1/\log L$ for $k\le d$ and as a power of $L^{-(d-k+1)}$ for $k>d$.
- Random graphs: On Erdős–Rényi $G(n,p)$ and on regular random graphs, bootstrap percolation exhibits a discontinuous “explosive” transition when the initial density crosses a certain value (Pittel, Spencer, Wormald, 1996).
- Metastability: For subcritical initial densities, the time to reach the final configuration can be exponentially large in the system size, a phenomenon studied in the context of metastable states.
Variants and extensions
- Modified bootstrap percolation: Rules may depend on anisotropic neighborhoods, long‑range connections, or stochastic activation (probabilistic thresholds).
- Kinetic constraints models: Bootstrap percolation is a special case of kinetically constrained models (KCMs) used to describe glassy dynamics.
- Bootstrap percolation on hypercubes: Exact thresholds are known for the hypercube $Q_n$ (Balogh, Bollobás, Morris, 2012).
- Cooperative percolation: Some versions allow de‑occupation under certain conditions, leading to reversible dynamics.
Applications
- Statistical physics: Modeling nucleation and growth phenomena, magnetic systems with blocked spins, and glass transition dynamics.
- Epidemiology and social dynamics: Capturing “threshold” adoption behavior where an individual adopts a behavior only after enough neighbors have done so.
- Computer science: Analyzing fault tolerance in networks, spread of information, and bootstrap percolation based algorithms for graph exploration.
- Mathematics: Providing test cases for techniques in percolation theory, cellular automata, and probabilistic combinatorics.
Notable references
- J. Chalupa, P. L. Leath, G. R. Reich, Bootstrap percolation on a Bethe lattice, J. Phys. C 12 (1979) 571–578.
- M. Aizenman, J. Lebowitz, Metastability and nucleation for a stochastic dynamics of Ising spins at very low temperature, Comm. Math. Phys. 121 (1989) 579–595.
- J. Pittel, J. Spencer, N. Wormald, Sudden emergence of a giant k‑core in a random graph, J. Comb. Theory B 67 (1996) 111–151.
- B. Balogh, B. Bollobás, R. Morris, Bootstrap percolation in high dimensions, Probab. Theory Relat. Fields 156 (2013) 51–84.
Bootstrap percolation remains an active research area, with ongoing work on precise critical thresholds, dynamical universality classes, and connections to other models of constrained dynamics.
