@article{bollobas2015maximum,
author = "B{\'e}la Bollob{\'a}s and Micha{\l} Przykucki and Oliver Riordan and Julian Sahasrabudhe",
abstract = "Graph bootstrap percolation is a simple cellular automaton introduced by Bollob$\backslash$'as in 1968. Given a graph {\$}H{\$} and a set {\$}G \backslashsubseteq E(K{\_}n){\$} we initially "infect" all edges in {\$}G{\$} and then, in consecutive steps, we infect every {\$}e \backslashin 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 Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollob$\backslash$'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 {\$}\backslashlceil \backslashlog{\_}2 (n-1) \backslashrceil {\$}. However, a new phenomenon occurs for {\$}r=4{\$} when, as we show, the maximum time of the process is {\$}n-3{\$}. For {\$}r \backslashgeq 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-\backslashvarepsilon{\_}r{\}}{\$} time steps for some {\$}\backslashvarepsilon{\_}r{\$} that tends to {\$}0{\$} as {\$}r \backslashto \backslashinfty{\$}.",
pages = "1--17",
title = "{O}n the maximum running time in graph bootstrap percolation",
url = "http://arxiv.org/abs/1510.07096",
year = "2015",
}