Graph bootstrap percolation

Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollobás in 1968, and is defined as follows. Given a graph H, and a set G ⊂ E(K _n) of initially 'infected' edges, we infect, at each time step, a new edge e if there is a copy of H in K _n such that e is the only not-yet infected edge of H. We say that G percolates in the H-bootstrap process if eventually every edge of K _n is infected. The extremal questions for this model, when H is the complete graph K _r, were solved (independently) by Alon, Kalai and Frankl almost thirty years ago. In this paper we study the random questions, and determine the critical probability p _c(n,K _r) for the K _r-process up to a poly-logarithmic factor. In the case r = 4 we prove a stronger result, and determine the threshold for p _c(n,K ₄).