Cycles and eigenvalues of sequentially growing random regular graphs

DOI10.1214/13-AOP864MaRDI QIDQ400565zbMATH OpenFDO

Authors Tobias Johnson, Soumik Pal

Publication date 22 August 2014

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

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

zbMATH Keywords

Chinese restaurant processeigenvalue fluctuationsminors of random matricesrandom regular graphs

Mathematics Subject Classification ID

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

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.

Review text

The authors consider random regular (multi-)graphs defined by the incidence matrices obtained as the sum of \(d\) i.i.d. random permutation matrices on \(n\) labels along with their transposes. They explore the joint asymptotic fluctuation for a coupling of all random regular graphs of various degrees constructed in such a way that each component permutation grows according to the Chinese restaurant process. Among other results, the authors prove that one can express the corresponding eigenvalue statistics in terms of a family of independent Yule processes with immigration. It is also observed that some GFF-like processes emerge when \(d\rightarrow \infty\).

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

Cites work

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

Cited in

(7)

• Interlacing adjacent levels of \(\beta\)-Jacobi corners processes
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Exchangeable pairs, switchings, and random regular graphs
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• Functional limit theorems for random regular graphs
• Spectra of overlapping Wishart matrices and the Gaussian free field
• Eigenvalues of random signed graphs with cycles: a graph-centered view of the method of moments with practical applications

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)