Slow subgraph bootstrap percolation (Tibor Szabó, Freie Universität Berlin)
- Series
- Graph Theory Seminar
- Time
- Tuesday, March 5, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Tibor Szabó – Freie Universität Berlin – szabo@math.fu-berlin.de
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.