## Abstract

Graph bootstrap percolation, introduced by Bollobás in 1968, is a cellular automaton defined as follows. Given a "small" graph H and a "large" graph G=G

For H=K

_{0}⊆K_{n}, in consecutive steps we obtain G_{t+1}from G_{t}by adding to it all new edges e such that Gt∪e contains a new copy of H. We say that G percolates if for some t≥0, we have G_{t}=K_{n}.For H=K

_{r}, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollobás and Morris considered graph bootstrap percolation for G=G(n,p) and studied the critical probability p_{c}(n,K_{r}), for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time t for all 1≤t≤C log log n.Original language | English |
---|---|

Pages (from-to) | 143-168 |

Number of pages | 26 |

Journal | Random Structures and Algorithms |

Volume | 51 |

Issue number | 1 |

Early online date | 26 Aug 2016 |

DOIs | |

Publication status | Published - 2017 |

## Keywords

- bootstrap percolation
- weak saturation
- random graphs