On the Running Time of Hypergraph Bootstrap Percolation

RANGANATHAN, ARJUN; Noel, Jonathan A.

DR Home
→
PUBLICATIONS & PATENTS
→
JOURNAL ARTICLES
→
View Item

dc.contributor.author	Noel, Jonathan A.	en_US
dc.contributor.author	RANGANATHAN, ARJUN	en_US
dc.date.accessioned	2023-08-25T05:37:46Z
dc.date.available	2023-08-25T05:37:46Z
dc.date.issued	2023-06	en_US
dc.identifier.citation	Electronic Journal of Combinatorics, 30(02).	en_US
dc.identifier.issn	1077-8926	en_US
dc.identifier.uri	https://doi.org/10.37236/11307	en_US
dc.identifier.uri	http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/8160
dc.description.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.	en_US
dc.language.iso	en	en_US
dc.publisher	Electronic Journal of Combinatorics	en_US
dc.subject	Metastability threshold	en_US
dc.subject	Sharp threshold	en_US
dc.subject	Saturation	en_US
dc.subject	Bounds	en_US
dc.subject	2023-AUG-WEEK3	en_US
dc.subject	TOC-AUG-2023	en_US
dc.subject	2023	en_US
dc.title	On the Running Time of Hypergraph Bootstrap Percolation	en_US
dc.type	Article	en_US
dc.contributor.department	Dept. of Mathematics	en_US
dc.identifier.sourcetitle	Electronic Journal of Combinatorics	en_US
dc.publication.originofpublisher	Foreign	en_US