Upper bounds on the running time of bootstrap percolation

Abstract

For $k$-graphs $F$ and $H_0$ the $F$-bootstrap percolation process (or $F$-process) starting with $H_0$ is a sequence $(H_i{)}_{i\ge 0}$ of $k$-graphs such that $H_{i+1}$ is obtained from $H_i$ by adding all those $e\in V(H_0{)}^{(k)}\setminus E(H_i)$ as edges that complete a new copy of $F$. The running time of this $F$-process, denoted by $M_F(H_0)$, is the smallest $i$ with $H_i=H_{i+1}$. Bollobás proposed the problem of determining the maximum running time for $n\in \mathbb{N}$, i.e., $M_F(n)={\max }_{|V(H_0)|=n}{M}_F(H_0)$. Although this problem has received a lot of attention recently, until now the best known upper bound for $M_{K_t}(n)$, with $t\ge 5$, was the trivial bound $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Here we provide the first non-trivial upper bound for this problem by showing that $$M_{K_t}(n)\le (\frac{t-3}{t-2}+o(1))\left(\genfrac{}{}{0ex}{}{n}{2}\right)$$ holds for every integer $t\ge 3$. In fact, we prove the following more general result. For every $k\ge 2$, every $k$-graph $F$, and every $e\in E(F)$ we have $M_F(n)\le (\ddot{I}€(F-e)+o(1))\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, where $\ddot{I}€$ is the Turán density.

8 pages. arXiv admin note: text overlap with arXiv:2604.04607. text overlap with arXiv:2604.04607