论文标题
在随机图中最长循环的长度上的改进的下限
An improved lower bound on the length of the longest cycle in random graphs
论文作者
论文摘要
我们在二项式随机图$ g（n，（1+ε）/n）$的最长循环的长度上提供了一个新的下限，该循环的最长界限（n，（1+ε）/n）$持有W.H.P.对于所有$ε=ε（n）$，使$ε^3n \ to \ infty $。在某些足够小的常数$ε_0$的情况下，$ε\leqε_0$，此键等于$1.581ε^2n $，这在当前最佳下限$4ε^2n/3 $上得到改善。
We provide a new lower bound on the length of the longest cycle of the binomial random graph $G(n,(1+ε)/n)$ that holds w.h.p. for all $ε=ε(n)$ such that $ε^3n\to \infty$. In the case $ε\leq ε_0$ for some sufficiently small constant $ε_0$, this bound is equal to $1.581ε^2n$ which improves upon the current best lower bound of $4ε^2n/3$ due to Luczak.
