On the Running Time of Hypergraph Bootstrap Percolation

Abstract

Given $r\ge 2$ and an $r$-uniform hypergraph $F$, the $F$-bootstrap process starts with an $r$-uniform hypergraph $H$ and, in each time step, every hyperedge which "completes" a copy of $F$ is added to $H$. The maximum running time of this process has been recently studied in the case that $r=2$ and $F$ is a complete graph by Bollobás, Przykucki, Riordan and Sahasrabudhe [Electron. J. Combin. 24(2) (2017), Paper No. 2.16], Matzke [arXiv:1510.06156v2] and Balogh, Kronenberg, Pokrovskiy and Szabó [arXiv:1907.04559v1]. We consider the case that $r\ge 3$ and $F$ is the complete $r$-uniform hypergraph on $k$ vertices. Our main results are that the maximum running time is $\Theta \left(n^r\right)$ if $k\ge r+2$ and $\Omega \left(n^{r-1}\right)$ if $k=r+1$. For the case $k=r+1$, we conjecture that our lower bound is optimal up to a constant factor when $r=3$, but suspect that it can be improved by more than a constant factor for large $r$.

arXiv comment20 pages, 3 figures

References in corpus (7)

• Monotone cellular automata in a random environment
• The second term for two-neighbour bootstrap percolation in two dimensions
• Weak saturation numbers of complete bipartite graphs in the clique
• A sharp threshold for a modified bootstrap percolation with recovery
• The Saturation Time of Graph Bootstrap Percolation
• Maximal Bootstrap Percolation Time on the Hypercube via Generalised Snake-in-the-Box
• Long running times for hypergraph bootstrap percolation

Cited by in corpus (1)

• The maximal running time of hypergraph bootstrap percolation