A scaling limit for the length of the longest cycle in a sparse random digraph. Issue 1 (14th June 2021) - Anastos, Michael; Frieze, Alan
Abstract: We discuss the length 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 f → ( c ) such that L → c, n / n → f → ( c ) a.s. The function f → ( c ) = 1 − ∑ k = 1 ∞ p k ( c ) e − k c 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 .