On the Running Time of Hypergraph Bootstrap Percolation

Abstract

GivenrÍ2andanr-uniformhypergraphF,theF-bootstrapprocessstartswithanr-uniformhypergraphHand,ineachtimestep,everyhyperedgewhich“completes”acopyofFisaddedtoH.Themaximumrunningtimeofthispro-cesshasbeenrecentlystudiedinthecasethatr=2andFisacompletegraphbyBollob ́as,Przykucki,RiordanandSahasrabudhe[Electron.J.Combin.24(2)(2017),PaperNo.2.16],Matzke[arXiv:1510.06156v2]andBalogh,Kronenberg,PokrovskiyandSzab ́o[arXiv:1907.04559v1].WeconsiderthecasethatrÍ3andFisthecompleter-uniformhypergraphonkvertices.OurmainresultsarethatthemaximumrunningtimeisΘ(nr)ifkÍr+2andΩ nr−1 ifk=r+1.Forthecasek=r+1,weconjecturethatourlowerboundisoptimaluptoaconstantfactorwhenr=3,butsuspectthatitcanbeimprovedbymorethanaconstantfactorforlarger.