On the maximum running time in graph bootstrap percolation

Bollobás, Béla; Przykucki, Micha{\l}; Riordan, Oliver; Sahasrabudhe, Julian
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{\$}.
Research areas:
Year:
2015
Type of Publication:
Article
Pages:
1-17
Hits: 3537

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information