## Abstract

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**that completes a new infected copy of_{n}**H**in**K**. We say that_{n}**G**percolates if eventually every edge in**K**is infected. The extremal question about the size of the smallest percolating sets when_{n}**H**=**K**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}**r**=**3**this maximum is ⌈**log**(_{2}**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**-bootstrap process can run for at least_{r}**n**^{2}^{−εr}time steps for some ε**that tends to**_{r}**0**as**r**→**∞**.Original language | English |
---|---|

Article number | P2.16 |

Number of pages | 20 |

Journal | Electronic Journal of Combinatorics |

Volume | 24 |

Issue number | 2 |

Publication status | Published - 5 May 2017 |

## Keywords

- Bootstrap percolation
- Weak saturation
- Cellular automata
- Monotone cellular automata
- Extremal combinatorics