{
  "id": "0806.4485",
  "version": "v2",
  "published": "2008-06-27T11:00:54.000Z",
  "updated": "2009-08-31T06:42:26.000Z",
  "title": "Bootstrap percolation in three dimensions",
  "authors": [
    "József Balogh",
    "Béla Bollobás",
    "Robert Morris"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/08-AOP433 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Probability 2009, Vol. 37, No. 4, 1329-1380",
  "doi": "10.1214/08-AOP433",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "By bootstrap percolation we mean the following deterministic process on a graph $G$. Given a set $A$ of vertices \"infected\" at time 0, new vertices are subsequently infected, at each time step, if they have at least $r\\in\\mathbb{N}$ previously infected neighbors. When the set $A$ is chosen at random, the main aim is to determine the critical probability $p_c(G,r)$ at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the $d$-dimensional grid $[n]^d$: with $2\\leq r\\leq d$ fixed, it was proved by Cerf and Cirillo (for $d=r=3$), and by Cerf and Manzo (in general), that \\[p_c([n]^d,r)=\\Theta\\biggl(\\frac{1}{\\log_{(r-1)}n}\\biggr)^{d-r+1},\\] where $\\log_{(r)}$ is an $r$-times iterated logarithm. However, the exact threshold function is only known in the case $d=r=2$, where it was shown by Holroyd to be $(1+o(1))\\frac{\\pi^2}{18\\log n}$. In this paper we shall determine the exact threshold in the crucial case $d=r=3$, and lay the groundwork for solving the problem for all fixed $d$ and $r$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2009-08-31T06:42:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "60C05"
    ],
    "keywords": [
      "bootstrap percolation",
      "dimensions",
      "exact threshold function",
      "entire graph",
      "time step"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0806.4485B"
    }
  }
}