{
  "id": "1202.5351",
  "version": "v5",
  "published": "2012-02-24T00:47:02.000Z",
  "updated": "2015-01-23T11:13:50.000Z",
  "title": "Bootstrap percolation on the Hamming torus",
  "authors": [
    "Janko Gravner",
    "Christopher Hoffman",
    "James Pfeiffer",
    "David Sivakoff"
  ],
  "comment": "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)",
  "journal": "Annals of Applied Probability 2015, Vol. 25, No. 1, 287-323",
  "doi": "10.1214/13-AAP996",
  "categories": [
    "math.PR"
  ],
  "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.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2013-11-19T20:36:08.000Z",
      "title": "Bootstrap Percolation on the Hamming Torus",
      "abstract": "The Hamming torus of dimension $d$ is the graph with vertices ${1,..., 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.",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v5",
      "updated": "2015-01-23T11:13:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bootstrap percolation",
      "hamming torus",
      "probability",
      "open set grows",
      "open vertices"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}