The time of graph bootstrap percolation

Karen Gunderson, Sebastian Koch, Michał Przykucki

Research output: Contribution to journalArticle (Academic Journal)

231 Downloads (Pure)

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$.
Original languageEnglish
Number of pages18
JournalarXiv
Publication statusPublished - 4 Mar 2015

Bibliographical note

18 pages, 3 figures

Keywords

  • math.PR
  • math.CO
  • 05C05
  • 05C80
  • 60K35
  • 60C05

Fingerprint Dive into the research topics of 'The time of graph bootstrap percolation'. Together they form a unique fingerprint.

Cite this