The law of the circumference of sparse binomial random graphs

2025/03/18 by Anastos, Michael, Erde, Joshua, Kang, Mihyun +1 · 1 citation
#05C38 #05C80 #60F05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2503.14336

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 = Θ((1)/(n)). 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.

Cited by

• A short proof of a central limit theorem for the order of the giant component and k-core

Related

• A scaling limit for the length of the longest cycle in a sparse random\n graph
• Cycle lengths in sparse random graphs
• A note on long cycles in sparse random graphs
• An improved lower bound on the length of the longest cycle in random graphs
• The largest hole in sparse random graphs