{
  "id": "1503.01454",
  "version": "v1",
  "published": "2015-03-04T20:52:41.000Z",
  "updated": "2015-03-04T20:52:41.000Z",
  "title": "The time of graph bootstrap percolation",
  "authors": [
    "Karen Gunderson",
    "Sebastian Koch",
    "Michał Przykucki"
  ],
  "comment": "18 pages, 3 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Graph bootstrap percolation, introduced by Bollob\\'as in 1968, is a cellular automaton defined as follows. Given a \"small\" graph $H$ and a \"large\" graph $G = G_0 \\subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \\cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \\geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the smallest size of percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollob\\'as and Morris considered graph bootstrap percolation for $G = G(n,p)$ and studied the critical probability $p_c(n,K_r)$ for the event that the graph percolates with high probability. In this paper, using the same setup, we determine up to a logarithmic factor the critical probability for percolation by time $t$ for all $1 \\leq t \\leq C \\log\\log n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-03-04T20:52:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05",
      "05C80",
      "60K35",
      "60C05"
    ],
    "keywords": [
      "graph bootstrap percolation",
      "critical probability",
      "logarithmic factor",
      "graph percolates",
      "high probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150301454G"
    }
  }
}