Functional limit theorems for random regular graphs

• 成果类型: Article
• 署名作者: Dumitriu, Ioana; Johnson, Tobias; Pal, Soumik; Paquette, Elliot
• 署名单位: University of Washington; University of Washington Seattle
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-012-0447-y
• 发表日期: 2013
• 页码: 921-975
• 关键词: random-walks; eigenvalues; fluctuations; statistics; matrices; SPECTRA

摘要

Consider uniformly random permutation matrices on 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 on vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as grows to infinity, either when is kept fixed or grows slowly with . 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 and .