The maximum length of $K_r$-Bootstrap Percolation

Abstract

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(K_n)$, 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\le 4$ and gave a non-trivial lower bound for every $r\ge 5$. They also conjectured that the maximal running time is $o(n^2)$ for every integer $r$. In this paper we disprove their conjecture for every $r\ge 6$ and we give a better lower bound for the case $r=5$; in the proof we use the Behrend construction.

10 pages