On the maximum running time in graph bootstrap percolation

Journal article

Graph bootstrap percolation is a simple cellular automaton introduced by Bollob´as in 1968. Given a graph H and a set G ⊆ E(Kn) we initially “infect” all edges in G and then, in consecutive steps, we infect every e ∈ Kn that completes a new infected copy of H in Kn. We say that G percolates if eventually every edge in Kn is infected. The extremal question about the size of the smallest percolating sets when H = Kr was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollob´as: what is the maximum time the process can run before it stabilizes? It is an easy observation that for r = 3 this maximum is ⌈log2 (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 Kr-bootstrap process can run for at least n 2−εr time steps for some εr that tends to 0 as r → ∞.

Authors: Bollobás, B; Przykucki, M; Riordan, O; Sahasrabudhe, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Electronic Journal of Combinatorics
• Journal: Electronic Journal of Combinatorics
• Volume: 24
• Issue: 2
• Pages: P2.16
• Publication date: 2017-05-05
• Acceptance date: 2017-01-01
• EISSN: 1077-8926
• ISSN: 1077-8926
• Keywords: Cellular automata; Extremal combinatorics; Monotone cellular automata; Bootstrap percolation; Weak saturation