The Saturation Time of Graph Bootstrap Percolation

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\ge 5$ by giving an explicit construction.

This paper is a part of my Master Thesis written at Technische Universität München under the direction of Nina Gantert. Corrected a typo and added references

References in corpus (1)

• Bootstrap percolation in three dimensions

Cited by in corpus (1)

• On the Running Time of Hypergraph Bootstrap Percolation