The maximal running time of hypergraph bootstrap percolation

Abstract

We show that for every $r\ge 3$, the maximal running time of the $K_{r+1}^r$-bootstrap percolation in the complete $r$-uniform hypergraph on $n$ vertices $K_n^r$ is $\Theta (n^r)$. This answers a recent question of Noel and Ranganathan in the affirmative, and disproves a conjecture of theirs. Moreover, we show that the prefactor is of the form $r^{-r}{\mathrm{e}}^{O(r)}$ as $r\to \infty$.

10 pages, 2 figures, updated creative commons license

References in corpus (1)

• On the Running Time of Hypergraph Bootstrap Percolation