The time of graph bootstrap percolation

K. Gunderson, S. Koch, M. Przykucki

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

Graph bootstrap percolation, introduced by Bollobás in 1968, is a cellular automaton defined as follows. Given a "small" graph H and a "large" graph G=G0⊆Kn, in consecutive steps we obtain Gt+1 from Gt by adding to it all new edges e such that Gt∪e contains a new copy of H. We say that G percolates if for some t≥0, we have Gt=Kn.

For H=Kr, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollobás and Morris considered graph bootstrap percolation for G=G(n,p) and studied the critical probability pc(n,Kr), 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≤t≤C log log n.
Original languageEnglish
Pages (from-to)143-168
Number of pages26
JournalRandom Structures and Algorithms
Volume51
Issue number1
Early online date26 Aug 2016
DOIs
Publication statusPublished - 2017

Keywords

  • bootstrap percolation
  • weak saturation
  • random graphs

Fingerprint

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

Cite this