Georgia Institute of Technology College of Sciences

 For a graph $H$ and an $n$-vertex graph $G$, the $H$-bootstrap percolation process on $G$ is the process which starts with $G$ and, at every time step, adds any missing edges on the vertices of $G$ that complete a copy of $H$. This process eventually stabilises and we are interested in the extremal question raised by Bollob\'as, of determining the maximum \emph{running time} (number of time steps before stabilising) of this process, over all possible choices of $n$-vertex graph $G$. We initiate a systematic study of this parameter, denoted $M_H(n)$, and its dependence on properties of the graph $H$. In a series of works we determine the precise running time for cycles and asymptotic running time for several other important classes. In general, we study necessary and sufficient conditions on $H$ for fast, i.e. sublinear or linear $H$-bootstrap percolation, and in particular explore the relationship between running time and minimum vertex degree and connectivity. Furthermore we also obtain the running time of the process for typical $H$ and discover several graphs exhibiting surprising behavior.  The talk represents joint work with David Fabian and Patrick Morris.