Edge rigidity and universality of random regular graphs of intermediate degree

DOI10.1007/S00039-020-00538-0MaRDI QIDQ2201984zbMATH OpenOpenAlexFDO

Authors Roland Bauerschmidt, Jiaoyang Huang, Antti Knowles, Horng-Tzer Yau

Publication date 17 September 2020

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

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

zbMATH Keywords

eigenvalue distributionrandom regular graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: For random $d$-regular graphs on $N$ vertices with $1lldll{N}^{2/3}$, we develop a $d^{-1/2}$ expansion of the local eigenvalue distribution about the Kesten-McKay law up to order $d^{-3}$. This result is valid up to the edge of the spectrum. It implies that the eigenvalues of such random regular graphs are more rigid than those of ErdH{o}s-R'enyi graphs of the same average degree. As a first application, for $1lldll{N}^{2/3}$, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by $(2+o(1))sqrtd-1$. As a second application, for $N^{2/9}lldll{N}^{1/3}$, we prove that the extremal eigenvalues are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by Tracy-Widom statistics. Thus, in the same regime of $d$, $52\mathrm{\%}$ of all $d$-regular graphs have second-largest eigenvalue strictly less than $2sqrtd-1$.

Recommendations

• Sharp threshold for rigidity of random graphs
• On the Rigidity of Sparse Random Graphs
• The rigidity transition in random graphs
• On universality of graphs with uniformly distributed edges
• Edge ideals of Erdős-Rényi random graphs: linear resolution, unmixedness and regularity
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• On edge irregularity strength of graphs
• On vertex, edge, and vertex-edge random graphs
• On vertex, edge, and vertex-edge random graphs (extended abstract)
• ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphs

Cites work

• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 6803211 (Why is no real title available?)
• scientific article; zbMATH DE number 2115090 (Why is no real title available?)
• A Dynamical Approach to Random Matrix Theory
• A proof of Alon’s second eigenvalue conjecture and related problems
• A universality result for the smallest eigenvalues of certain sample covariance matrices
• Around the circular law
• Bulk eigenvalue statistics for random regular graphs
• Bulk universality for Wigner matrices
• Bulk universality for generalized Wigner matrices
• Bulk universality of sparse random matrices
• Circular law for the sum of random permutation matrices
• Circular law, extreme singular values and potential theory
• Convergence of local statistics of Dyson Brownian motion
• Eigenvector distribution of Wigner matrices
• Eigenvector statistics of sparse random matrices
• Exchangeable pairs, switchings, and random regular graphs
• Expansion of random graphs: new proofs, new results
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Fixed energy universality for generalized Wigner matrices
• Functional limit theorems for random regular graphs
• Gap universality of generalized Wigner and \(\beta\)-ensembles
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. IV: Bipartite Ramanujan graphs of all sizes
• Isotropic local laws for sample covariance and generalized Wigner matrices
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Local Kesten-McKay law for random regular graphs
• Local law and Tracy-Widom limit for sparse random matrices
• Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs
• Local semicircle law for random regular graphs
• On the almost eigenvectors of random regular graphs
• On the free convolution with a semi-circular distribution
• On the singularity of adjacency matrices for random regular digraphs
• Ramanujan graphs
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Random matrices: universal properties of eigenvectors
• Random matrices: universality of ESDs and the circular law
• Random matrices: universality of local eigenvalue statistics
• Random operators. Disorder effects on quantum spectra and dynamics
• Random regular graphs of high degree
• Rigidity of eigenvalues of generalized Wigner matrices
• Size biased couplings and the spectral gap for random regular graphs
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Spectral statistics of sparse Erdős-Rényi graph Laplacians
• Symmetric Random Walks on Groups
• The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
• The circular law for random matrices
• The circular law for random regular digraphs with random edge weights
• The eigenvector moment flow and local quantum unique ergodicity
• The probability that a random real Gaussian matrix has \(k\) real eigenvalues, related distributions, and the circular law
• The rank of random regular digraphs of constant degree
• The spectral edge of some random band matrices
• The spectral gap of dense random regular graphs
• Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs
• Universality at the edge of the spectrum in Wigner random matrices.
• Universality of random matrices and local relaxation flow
• Universality of sine-kernel for Wigner matrices with a small Gaussian perturbation
• Universality of the local spacing distribution in certain ensembles of Hermitian Wigner matrices
• Universality results for the largest eigenvalues of some sample covariance matrix ensembles

Cited in

(19)

• The spectral gap of random regular graphs
• Quantitative Tracy-Widom laws for the largest eigenvalue of generalized Wigner matrices
• Dyson Brownian motion for general \(\beta\) and potential at the edge
• Spectrum of random d‐regular graphs up to the edge
• Eigenvectors of the square grid plus GUE
• Localized phase for the Erdős-Rényi graph
• Spectral gap and edge universality of dense random regular graphs
• Bernoulli random matrices
• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs
• Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs
• Bulk eigenvalue statistics for random regular graphs
• Rigidity of eigenvalues for \(\beta\) ensemble in multi-cut regime
• Exponential growth of random determinants beyond invariance
• Global eigenvalue fluctuations of random biregular bipartite graphs
• On the second eigenvalue of random bipartite biregular graphs
• The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
• Optimal multi-resolvent local laws for Wigner matrices
• Functional limit theorems for random regular graphs
• On the largest and the smallest singular value of sparse rectangular random matrices

This page was built for publication: Edge rigidity and universality of random regular graphs of intermediate degree

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