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

Abstract

We discuss the length L -> c,n of the longest directed cycle in the sparse random digraph Dn,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- n-ary sumation k=1 infinity pk(c)e-kc where pk is a polynomial in c. We are only able to explicitly give the values p1,p2, although we could in principle compute any pk.