On Pósa's Conjecture for Random Graphs
On Pósa's Conjecture for Random Graphs
复制标题
关于Pósa的随机图猜想
DOI：
10.1137/120871729
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Deryk Osthus
中科院分区：
文献类型：
--
作者：
D. Kühn;Deryk Osthus
著名的Posa猜想指出，每个最小度至少为2n/3的图都包含一个汉密尔顿圈的平方。这已经被证明了大$n$由Komlos，萨科齐，和Szemeredi。本文证明了：若p \gem ^{-1/2+\varepad}$，则二项随机图G_{n，p}$渐近几乎必然包含一个汉密尔顿圈的平方.这为属性提供了一个“近似阈值”，在这个意义上，如果$p\le n^{-1/2}$，结果将不成立。
The famous Posa conjecture states that every graph of minimum degree at least $2n/3$ contains the square of a Hamilton cycle. This has been proved for large $n$ by Komlos, Sarkozy, and Szemeredi. Here we prove that if $p \ge n^{-1/2+\varepsilon}$, then asymptotically almost surely, the binomial random graph $G_{n,p}$ contains the square of a Hamilton cycle. This provides an “approximate threshold” for the property in the sense that the result fails to hold if $p\le n^{-1/2}$.
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus