Upper bounds on the running time of bootstrap percolation
Weichan Liu, Xiangxiang Nie, Simón Piga, Bjarne Schülke · 2026
Read Upper bounds on the running time of bootstrap percolation by Weichan Liu, Xiangxiang Nie, Simón Piga, Bjarne Schülke (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22630.txt.
Introduction
Liu and three colleagues give the first non-trivial bootstrap percolation bound for complete graphs. The F-bootstrap process adds edges completing copies of F, and the running time is the step where it stops changing. Bollobás posed the running time problem for n vertices. Until now the best bound for complete graphs on t vertices, with t at least 5, was the trivial pairs bound. Running time is a fraction of pairs approaching one from below as t grows, for t at least 3. A k-graph result follows.
Catalog record
| CREATOR | Weichan Liu, Xiangxiang Nie, Simón Piga, Bjarne Schülke |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16897 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22630
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Upper bounds on the running time of bootstrap percolation Weichan Liu, Xiangxiang Nie, Simón Piga, Bjarne Schülke Abstract . For k k -graphs F F and H 0 H_{0} the F F -bootstrap percolation process (or F F -process) starting with H 0 H_{0} is a sequence ( H i ) i ≥ 0 (H_{i})_{i\geq 0} of k k -graphs such that H i + 1 H_{i+1} is obtained from H i H_{i} by adding all those e ∈ V ( H 0 ) ( k ) ∖ E ( H i ) e\in V(H_{0})^{(k)}\smallsetminus E(H_{i}) as edges that complete a new copy of F F . The running time of this F F -process, denoted by M F ( H 0 ) M_{F}(H_{0}) , is the smallest i i with H i = H i + 1 H_{i}=H_{i+1} . Bollobás proposed the problem of determining the maximum running time for n ∈ ℕ n\in\mathds{N} , i.e., M F ( n ) = max | V ( H 0 ) | = n M F ( H 0 ) 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 ) M_{K_{t}}(n) , with t ≥ 5 t\geq 5 , was the trivial bound ( n 2 ) \binom{n}{2} . Here we provide the first non-trivial upper bound for this problem by showing that M K t ( n ) ≤ ( t − 3 t − 2 + o ( 1 ) ) ( n 2 ) M_{K_{t}}(n)\leq\Big(\frac{t-3}{t-2}+o(1)\Big)\binom{n}{2} holds for every integer t ≥ 3 t\geq 3 . In fact, we prove the following more general result. For every k ≥ 2 k\geq 2 , every k k -graph F F , and every e ∈ E ( F ) e\in E(F) we have M F ( n ) ≤ ( π ( F − e ) + o ( 1 ) ) ( n k ) M_{F}(n)\leq\big(\pi(F-e)+o(1)\big)\binom{n}{k} , where π \pi is the Turán density. 1. Introduction A k -uniform hypergraph (or k -graph ) H consists of a vertex set V(H) and a set of edges E(H)\subseteq V(H)^{(k)} , where V(H)^{(k)}=\{S\subseteq V(H):|S|=k\} . Given k -graphs F and H , a copy of F in H is a subhypergraph of H that is isomorphic to F . The number of copies of F in H is denoted by c(F,H) . The F -bootstrap percolation process (or F -process ) starting with H is the sequence (H_{i})_{i\geq 0} of k -graphs with H_{i} defined inductively as follows. Set H_{0}=H and given H_{i} let H_{i+1} be the k -graph with vertex set V(H) and edge set \displaystyle E(H_{i+1})=E(H_{i})\cup\big\{e\in V(H)^{(k)}:\>c(F,H_{i}\cup e)>c(F,H_{i})\big\}\,, where H_{i}\cup e denotes the k -graph \big(V(H),E(H_{i})\cup\{e\}\big) . This notion originates in the work of Bollobás [ 4 ] , where it arose in the context of weak saturation. Since then, connections to other areas such as to cellular automata, more general bootstrap-type dynamics [ 18 ] , and statistical physics (see [ 1 ] and [ 5 ] ) have been established. Bollobás [ 3 ] suggested the problem of determining the maximum running time of such processes (see also [ 12 ] for a random variant). More precisely, the running time of the F -process starting with H is \tau_{F}(H)=\min\{t\in\mathbb{N}_{\geq 0}:\>H_{t}=H_{t+1}\} . Given n\in\mathds{N} (and for k=2 ), Bollobás asked to determine M_{F}(n)=\max\big\{\tau_{F}(H):\>H\text{ is a }k\text{-graph on }n\text{ vertices}\big\}\,. One major theme in this area is the maximum running time of K_{r} -processes, where K_{r} is the complete graph on r vertices. Bollobás, Przykucki, Riordan, and Sahasrabudhe [ 3 ] and, independently, Matzke [ 17 ] showed that M_{K_{4}}(n)=n-3 , for all n\geq 3 . In [ 3 ] the authors also showed that M_{K_{r}}(n)\geq n^{2-\lambda_{r}-o(1)} for r\geq 5 , where \lambda_{r} is some explicit constant with \lambda_{r}\rightarrow 0 as r\rightarrow\infty , and conjectured that for all r\geq 5 , M_{K_{r}}(n)=o(n^{2}) . Balogh, Kronenberg, Pokrovskiy, and Szabó [ 2 ] disproved this conjecture, showing that M_{K_{r}}(n)=\Omega(n^{2}) for all r\geq 6 . For r=5 , they used Behrend’s construction for arithmetic progressions to show that M_{K_{5}}(n) is asymptotically larger than n^{2-\varepsilon} for all \varepsilon>0 . It remains an open problem whether M_{K_{5}}(n) is quadratic in n or not. Until now, the best known upper bound for M_{K_{t}}(n) , with t\geq 5 , was the trivial upper bound \binom{n}{2} . This frustrating state of affairs has been pointed out repeatedly in the literature, for instance in [ 3 ] , [ 2 ] , and most recently in the survey [ 10 ] . Here we establish the first non-trivial upper bound on M_{K_{t}}(n) for t\geq 5 . Theorem 1.1 . For every t\geq 3 we have M_{K_{t}}(n)\leq\big(\frac{t-3}{t-2}+o(1)\big)\binom{n}{2} . The o(1) notation in the statement means that for every \varepsilon>0 there is some n_{0} such that M_{K_{t}}(n)\leq\big(\frac{t-3}{t-2}+\varepsilon\big)\binom{n}{2} for all n\in\mathds{N} with n\geq n_{0} . Moreover, we provide a non-trivial upper bound for every graph in terms of the chromatic number . Recall that for a graph F the chromatic number \chi(F) denotes the smallest c\in\mathds{N} such that there is a proper colouring of F with c colours. Theorem 1.2 . For every graph F and every e\in E(F) we have M_{F}(n)\leq\bigg(\frac{\chi(F-e)-2}{\chi(F-e)-1}+o(1)\bigg)\binom{n}{2}\,. Note that Theorem 1.2 directly implies Theorem 1.1 . Apart from few exceptions (see the survey by Fabian, Morris, and Szabó [ 10 ] ), for a general graph F no non-trivial upper bound on M_{F}(n) was known. One notable exception is the following proposition by Fabian, Morris, and Szabó [ 9 ] with a very elegant proof. Proposition 1.3 ( [ 9 ] ) . Let F be a graph with at least two edges. Then M_{F}(n)\leq 2\text{\rm ex}(n,F) for every n\in\mathds{N} . Note that this proposition provides non-trivial upper bounds for bipartite graphs F but not for non-bipartite ones. For a further discussion of this proposition and more background on the F -process we refer the reader to the survey by Fabian, Morris, and Szabó [ 10 ] . Recently, the investigation of F -processes and their maximum running times was initiated for hypergraphs, see [ 19 ] , [ 13 ] , and [ 8 ] . While these works established that M_{K^{(k)}_{r}}(n)=\Omega(n^{k}) holds for all k\geq 3 and r\geq k+1 , also in this setting non-trivial upper bounds were lacking. The only non-trivial upper bounds for hypergraphs (of uniformity at least 3 ) before this work were for K_{4}^{(3)-} , proved in [ 8 ] , and for extension hypergraphs [ 16 ] . In particular, the best known upper bound for any k -uniform clique was so far \binom{n}{k} . We provide the first non-trivial upper bounds in this more general setup as well and indeed Theorem 1.2 is a simple corollary of our general result for hypergraphs. To state it, we briefly recall the following definitions. Given a k -graph F and n\in\mathds{N} , the extremal number of n and F , denoted by \text{\rm ex}(n,F) , is the maximum number of edges that a k -graph on n vertices can