{
  "id": "1107.1410",
  "version": "v2",
  "published": "2011-07-07T14:48:24.000Z",
  "updated": "2012-02-25T23:00:14.000Z",
  "title": "Linear algebra and bootstrap percolation",
  "authors": [
    "József Balogh",
    "Béla Bollobás",
    "Robert Morris",
    "Oliver Riordan"
  ],
  "comment": "10 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In $\\HH$-bootstrap percolation, a set $A \\subset V(\\HH)$ of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph $\\HH$. A particular case of this is the $H$-bootstrap process, in which $\\HH$ encodes copies of $H$ in a graph $G$. We find the minimum size of a set $A$ that leads to complete infection when $G$ and $H$ are powers of complete graphs and $\\HH$ encodes induced copies of $H$ in $G$. The proof uses linear algebra, a technique that is new in bootstrap percolation, although standard in the study of weakly saturated graphs, which are equivalent to (edge) $H$-bootstrap percolation on a complete graph.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-02-25T23:00:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bootstrap percolation",
      "linear algebra",
      "complete graph",
      "vertices spreads",
      "encodes induced copies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1107.1410B"
    }
  }
}