Exchangeable Pairs, Switchings, and Random Regular Graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2015-02, Vol.22 (1)
Main Author: Johnson, Tobias
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1077-8926
1077-8926
DOI:10.37236/4659