Edge rigidity and universality of random regular graphs of intermediate degree

DOI10.1007/S00039-020-00538-0zbMATH Open1453.05117arXiv1910.10121OpenAlexW2981994428MaRDI QIDQ2201984FDOQ2201984

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

Publication date: 17 September 2020

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

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$.

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)

Cites Work

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

Cited In (16)

• 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
• 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
• Optimal multi-resolvent local laws for Wigner matrices
• On the largest and the smallest singular value of sparse rectangular random matrices
• The spectral gap of random regular graphs

   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 👍 👎

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)