Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
复制标题
随机 3-一致超图中的松散哈密顿循环
DOI：
10.37236/477
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
A. Frieze
在随机超图$H=H_{n,p;3}$中，每个可能的三元组以$p$的概率独立出现。一个松散的汉密尔顿环可以被描述为一个边序列$\{x_i,y_i,x_{i+1}\}$对于$i=1,2,\ldots,n/2$，其中$x_1,x_2,\ldots,x_{n/2},y_1,y_2,\ldots,y_{n/2}$都是不同的。我们证明存在一个绝对常数$K>0$，使得如果$p\geq {K\log n\over n^2}$则 $$\lim_{\textstyle{n\to \infty\atop 4|n}}\Pr(H_{n,p;3}\ contains\ a\ loose\ Hamilton\ cycle)=1.$$
In the random hypergraph $H=H_{n,p;3}$ each possible triple appears independently with probability $p$. A loose Hamilton cycle can be described as a sequence of edges $\{x_i,y_i,x_{i+1}\}$ for $i=1,2,\ldots,n/2$ where $x_1,x_2,\ldots,x_{n/2},y_1,y_2,\ldots,y_{n/2}$ are all distinct. We prove that there exists an absolute constant $K>0$ such that if $p\geq {K\log n\over n^2}$ then $$\lim_{\textstyle{n\to \infty\atop 4|n}}\Pr(H_{n,p;3}\ contains\ a\ loose\ Hamilton\ cycle)=1.$$