Functional limit theorems for random regular graphs

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édi argument for estimating the second largest eigenvalue for all values of d and n.

Added Remark 27. 39 pages. To appear in Probability Theory and Related Fields

References in corpus (4)

• Central limit theorem for linear eigenvalue statistics of random matrices with independent entries
• Exchangeable pairs and Poisson approximation
• Random matrices, non-backtracking walks, and orthogonal polynomials
• Sparse random graphs: Eigenvalues and Eigenvectors

Cited by in corpus (18)

• Expansion of Random Graphs: New Proofs, New Results
• Local Kesten--McKay law for random regular graphs
• Local semicircle 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
• Central limit theorems for linear statistics of heavy tailed random matrices
• Edge rigidity and universality of random regular graphs of intermediate degree
• Exchangeable pairs, switchings, and random regular graphs
• Cycles and eigenvalues of sequentially growing random regular graphs
• Sparse random tensors: Concentration, regularization and applications
• 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
• Dense random regular digraphs: singularity of the adjacency matrix
• Eigenvalue fluctuations for random regular graphs
• Quantitative Small Subgraph Conditioning
• Reliable Spanners for Metric Spaces