{
  "id": "1010.3326",
  "version": "v2",
  "published": "2010-10-16T06:22:53.000Z",
  "updated": "2011-02-24T03:12:16.000Z",
  "title": "The sharp threshold for bootstrap percolation in all dimensions",
  "authors": [
    "József Balogh",
    "Béla Bollobás",
    "Hugo Duminil-Copin",
    "Robert Morris"
  ],
  "comment": "37 pages, sketch of the proof added, to appear in Trans. of the AMS",
  "categories": [
    "math.PR",
    "math-ph",
    "math.CO",
    "math.DS",
    "math.MP"
  ],
  "abstract": "In r-neighbour bootstrap percolation on a graph G, a (typically random) set A of initially 'infected' vertices spreads by infecting (at each time step) vertices with at least r already-infected neighbours. This process may be viewed as a monotone version of the Glauber dynamics of the Ising model, and has been extensively studied on the d-dimensional grid $[n]^d$. The elements of the set A are usually chosen independently, with some density p, and the main question is to determine $p_c([n]^d,r)$, the density at which percolation (infection of the entire vertex set) becomes likely. In this paper we prove, for every pair $d \\ge r \\ge 2$, that there is a constant L(d,r) such that $p_c([n]^d,r) = [(L(d,r) + o(1)) / log_(r-1) (n)]^{d-r+1}$ as $n \\to \\infty$, where $log_r$ denotes an r-times iterated logarithm. We thus prove the existence of a sharp threshold for percolation in any (fixed) number of dimensions. Moreover, we determine L(d,r) for every pair (d,r).",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-02-24T03:12:16.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "60C05"
    ],
    "keywords": [
      "sharp threshold",
      "dimensions",
      "r-neighbour bootstrap percolation",
      "entire vertex set",
      "vertices spreads"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1010.3326B"
    }
  }
}