The time of graph bootstrap percolation
Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Wiley
2016
|
| _version_ | 1797064003918233600 |
|---|---|
| author | Gunderson, K Koch, S Przykucki, M |
| author_facet | Gunderson, K Koch, S Przykucki, M |
| author_sort | Gunderson, K |
| collection | OXFORD |
| description | Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollob\'as and Morris considered graph bootstrap percolation for $G = G(n,p)$ and studied the critical probability $p_c(n,K_r)$, for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time $t$ for all $1 \leq t \leq C \log\log n$. |
| first_indexed | 2024-03-06T21:08:04Z |
| format | Journal article |
| id | oxford-uuid:3d287434-5454-4489-8b4e-f4922b2dc89c |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:08:04Z |
| publishDate | 2016 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:3d287434-5454-4489-8b4e-f4922b2dc89c2022-03-26T14:17:57ZThe time of graph bootstrap percolationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3d287434-5454-4489-8b4e-f4922b2dc89cSymplectic Elements at OxfordWiley2016Gunderson, KKoch, SPrzykucki, MGraph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollob\'as and Morris considered graph bootstrap percolation for $G = G(n,p)$ and studied the critical probability $p_c(n,K_r)$, for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time $t$ for all $1 \leq t \leq C \log\log n$. |
| spellingShingle | Gunderson, K Koch, S Przykucki, M The time of graph bootstrap percolation |
| title | The time of graph bootstrap percolation |
| title_full | The time of graph bootstrap percolation |
| title_fullStr | The time of graph bootstrap percolation |
| title_full_unstemmed | The time of graph bootstrap percolation |
| title_short | The time of graph bootstrap percolation |
| title_sort | time of graph bootstrap percolation |
| work_keys_str_mv | AT gundersonk thetimeofgraphbootstrappercolation AT kochs thetimeofgraphbootstrappercolation AT przykuckim thetimeofgraphbootstrappercolation AT gundersonk timeofgraphbootstrappercolation AT kochs timeofgraphbootstrappercolation AT przykuckim timeofgraphbootstrappercolation |