The law of the circumference of sparse binomial random graphs

Abstract

There has been much interest in the distribution of the circumference, the length of the longest cycle, of a random graph $G(n,p)$ in the sparse regime, when $p=\Theta \left(\frac{1}{n}\right)$. Recently, the first author and Frieze established a scaling limit for the circumference in this regime, along the way establishing an alternative 'structural' approximation for this parameter. In this paper, we give a central limit theorem for the circumference in this regime using a novel argument based on the Efron-Stein inequality, which relies on a combinatorial analysis of the effect of resampling edges on this approximation.

48 pages + 19-page appendix