Long running times for hypergraph bootstrap percolation

Abstract

Consider the hypergraph bootstrap percolation process in which, given a fixed $r$-uniform hypergraph $H$ and starting with a given hypergraph $G_0$, at each step we add to $G_0$ all edges that create a new copy of $H$. We are interested in maximising the number of steps that this process takes before it stabilises. For the case where $H=K_{r+1}^{(r)}$ with $r\ge 3$, we provide a new construction for $G_0$ that shows that the number of steps of this process can be of order $\Theta (n^r)$. This answers a recent question of Noel and Ranganathan. To demonstrate that different running times can occur, we also prove that, if $H$ is $K_4^{(3)}$ minus an edge, then the maximum possible running time is $2n-\lfloor {\log }_2(n-2)\rfloor -6$. However, if $H$ is $K_5^{(3)}$ minus an edge, then the process can run for $\Theta (n^3)$ steps.

Added two new results