Consider random regular graphs of order n and degree d=d(n)≥ 3. Let g=g(n)≥ 3 satisfy (d-1)²ᵍ⁻¹=o(n). Then the number of cycles of lengths up to g have a distribution similar to that of independent Poisson variables. In particular, we find the asymptotic probability that there are no cycles with sizes in a given set, including the probability that the girth is greater than g. A corresponding result is given for random regular bipartite graphs.
No takes yet. Share an insight, caveat, or question.
McKay et al. (2004) studied this question.