A scaling limit for the length of the longest cycle in a sparse random digraph

Abstract

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$.

arXiv admin note: substantial text overlap with arXiv:1907.03657