The maximal running time of hypergraph bootstrap percolation

arXiv2208.13489MaRDI QIDQ6506482FDOQ6506482

Authors: Ivailo Hartarsky, Lyuben Lichev 

Abstract: We show that for every $rgeq3$, the maximal running time of the $K_{r+1}^r$-bootstrap percolation in the complete $r$-uniform hypergraph on $n$ vertices $K_n^r$ is $Theta(n^r)$. This answers a recent question of Noel and Ranganathan in the affirmative, and disproves a conjecture of theirs. In fact, we also determine the leading asymptotics of the prefactor when $rightarrowinfty$.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal combinatorics (05D99)

This page was built for publication: The maximal running time of hypergraph bootstrap percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6506482)