The maximum length of K_r-Bootstrap Percolation

MaRDI QIDQ6321855zbMATH OpenFDO

Authors József Balogh, Gal Kronenberg, Alexey Pokrovskiy, Tibor Szabó

Publication date 10 July 2019

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal combinatorics (05D99) Arithmetic progressions (11B25) Percolation (82B43)

Abstract: Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollob'as 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}subseteqE(K_n)$, we infect a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n],E_{t}cupe)$. A question raised by Bollob'as asks for the maximum time the process can run before it stabilizes. Bollob'as, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where $H=K_r$. They answered the question for $rleq4$ and gave a non-trivial lower bound for every $rgeq5$. 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 $rgeq6$ and we give a better lower bound for the case $r=5$; in the proof we use the Behrend construction.

This page was built for publication: The maximum length of $K_r$-Bootstrap Percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6321855)