论文标题
HyperGraph Bootstrap Percolation的长期运行时间
Long running times for hypergraph bootstrap percolation
论文作者
论文摘要
考虑HyperGraph Bootstrap Percolation Percolation Percolation过程，在该过程中，考虑到固定的$ r $ r $均匀的hypergraph $ h $，并从给定的HyperGraph $ g_0 $开始，在每个步骤中，我们将其添加到$ G_0 $ $ g_0 $所有的边缘，这些边缘创建了$ h $的新副本。我们有兴趣最大化此过程稳定之前采取的步骤数。对于带有$ r \ geq3 $的$ h = k_ {r+1}^{（r）} $，我们为$ g_0 $提供了新的构造，这表明此过程的步骤数可以是$θ（n^r）$的订单。这回答了Noel和Ranganathan的最新问题。为了证明可能发生不同的运行时间，我们还证明，如果$ h $是$ k_4^{（3）} $减去边缘，则最大可能的运行时间为$ 2N- \ lfloor \ log_2（n-2）\ rfloor-6 $。但是，如果$ h $是$ k_5^{（3）} $减去边缘，则该过程可以以$θ（n^3）$ steps运行。
Consider the hypergraph bootstrap percolation process in which, given a fixed $r$-uniform hypergraph $H$ and starting with a given hypergraph $G_0$, at each step we add to $G_0$ 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=K_{r+1}^{(r)}$ with $r\geq3$, we provide a new construction for $G_0$ that shows that the number of steps of this process can be of order $Θ(n^r)$. This answers a recent question of Noel and Ranganathan. To demonstrate that different running times can occur, we also prove that, if $H$ is $K_4^{(3)}$ minus an edge, then the maximum possible running time is $2n-\lfloor \log_2(n-2)\rfloor-6$. However, if $H$ is $K_5^{(3)}$ minus an edge, then the process can run for $Θ(n^3)$ steps.
