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

Abstract

We discuss the length L-c,L-n of the longest cycle in a sparse random graph G(n,p), p = c/n, c constant. We show that for large c there exists a function f (c) such that L-c,L-n/n -> f (c) a.s. The function f (c) = 1 - Sigma(infinity)(k=1) p(k)(c)e(-kc) where pk(c) 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). We see immediately that the length of the longest path is also asymptotic to f (c)n w.h.p.