{
  "id": "1806.02903",
  "version": "v1",
  "published": "2018-06-07T21:01:54.000Z",
  "updated": "2018-06-07T21:01:54.000Z",
  "title": "A Sharp Threshold for Bootstrap Percolation in a Random Hypergraph",
  "authors": [
    "Natasha Morrison",
    "Jonathan A. Noel"
  ],
  "comment": "89 pages, 14 figures",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Given a hypergraph $\\mathcal{H}$, the $\\mathcal{H}$-bootstrap process starts with an initial set of infected vertices of $\\mathcal{H}$ and, at each step, a healthy vertex $v$ becomes infected if there exists a hyperedge of $\\mathcal{H}$ in which $v$ is the unique healthy vertex. We say that the set of initially infected vertices percolates if every vertex of $\\mathcal{H}$ is eventually infected. We show that this process exhibits a sharp threshold when $\\mathcal{H}$ is a hypergraph obtained by randomly sampling hyperedges from an approximately $d$-regular $r$-uniform hypergraph satisfying some mild degree and codegree conditions; this confirms a conjecture of Morris. As a corollary, we obtain a sharp threshold for a variant of the graph bootstrap process for strictly $2$-balanced graphs which generalises a result of Kor\\'{a}ndi, Peled and Sudakov. Our approach involves an application of the differential equations method.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-07T21:01:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sharp threshold",
      "bootstrap percolation",
      "random hypergraph",
      "unique healthy vertex",
      "bootstrap process starts"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 89,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}