论文标题
在HyperGraph Bootstrap Percolation的运行时间
On the Running Time of Hypergraph Bootstrap Percolation
论文作者
论文摘要
给定$ r \ geq2 $和$ r $均匀的hypergraph $ f $，$ f $ -bootstrap流程以$ r $ rus-rystrical-siform-siform-siform hypergraph $ h $开始，并且在每个时间步骤中，每个“完成” $ f $的“完成”副本均添加到$ h $中。最近研究了此过程的最大运行时间，即$ r = 2 $和$ f $是Bollobás，Przykucki，Riordan和Sahasrabudhe的完整图。 J. Combin。 24（2）（2017），第2.16页]，Matzke [Arxiv：1510.06156V2]和Balogh，Kronenberg，Pokrovskiy和Szabó[Arxiv：1907.04559v1]。我们认为，$ r \ geq3 $和$ f $是$ k $ Vertices上的完整$ r $ rust-Suormifergraph。我们的主要结果是，如果$ k \ geq r+2 $和$ω\ left（n^{r-1} \ right）如果$ k = r+1 $，则最大运行时间为$θ\ left（n^r \右）$。对于$ k = r+1 $的情况，我们认为，当$ r = 3 $时，我们的下限是最佳的恒定因素，但怀疑它可以将其提高到大于$ r $的恒定因素。
Given $r\geq2$ and an $r$-uniform hypergraph $F$, the $F$-bootstrap process starts with an $r$-uniform hypergraph $H$ and, in each time step, every hyperedge which "completes" a copy of $F$ is added to $H$. The maximum running time of this process has been recently studied in the case that $r=2$ and $F$ is a complete graph by Bollobás, Przykucki, Riordan and Sahasrabudhe [Electron. J. Combin. 24(2) (2017), Paper No. 2.16], Matzke [arXiv:1510.06156v2] and Balogh, Kronenberg, Pokrovskiy and Szabó [arXiv:1907.04559v1]. We consider the case that $r\geq3$ and $F$ is the complete $r$-uniform hypergraph on $k$ vertices. Our main results are that the maximum running time is $Θ\left(n^r\right)$ if $k\geq r+2$ and $Ω\left(n^{r-1}\right)$ if $k=r+1$. For the case $k=r+1$, we conjecture that our lower bound is optimal up to a constant factor when $r=3$, but suspect that it can be improved by more than a constant factor for large $r$.
