The Saturation Time of Graph Bootstrap Percolation
read the original abstract
The process of $H$-bootstrap percolation for a graph $H$ is a cellular automaton, where, given a subset of the edges of $K_n$ as initial set, an edge is added at time $t$ if it is the only missing edge in a copy of $H$ in the graph obtained through this process at time $t-1$. We discuss an extremal question about the time of $K_r$-bootstrap percolation, namely determining maximal times for an $n$-vertex graph before the process stops. We determine exact values for $r=4$ and find a lower bound for the asymptotics for $r \geq 5$ by giving an explicit construction.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Upper bounds on the running time of bootstrap percolation
The maximum running time of F-bootstrap percolation on n vertices is at most (π(F minus one edge) plus o(1)) times the number of possible edges.
-
Bootstrap percolation of extension hypergraphs
For any graph G on t vertices and k at least 3, the maximum running time of the F-process where F is the k-extension of G is bounded by a constant C_{k,t} independent of n.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.