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 \u27infected\u27 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 4). © 2012 Wiley Periodicals, Inc