Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/8160| Title: | On the Running Time of Hypergraph Bootstrap Percolation |
| Authors: | Noel, Jonathan A. RANGANATHAN, ARJUN Dept. of Mathematics |
| Keywords: | Metastability threshold Sharp threshold Saturation Bounds 2023-AUG-WEEK3 TOC-AUG-2023 2023 |
| Issue Date: | Jun-2023 |
| Publisher: | Electronic Journal of Combinatorics |
| Citation: | Electronic Journal of Combinatorics, 30(02). |
| 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. |
| URI: | https://doi.org/10.37236/11307 http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/8160 |
| ISSN: | 1077-8926 |
| Appears in Collections: | JOURNAL ARTICLES |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.