{
  "id": "1408.5488",
  "version": "v1",
  "published": "2014-08-23T10:48:49.000Z",
  "updated": "2014-08-23T10:48:49.000Z",
  "title": "Saturation in the Hypercube and Bootstrap Percolation",
  "authors": [
    "Natasha Morrison",
    "Jonathan A. Noel",
    "Alex Scott"
  ],
  "comment": "21 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $Q_d$ denote the hypercube of dimension $d$. Given $d\\geq m$, a spanning subgraph $G$ of $Q_d$ is said to be $(Q_d,Q_m)$-saturated if it does not contain $Q_m$ as a subgraph but adding any edge of $E(Q_d)\\setminus E(G)$ creates a copy of $Q_m$ in $G$. Answering a question of Johnson and Pinto, we show that for every fixed $m\\geq2$ the minimum number of edges in a $(Q_d,Q_m)$-saturated graph is $\\Theta(2^d)$. We also study weak saturation, which is a form of bootstrap percolation. Given graphs $F$ and $H$, a spanning subgraph $G$ of $F$ is said to be weakly $(F,H)$-saturated if the edges of $E(F)\\setminus E(G)$ can be added to $G$ one at a time so that each additional edge creates a new copy of $H$. Answering another question of Johnson and Pinto, we determine the minimum number of edges in a weakly $(Q_d,Q_m)$-saturated graph for all $d\\geq m\\geq1$. More generally, we determine the minimum number of edges in a subgraph of the $d$-dimensional grid $P_k^d$ which is weakly saturated with respect to `axis aligned' copies of a smaller grid $P_r^m$. We also study weak saturation of cycles in the grid.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-23T10:48:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bootstrap percolation",
      "minimum number",
      "study weak saturation",
      "additional edge creates",
      "spanning subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.5488M"
    }
  }
}