Short Cycles in Random Regular Graphs

Source abstract

Consider random regular graphs of order $n$ and degree $d=d(n)\ge 3$. Let $g=g(n)\ge 3$ satisfy $(d-1)^{2g-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.