On the maximum running time in graph bootstrap percolation

Graph bootstrap percolation is a simple cellular automaton introduced by Bollobás in 1968. Given a graph H and a set G⊆E(K_n) we initially `infect' all edges in G and then, in consecutive steps, we infect every e∈K_n that completes a new infected copy of H in K_n. We say that G percolates if eventually every edge in K_n is infected. The extremal question about the size of the smallest percolating sets when H=K_r 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 ⌈log₂(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 K_r-bootstrap process can run for at least n^2−εr time steps for some ε_r that tends to 0 as r→∞.