## Abstract

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 _{4}).

Original language | English (US) |
---|---|

Pages (from-to) | 413-440 |

Number of pages | 28 |

Journal | Random Structures and Algorithms |

Volume | 41 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2012 |

## Keywords

- Bootstrap percolation
- Graph theory
- Weak saturation

## ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics