论文标题
随机$ k_k $ - 拆卸算法
Random $K_k$-removal algorithm
论文作者
论文摘要
一个有趣的问题是图形如何从某些受约束的随机图过程中发展，这是动态网络形成和演变中的基本机制。这里的问题是指随机$ k_k $ - 删除算法。对于固定的整数$ k \ geqslant 3 $，它以$ n \ rightarrow \ infty $ vertices上的完整图开始，然后迭代地删除了均匀选择的$ k_k $的边缘。该算法终止，一旦剩下$ k_k $ s，它也会生成一个线性$ k $均匀的超图。对于$ k = 3 $，显示最终图中的大小为$ n^{3/2+o（1）} $。在$ k \ geqslant 4 $的情况下，结果更少。在本文中，我们证明该算法中各种关键参数的确切预期轨迹到某些迭代中，因此该算法中的最终大小最多是$ n^{2-1/（k-1）-2 -2 -2）+O（1）} $ for $ k \ geqslant 4 $。我们还表明，界限是自然的障碍。
One interesting question is how a graph develops from some constrained random graph process, which is a fundamental mechanism in the formation and evolution of dynamic networks. The problem here is referred to the random $K_k$-removal algorithm. For a fixed integer $k\geqslant 3$, it starts with a complete graph on $n\rightarrow\infty$ vertices and iteratively removes the edges of an uniformly chosen $K_k$. This algorithm terminates once no $K_k$s remain and at the same time it generates one linear $k$-uniform hypergraph. For $k=3$, it was shown that the size in the final graph is $n^{3/2+o(1)}$. Less results are on the cases when $k\geqslant 4$. In this paper, we prove that the exact expected trajectories of various key parameters in the algorithm to some iteration such that the final size in the algorithm is at most $n^{2-1/(k(k-1)-2)+o(1)}$ for $k\geqslant 4$. We also show the bound is a natural barrier.
