{
  "id": "1204.3190",
  "version": "v2",
  "published": "2012-04-14T17:54:40.000Z",
  "updated": "2018-06-22T19:33:38.000Z",
  "title": "An Improved Upper Bound for Bootstrap Percolation in All Dimensions",
  "authors": [
    "Andrew J. Uzzell"
  ],
  "comment": "30 pages, 3 figures. Substantially revised",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "In $r$-neighbor bootstrap percolation on the vertex set of a graph $G$, a set $A$ of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least $r$ previously infected neighbors. When the elements of $A$ are chosen independently with some probability $p$, it is natural to study the critical probability $p_c(G,r)$ at which it becomes likely that all of $V(G)$ will eventually become infected. Improving a result of Balogh, Bollob\\'as, and Morris, we give a bound on the second term in the expansion of the critical probability when $G = [n]^d$ and $d \\geq r \\geq 2$. We show that for all $d \\geq r \\geq 2$ there exists a constant $c_{d,r} > 0$ such that if $n$ is sufficiently large, then \\[ p_c([n]^d, r) \\leq \\Biggl(\\dfrac{\\lambda(d,r)}{\\log_{(r-1)}(n)} - \\dfrac{c_{d,r}}{\\bigl(\\log_{(r-1)}(n)\\bigr)^{3/2}}\\Biggr)^{d-r+1}, \\] where $\\lambda(d,r)$ is an exact constant and $\\log_{(k)}(n)$ denotes the $k$-times iterated natural logarithm of $n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-04-14T17:54:40.000Z",
      "abstract": "In $r$-neighbor bootstrap percolation on the vertex set of a graph $G$, a set $A$ of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least $r$ previously infected neighbors. When the elements of $A$ are chosen independently with some probability $p$, it is interesting to determine the critical probability $p_c(G,r)$ at which it becomes likely that all of $V(G)$ will eventually become infected. Improving a result of Balogh, Bollob\\'as, and Morris, we give a second term in the expansion of the critical probability when $G = [n]^d$ and $d \\geq r \\geq 2$. We show that there exists a constant $c > 0$ such that for all $d \\geq r \\geq 2$, \\[p_c([n]^d, r) \\leq (\\dfrac{\\lambda(d,r)}{\\log_{(r-1)}(n)} - \\dfrac{c}{(\\log_{(r-1)}(n))^{2 - 1/(2d - 2)}})^{d-r+1}\\] as $n \\to \\infty$, where $\\lambda(d,r)$ is an exact constant and $\\log_{(k)}(n)$ denotes the $k$-times iterated logarithm of $n$.",
      "comment": "19 pages, 2 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2018-06-22T19:33:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "60C05"
    ],
    "keywords": [
      "upper bound",
      "dimensions",
      "neighbor bootstrap percolation",
      "critical probability",
      "initially infected vertices spreads"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1204.3190U"
    }
  }
}