On the maximum running time in graph bootstrap percolation

Graph bootstrap percolation is a simple cellular automaton introduced by Bollob´as in 1968. Given a graph H and a set G ⊆ E(Kn) we initially “infect” all edges in G and then, in consecutive steps, we infect every e ∈ Kn 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´as: 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 (n − 1)⌉. However, a new phenomenon occurs for r = 4 when, as we show, the maximum time of the process is n − 3. For r > 5 the behaviour of the dynamics is even more complex, which we demonstrate by showing that the Kr-bootstrap process can run for at least n 2−εr time steps for some εr that tends to 0 as r → ∞