{
  "id": "1909.04649",
  "version": "v1",
  "published": "2019-09-10T17:49:09.000Z",
  "updated": "2019-09-10T17:49:09.000Z",
  "title": "Bootstrap percolation in Ore-type graphs",
  "authors": [
    "Alexandra Wesolek"
  ],
  "comment": "26 pages, 5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The $r$-neighbour bootstrap process describes an infection process on a graph, where we start with a set of initially infected vertices and an uninfected vertex becomes infected as soon as it has $r$ infected neighbours. An inital set of infected vertices is called percolating if at the end of the bootstrap process all vertices are infected. We give Ore-type conditions that guarantee the existence of a small percolating set of size $l\\leq 2r-2$ if the number of vertices $n$ of our graph is sufficiently large: if $l\\geq r$ and satisfies $2r \\geq l+2 \\lfloor \\sqrt{2(l-r)+0.25}+2.5 \\rfloor-1$ then there exists a percolating set of size $l$ for every graph in which any two non-adjacent vertices $x$ and $y$ satisfy $deg(x)+deg(y) \\geq n+4r-2l-2\\lfloor\\sqrt{2(l-r)+0.25}+2.5 \\rfloor-1$ and if $l$ is larger with $l\\leq 2r-2$ there exists a percolating set of size $l$ if $deg(x)+deg(y) \\geq n+2r-l-2$. Our results extend the work of Gunderson, who showed that a graph with minimum degree $\\lfloor n/2 \\rfloor+r-3$ has a percolating set of size $r \\geq 4$. We also give bounds for arbitrarily large $l$ in the minimum degree setting.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-09-10T17:49:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C99",
      "G.2.2"
    ],
    "keywords": [
      "bootstrap percolation",
      "ore-type graphs",
      "percolating set",
      "minimum degree",
      "neighbour bootstrap process"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}