Bootstrap percolation on the Hamming torus

Abstract

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 $\theta$ 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 $\theta$ open neighbors. We assume that $n$ is large and that $p$ scales as $n^{-\alpha }$ for some $\alpha >1$, and study the probability that an $i$-dimensional subgraph ever becomes open. For large $\theta$, we prove that the critical exponent $\alpha$ is about $1+d/\theta$ for $i=1$, and about $1+2/\theta +\Theta ({\theta }^{-3/2})$ for $i\ge 2$. Our small $\theta$ results are mostly limited to $d=3$, where we identify the critical $\alpha$ in many cases and, when $\theta =3$, compute exactly the critical probability that the entire graph is eventually open.

Published in at http://dx.doi.org/10.1214/13-AAP996 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)