Functional limit theorems for random regular graphs
Preprint
Abstract
Consider d uniformly random permutation matrices on n labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree 2d on n vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as n grows to infinity, either when d is kept fixed or grows slowly with n. In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein's method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn-Szemer\'edi argument for estimating the second largest eigenvalue for all values of d and n.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Sparse random graphs: Eigenvalues and eigenvectorsRandom Structures & Algorithms, 2012
- Spectra of lifted Ramanujan graphsAdvances in Mathematics, 2011
- Word maps and spectra of random graph liftsRandom Structures & Algorithms, 2010
- Fluctuations of eigenvalues and second order Poincaré inequalitiesProbability Theory and Related Fields, 2007
- Concentration of measure and logarithmic Sobolev inequalities1999
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- Some limit theorems for the eigenvalues of a sample covariance matrixJournal of Multivariate Analysis, 1982
- [52–2] On Certain Hermitian Forms Associated with the Fourier Series of a Positive Function1982
- The expected eigenvalue distribution of a large regular graphLinear Algebra and its Applications, 1981
- The eigenvalues of random symmetric matricesCombinatorica, 1981