2022/09/05 by Díaz, Alberto Espuny, Janzer, Barnabás, Kronenberg, Gal +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2209.02015
Consider the hypergraph bootstrap percolation process in which, given a fixed r-uniform hypergraph H and starting with a given hypergraph G0, at each step we add to G0 all edges that create a new copy of H. We are interested in maximising the number of steps that this process takes before it stabilises. For the case where H=Kr+1(r) with r≥3, we provide a new construction for G0 that shows that the number of steps of this process can be of order Θ(nr). This answers a recent question of Noel and Ranganathan. To demonstrate that different running times can occur, we also prove that, if H is K4(3) minus an edge, then the maximum possible running time is 2n-\lfloor log2(n-2)\rfloor-6. However, if H is K5(3) minus an edge, then the process can run for Θ(n3) steps.