On the maximum running time in graph bootstrap percolation

B. Bollobás, M. Przykucki, O. Riordan, J. Sahasrabudhe

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Graph bootstrap percolation is a simple cellular automaton introduced by Bollobás in 1968. Given a graph H and a set GE(Kn) we initially `infect' all edges in G and then, in consecutive steps, we infect every eKn that completes a new infected copy of H in Kn. We say that G percolates if eventually every edge in Kn is infected. The extremal question about the size of the smallest percolating sets when H=Kr was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollobás: what is the maximum time the process can run before it stabilizes? It is an easy observation that for r=3 this maximum is ⌈log2(n1)⌉. However, a new phenomenon occurs for r=4 when, as we show, the maximum time of the process is n3. For r5 the behaviour of the dynamics is even more complex, which we demonstrate by showing that the Kr-bootstrap process can run for at least n2−εr time steps for some εr that tends to 0 as r.
Original languageEnglish
Article numberP2.16
Number of pages20
JournalElectronic Journal of Combinatorics
Issue number2
Publication statusPublished - 5 May 2017


  • Bootstrap percolation
  • Weak saturation
  • Cellular automata
  • Monotone cellular automata
  • Extremal combinatorics


Dive into the research topics of 'On the maximum running time in graph bootstrap percolation'. Together they form a unique fingerprint.

Cite this