Paper detail

Bootstrap percolation on the Hamming torus

The Hamming torus of dimension $d$ is the graph with vertices $\{1,\dots,n\}^d$ and an edge between any two vertices that differ in a single coordinate. Bootstrap percolation with threshold $θ$ starts with a random set of open vertices, to which every vertex belongs independently with probability $p$, and at each time step the open set grows by adjoining every vertex with at least $θ$ open neighbors. We assume that $n$ is large and that $p$ scales as $n^{-α}$ for some $α>1$, and study the probability that an $i$-dimensional subgraph ever becomes open. For large $θ$, we prove that the critical exponent $α$ is about $1+d/θ$ for $i=1$, and about $1+2/θ+Θ(θ^{-3/2})$ for $i\ge2$. Our small $θ$ results are mostly limited to $d=3$, where we identify the critical $α$ in many cases and, when $θ=3$, compute exactly the critical probability that the entire graph is eventually open.