Cycles and eigenvalues of sequentially growing random regular graphs

DOI10.1214/13-AOP864zbMATH Open1355.60012arXiv1203.1113MaRDI QIDQ400565FDOQ400565

Soumik Pal, Tobias Johnson

Publication date: 22 August 2014

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: Consider the sum of $d$ many i.i.d. random permutation matrices on $n$ labels along with their transposes. The resulting matrix is the adjacency matrix of a random regular (multi)-graph of degree $2d$ on $n$ vertices. It is known that the distribution of smooth linear eigenvalue statistics of this matrix is given asymptotically by sums of Poisson random variables. This is in contrast with Gaussian fluctuation of similar quantities in the case of Wigner matrices. It is also known that for Wigner matrices the joint fluctuation of linear eigenvalue statistics across minors of growing sizes can be expressed in terms of the Gaussian Free Field (GFF). In this article, we explore joint asymptotic (in $n$) fluctuation for a coupling of all random regular graphs of various degrees obtained by growing each component permutation according to the Chinese Restaurant Process. Our primary result is that the corresponding eigenvalue statistics can be expressed in terms of a family of independent Yule processes with immigration. These processes track the evolution of short cycles in the graph. If we now take $d$ to infinity, certain GFF-like properties emerge.

Full work available at URL: https://arxiv.org/abs/1203.1113

Recommendations

• The random transposition dynamics on random regular graphs and the Gaussian free field
• Functional limit theorems for random regular graphs
• scientific article; zbMATH DE number 1335045
• Bulk eigenvalue statistics for random regular graphs
• On the almost eigenvectors of random regular graphs

zbMATH Keywords

Chinese restaurant processrandom regular graphsminors of random matriceseigenvalue fluctuations

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Gaussian free fields for mathematicians
• Title not available (Why is that?)
• Anisotropic growth of random surfaces in \({2+1}\) dimensions
• Eigenvalues of GUE minors
• CLT for spectra of submatrices of Wigner random matrices
• Title not available (Why is that?)
• Strong stationary times via a new form of duality
• Title not available (Why is that?)
• Sparse random graphs: Eigenvalues and eigenvectors
• Sparse regular random graphs: spectral density and eigenvectors
• Trace formulae and spectral statistics for discrete Laplacians on regular graphs (I)
• The cycle structure of random permutations
• CLT for spectra of submatrices of Wigner random matrices II. Stochastic evolution
• Beta-gamma random variables and intertwining relations between certain Markov processes
• Harmonic analysis on the infinite symmetric group
• Eigenvalue distributions of random permutation matrices.
• Word maps and spectra of random graph lifts
• Functional limit theorems for random regular graphs
• A Unitary Extension of Virtual Permutations
• On the partial connection between random matrices and interacting particle systems
• On fluctuations of eigenvalues of random permutation matrices
• Percolating level sets of the adjacency eigenvectors ofd-regular graphs
• Eigenvectors of the discrete Laplacian on regular graphs—a statistical approach
• The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
• Trace formulas and spectral statistics for discrete Laplacians on regular graphs (II)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Dyson Brownian minor process

Cited In (5)

• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• Interlacing adjacent levels of \(\beta\)-Jacobi corners processes
• Exchangeable pairs, switchings, and random regular graphs
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Spectra of overlapping Wishart matrices and the Gaussian free field

This page was built for publication: Cycles and eigenvalues of sequentially growing random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q400565)