Name
Abstract | ||
|---|---|---|
Graph bootstrap percolation is a simple cellular automaton introduced by Bollobas in 1968. Given a graph H and a set G subset of E(K-n) we initially 'infect' all edges in G and then, in consecutive steps, we infect every e is an element of 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 Bollobas: what is the maximum time the process can run before it stabilizes? It is an easy observation that for r = 3 this maximum is [log(2)(n - 1)]. However, a new phenomenon occurs for r = 4 when, as we show, the maximum time of the process is n - 3. For r >= 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-epsilon r) time steps for some epsilon(r) that tends to 0 as r -> infinity. |
Year | Venue | Keywords |
|---|---|---|
2017 | ELECTRONIC JOURNAL OF COMBINATORICS | Bootstrap percolation,weak saturation,cellular automata,monotone cellular automata,extremal combinatorics |
Field | DocType | Volume |
Cellular automaton,Discrete mathematics,Graph,Combinatorics,Bootstrap percolation,Mathematics | Journal | 24.0 |
Issue | ISSN | Citations |
2.0 | 1077-8926 | 1 |
PageRank | References | Authors |
0.63 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bela Bollobas | 1 | 66 | 12.05 |
| Michal Przykucki | 2 | 35 | 6.79 |
| Oliver Riordan | 3 | 285 | 38.31 |
| J. Sahasrabudhe | 4 | 3 | 2.79 |