{
  "id": "1610.04499",
  "version": "v1",
  "published": "2016-10-14T15:24:26.000Z",
  "updated": "2016-10-14T15:24:26.000Z",
  "title": "Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets",
  "authors": [
    "Michael Dairyko",
    "Michael Ferrara",
    "Bernard Lidický",
    "Ryan R. Martin",
    "Florian Pfender",
    "Andrew J. Uzzell"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~$G$ begin in one of two states, \"dormant\" or \"active\". Given a fixed integer $r$, a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$, we say that $G$ $r$-percolates (from $A$) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$-percolates from $A$. Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$. In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $\\sigma_2(G)\\ge n-2$, then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chv\\'{a}tal-type degree condition: If $G$ is a graph with degree sequence $d_1\\le d_2\\le\\dots\\le d_n$ such that $d_i \\geq i+1$ or $d_{n-i} \\geq n-i-1$ for all $1 \\leq i < \\frac{n}{2}$, then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. Combin.]",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-14T15:24:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "bootstrap percolation",
      "chvátal-type degree conditions",
      "small sets",
      "ore-type degree sum result",
      "deterministic cellular automaton"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}