Bootstrap Percolation in High Dimensions

Rob Morris
University of Cambridge

Let $G$ be a graph, $r$ be an integer, and $A$ be a set of initially `infected' vertices. Bootstrap percolation is the following deterministic
process: at each time step healthy vertices with at least $r$ infected neighbours become infected, and infected vertices remain infected forever.
Suppose the elements of $A$ are chosen independently at random with probability $p$. At what value of $p$ does percolation (infection of the entire vertex set) become likely?

The bootstrap process is closely related to the Ising model, and has been most extensively studied on the grid $[n]^d$ with $d$ fixed. Balogh and Bollob\'as were the first to study the process on the hypercube, with $r = 2$, and determined the critical threshold up to a constant factor. In this talk I will describe how to prove a sharp threshold for percolation on the hypercube, and more generally for the grid $[n]^d$ whenever $d \gg \log n$.

This is joint work with Jozsi Balogh and Bela Bollobas.

Back to Workshop I: Probabilistic Techniques and Applications