On the maximum running time in graph bootstrap percolation (Q528995): Difference between revisions

Summary: Graph bootstrap percolation is a simple cellular automaton introduced by \textit{B. Bollobás} [Beitr. Graphentheorie, Int. Kolloquium Manebach (DDR) 1967, 25--31 (1968; Zbl 0172.48905)]. Given a graph \(H\) and a set \(G \subseteq E(K_n)\) we initially `infect' all edges in \(G\) and then, in consecutive steps, we infect every \(e \in K_n\) that completes a new infected copy of \(H\) in \(K_n\). We say that \(G\) percolates if eventually every edge in \(K_n\) is infected. The extremal question about the size of the smallest percolating sets when \(H = K_r\) was answered independently by \textit{N. Alon} [J. Comb. Theory, Ser. A 40, 82--89 (1985; Zbl 0578.05002)], \textit{G. Kalai} [Ann. Discrete Math. 20, 189--190 (1984; Zbl 0576.05018)] and \textit{P. Frankl} [Eur. J. Comb. 3, 125--127 (1982; Zbl 0488.05004)]. Here we consider a different question raised more recently by B. Bollobás: what is the maximum time the process can run before it stabilizes? It is an easy observation that for \(r=3\) this maximum is \(\lceil \log_2 (n-1) \rceil \). However, a new phenomenon occurs for \(r=4\) when, as we show, the maximum time of the process is \(n-3\). For \(r \geq 5\) the behaviour of the dynamics is even more complex, which we demonstrate by showing that the \(K_r\)-bootstrap process can run for at least \(n^{2-\varepsilon_r}\) time steps for some \(\varepsilon_r\) that tends to 0 as \(r \rightarrow \infty\).