Bootstrap percolation on the Hamming torus
Skip to main content
eScholarship
Open Access Publications from the University of California

Bootstrap percolation on the Hamming torus

  • Author(s): Gravner, Janko
  • Hoffman, Christopher
  • Pfeiffer, James
  • Sivakoff, David
  • et al.

Published Web Location

https://arxiv.org/pdf/1202.5351.pdf
No data is associated with this publication.
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\ge2$. 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.

Item not freely available? Link broken?
Report a problem accessing this item