Slow graph bootstrap percolation I: Cycles

Abstract

Given a fixed graph $H$ and an $n$-vertex graph $G$, the $H$\emph{-bootstrap percolation process} on $G$ is defined to be the sequence of graphs $G_i$, $i\ge 0$ which starts with $G_0:=G$ and in which $G_{i+1}$ is obtained from $G_i$ by adding every edge that completes a copy of $H$. We are interested in $M_H(n)$ which is the maximum number of steps, over all $n$-vertex graphs $G$, that this process takes to stabilise. We determine this maximum running time precisely when $H$ is a cycle, giving the first infinite family of graphs $H$ for which an exact solution is known. We find that $M_{C_k}(n)$ is of order ${\log }_{k-1}(n)$ for all $3\le k\in \mathbb{N}$. Interestingly though, the function exhibits different behaviour depending on the parity of $k$ and the exact location of the values of $n$ for which $M_H(n)$ increases is determined by the Frobenius number of a certain numerical semigroup depending on $k$.

26 pages, 3 figures, final version