Long running times for hypergraph bootstrap percolation
Combinatorics Seminar
12th March 2024, 11:00 am – 12:00 pm
Fry Building, 2.04
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 maximizing the number of steps that this process takes before it stabilizes. For the case where $H=K_{r+1}^{(r)}$ with $r \geq 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. Joint work with Alberto Espuny D\'{i}az, Barnab\'{a}s Janzer, and Gal Kronenberg.
Comments are closed.