2019/07/10 by Balogh, József, Kronenberg, Gal, Pokrovskiy, Alexey +1
#05C35 #05D99 #11B25 #82B43 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1907.04559
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 E0, and we infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges Et⊆ E(Kn), we infect a non-infected edge e if it completes a new copy of H in G=([n],Et∪ 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=Kr. They answered the question for r≤ 4 and gave a non-trivial lower bound for every r≥ 5. They also conjectured that the maximal running time is o(n2) for every integer r. In this paper we disprove their conjecture for every r≥ 6 and we give a better lower bound for the case r=5; in the proof we use the Behrend construction.