Exchangeable pairs, switchings, and random regular graphs
The electronic journal of combinatorics, Tome 22 (2015) no. 1
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 statistics 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.
DOI :
10.37236/4659
Classification :
05C80, 60B10, 60B20
Mots-clés : switchings, Stein's method, exchangeable pairs, random regular graphs, linear eigenvalue statistics
Mots-clés : switchings, Stein's method, exchangeable pairs, random regular graphs, linear eigenvalue statistics
Affiliations des auteurs :
Tobias Johnson 1
@article{10_37236_4659,
author = {Tobias Johnson},
title = {Exchangeable pairs, switchings, and random regular graphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4659},
zbl = {1307.05205},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4659/}
}
Tobias Johnson. Exchangeable pairs, switchings, and random regular graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4659
Cité par Sources :