Slow graph bootstrap percolation I: Cycles

Given a fixed graph H and an n -vertex graph G , the H -bootstrap percolation process on G is defined to be the sequence of graphs G i , i ≥ 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 ≤ k ∈ ℕ . 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 .