论文标题
稀疏随机图中的循环长度
Cycle lengths in sparse random graphs
论文作者
论文摘要
我们研究了所有在$ n $ d $ g $ g $ n $ n $ g $中出现在$ n $ g $中的$ {\ cal l}（g）$ n $ d $ g $的$ $ n $ g $，用于固定$ d \ geq 3 $，以及在带有固定平均水平$ c> 1 $ $ c> 1 $的$ n $ n $ Vertices上的$rényi随机图中。这些模型中周期计数分布的基本结果是在1980年代和1990年代初建立的，重点是极端长度：固定长度的循环，以及$ n $的长度线性周期。在这里，我们得出了一个随机的$ d $ - 规范图，$ {\ cal l}（g）$同时包含整个范围$ \ {\ ell，\ ldots，n \} $ for $ \ ell \ ge g geq 3 $，作为$θ_\ ell = ul =θ_$ un（n ge）$ un（n ge）$ quyq 3 $（ $ \ ell \ to \ infty $。对于随机图$ {\ cal g}（n，p）$，$ p = c/n $，其中$ c \ geq c_0 $对于某些绝对常数$ c_0 $，我们显示了$ \ {\ ell，\ ell，\ ldots的范围的类似结果$ g $的最长周期。 $ {\ cal g}（n，p）$的限制概率与$ d $ regratiard cy的$θ_\ ell $相吻合时，当$ c $是$ c $是整数$ d-1 $。此外，对于定向的随机图$ {\ cal d}（n，p）$，我们显示的结果与$ {\ cal g}（n，p）$上的$ {\ cal g}（n，p）$类似，并且对于这两种型号，我们都找到了$cε^2 n $连续循环的间隔，该间隔在略微超级挑剔的态度中$ p = \ frac $ p = \ frac $ p = \ frac = \ frac {1+ε} n $。
We study the set ${\cal L}(G)$ of lengths of all cycles that appear in a random $d$-regular $G$ on $n$ vertices for a fixed $d\geq 3$, as well as in Erdős--Rényi random graphs on $n$ vertices with a fixed average degree $c>1$. Fundamental results on the distribution of cycle counts in these models were established in the 1980's and early 1990's, with a focus on the extreme lengths: cycles of fixed length, and cycles of length linear in $n$. Here we derive, for a random $d$-regular graph, the limiting probability that ${\cal L}(G)$ simultaneously contains the entire range $\{\ell,\ldots,n\}$ for $\ell\geq 3$, as an explicit expression $θ_\ell=θ_\ell(d)\in(0,1)$ which goes to $1$ as $\ell\to\infty$. For the random graph ${\cal G}(n,p)$ with $p=c/n$, where $c\geq C_0$ for some absolute constant $C_0$, we show the analogous result for the range $\{\ell,\ldots,(1-o(1))L_{\max}(G)\}$, where $L_{\max}$ is the length of a longest cycle in $G$. The limiting probability for ${\cal G}(n,p)$ coincides with $θ_\ell$ from the $d$-regular case when $c$ is the integer $d-1$. In addition, for the directed random graph ${\cal D}(n,p)$ we show results analogous to those on ${\cal G}(n,p)$, and for both models we find an interval of $c ε^2 n$ consecutive cycle lengths in the slightly supercritical regime $p=\frac{1+ε}n$.
