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 g e q 5

by giving an explicit construction.

This page was built for publication: The Saturation Time of Graph Bootstrap Percolation