Given $r\geq2$ 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\'as, Przykucki, Riordan and Sahasrabudhe [Electron. J. Combin. 24(2) (2017), Paper No. 2.16], Matzke [arXiv:1510.06156v2] and Balogh, Kronenberg, Pokrovskiy and Szab\'o [arXiv:1907.04559v1]. We consider the case that $r\geq3$ 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\geq 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$.
@article{10_37236_11307,
author = {Jonathan A. Noel and Arjun Ranganathan},
title = {On the running time of hypergraph bootstrap percolation},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {2},
doi = {10.37236/11307},
zbl = {1517.05087},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11307/}
}
TY - JOUR
AU - Jonathan A. Noel
AU - Arjun Ranganathan
TI - On the running time of hypergraph bootstrap percolation
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/11307/
DO - 10.37236/11307
ID - 10_37236_11307
ER -
%0 Journal Article
%A Jonathan A. Noel
%A Arjun Ranganathan
%T On the running time of hypergraph bootstrap percolation
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11307/
%R 10.37236/11307
%F 10_37236_11307
Jonathan A. Noel; Arjun Ranganathan. On the running time of hypergraph bootstrap percolation. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/11307
