论文标题
稀疏随机挖掘中最长循环长度的缩放限制
A scaling limit for the length of the longest cycle in a sparse random digraph
论文作者
论文摘要
我们讨论了稀疏随机挖掘$ d_ {n，p}中最长的定向周期的长度$ \ vec {l} _ {c，n} $，p = c/n $，$ c $ constant。我们表明，对于大$ c $，存在一个函数$ \ vec {f}（c）$，这样$ \ vec {l} _ {c，n}/n \ to \ to \ vec {f}（c）$ a.s.功能$ \ vec {f}（c）= 1- \ sum_ {k = 1}^\ infty p_k（c）e^{ - kc} $，其中$ p_k $是$ c $的多项式。尽管我们可以原则上计算任何$ p_k $，但我们只能明确地给出$ p_1，p_2 $的值。
We discuss the length $\vec{L}_{c,n}$ of the longest directed cycle in the sparse random digraph $D_{n,p},p=c/n$, $c$ constant. We show that for large $c$ there exists a function $\vec{f}(c)$ such that $\vec{L}_{c,n}/n\to \vec{f}(c)$ a.s. The function $\vec{f}(c)=1-\sum_{k=1}^\infty p_k(c)e^{-kc}$ where $p_k$ is a polynomial in $c$. We are only able to explicitly give the values $p_1,p_2$, although we could in principle compute any $p_k$.
