- 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