On the running time of hypergraph bootstrap percolation (Q6106304)

Summary: Given \(r\geqslant 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 \textit{B. Bollobás} et al. [Electron. J. Comb. 24, No. 2, Research Paper P2.16, 20 p. (2017; Zbl 1361.05135)], \textit{K. Matzke} [``The saturation time of graph bootstrap percolation'', Preprint, \url{arXiv:1510.06156v2}] and \textit{J. Balogh} et al. [``The maximum length of \(K_r\)-bootstrap percolation'', Preprint, \url{arXiv:1907.04559v1}]. We consider the case that \(r\geqslant 3\) and \(F\) is the complete \(r\)-uniform hypergraph on \(k\) vertices. Our main results are that the maximum running time is \(\Theta (n^r)\) if \(k\geqslant r+2\) and \(\Omega(n^{r-1})\) 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\).