The maximum length of K_r-Bootstrap Percolation

How long does it take for a pandemic to stop spreading? When modelling an infection process, especially these days, this is one of the main questions that comes to mind. In this talk, we consider this question in the bootstrap percolation setting.

Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges $E_0$, and we infect new edges according to a predetermined rule. Given a graph $H$ and a set of previously infected edges $E_t \subseteq E(Kn)$, we infect a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n] , E_t \cup \{e\})$. A question raised by Bollobás asks for the maximum time the process can run before it stabilizes. Bollobás, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where $H=K_r$. They answered the question for $r \leq 4$ and gave a non-trivial lower bound for every $r \geq 5$. They also conjectured that the maximal running time is $o(n^2)$ for every integer $r$. We disprove their conjecture for every $r \geq 6$ and we give a better lower bound for the case $r=5$; in the proof we use the Behrend construction. This is a joint work with József Balogh, Alexey Pokrovskiy, and Tibor Szabó.