Exchangeable pairs, switchings, and random regular graphs

Abstract

We consider the distribution of cycle counts in a random regular graph, which is closely linked to the graph's spectral properties. We broaden the asymptotic regime in which the cycle counts are known to be approximately Poisson, and we give an explicit bound in total variation distance for the approximation. Using this result, we calculate limiting distributions of linear eigenvalue functionals for random regular graphs. Previous results on the distribution of cycle counts by McKay, Wormald, and Wysocka (2004) used the method of switchings, a combinatorial technique for asymptotic enumeration. Our proof uses Stein's method of exchangeable pairs and demonstrates an interesting connection between the two techniques.

Very minor changes; 23 pages

References in corpus (3)

• Exchangeable pairs and Poisson approximation
• Functional limit theorems for random regular graphs
• Cycles and eigenvalues of sequentially growing random regular graphs

Cited by in corpus (10)

• Local Kesten--McKay law for random regular graphs
• Finite size correction to the spectrum of regular random graphs: an analytical solution
• Size biased couplings and the spectral gap for random regular graphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• Imaginary replica analysis of loopy regular random graphs
• Spectrum of Random $d$-regular Graphs Up to the Edge
• On the second eigenvalue of random bipartite biregular graphs
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Eigenvalue fluctuations for random regular graphs