Largest Components in Random Hypergraphs
Largest Components in Random Hypergraphs
复制标题
随机超图中的最大组成部分
DOI：
10.1017/s096354831800010x
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Y. Person
中科院分区：
文献类型：
--
作者：
Oliver Cooley;Mihyun Kang;Y. Person
本文考虑随机k-一致超图中的j-元组连通分支（j-元组连通性关系可以通过让两个j-集连通，如果它们位于公共边并考虑传递闭包来定义; j = 1的情况对应于点连通性的常见概念）。我们证明了包含Θ（nj）j-集的j-元组连通分支的存在性经历了相变，并证明了阈值出现在边缘概率处
$$\frac{（k-j）！} {\binom{k}{j}-1}n^{j-k}.$$
我们的证明扩展了Krivelevich和Sudakov最近的简短证明，该证明利用深度优先搜索来揭示随机图的边缘。我们的主要原始贡献是一个有界度引理，它控制着搜索过程中增长的组件的结构。
In this paper we consider j-tuple-connected components in random k-uniform hypergraphs (the j-tuple-connectedness relation can be defined by letting two j-sets be connected if they lie in a common edge and considering the transitive closure; the case j = 1 corresponds to the common notion of vertex-connectedness). We show that the existence of a j-tuple-connected component containing Θ(nj) j-sets undergoes a phase transition and show that the threshold occurs at edge probability
$$\frac{(k-j)!}{\binom{k}{j}-1}n^{j-k}.$$
Our proof extends the recent short proof for the graph case by Krivelevich and Sudakov, which makes use of a depth-first search to reveal the edges of a random graph. Our main original contribution is a bounded degree lemma, which controls the structure of the component grown in the search process.
DOI：
10.1017/s0963548314000017
发表时间：
2014
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
M. Behrisch;A. Coja-Oghlan;M. Kang
通讯作者：
M. Kang