Sparse regular random graphs: spectral density and eigenvectors

DOI10.1214/11-AOP673MaRDI QIDQ690878zbMATH OpenFDO

Authors Ioana Dumitriu, Soumik Pal

Publication date 29 November 2012

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

Full work available at URL https://arxiv.org/abs/0910.5306, https://projecteuclid.org/euclid.aop/1349703320

zbMATH Keywords

random regular graphssemicircle lawspectral distributionuniversality

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05)

Abstract: We examine the empirical distribution of the eigenvalues and the eigenvectors of adjacency matrices of sparse regular random graphs. We find that when the degree sequence of the graph slowly increases to infinity with the number of vertices, the empirical spectral distribution converges to the semicircle law. Moreover, we prove concentration estimates on the number of eigenvalues over progressively smaller intervals. We also show that, with high probability, all the eigenvectors are delocalized.

Recommendations

• Sparse random graphs: eigenvalues and eigenvectors
• Convergence of the density of states and delocalization of eigenvectors on random regular graphs
• Empirical spectral distributions of sparse random graphs
• Local semicircle law for random regular graphs
• Eigenvector statistics of sparse random matrices

Cites work

• A generalization of the Lindeberg principle
• A proof of Alon’s second eigenvalue conjecture and related problems
• An introduction to random matrices
• Asymptotic properties of large random matrices with independent entries
• Bulk universality for Wigner Hermite matrices with subexponential decay
• Bulk universality for Wigner matrices
• Concentration of the spectral measure for large matrices
• Continued fractions. Vol. 1: Convergence theory
• Convergence rate of expected spectral distributions of large random matrices. I: Wigner matrices
• Eigenvectors of random graphs: nodal domains
• Eigenvectors of the discrete Laplacian on regular graphs—a statistical approach
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Global spectrum fluctuations for the β-Hermite and β-Laguerre ensembles via matrix models
• scientific article; zbMATH DE number 3886886 (Why is no real title available?)
• scientific article; zbMATH DE number 5691097 (Why is no real title available?)
• scientific article; zbMATH DE number 51346 (Why is no real title available?)
• scientific article; zbMATH DE number 1552110 (Why is no real title available?)
• scientific article; zbMATH DE number 2162775 (Why is no real title available?)
• scientific article; zbMATH DE number 1862742 (Why is no real title available?)
• Local semicircle law and complete delocalization for Wigner random matrices
• On asymptotics of eigenvectors of large sample covariance matrix
• On fluctuations of eigenvalues of random Hermitian matrices.
• On the concentration of eigenvalues of random symmetric matrices
• On the convergence of the spectral empirical process of Wigner matrices
• On the second eigenvalue and random walks in random d-regular graphs
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Ramanujan graphs
• Random incidence matrices: moments of the spectral density
• Random matrices: universality of local eigenvalue statistics
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Random matrix central limit theorems for nonintersecting random walks
• Resolvent of large random graphs
• Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices
• Short cycles in random regular graphs
• Some geometric aspects of graphs and their eigenfunctions
• Sparse random graphs: eigenvalues and eigenvectors
• Sparse random matrices; Spectral edge and statistics of rooted trees
• Sparse random matrices: the eigenvalue spectrum revisited
• Spectra of large random trees
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Spectral techniques applied to sparse random graphs
• Symmetric Random Walks on Groups
• The Calogero-Sutherland model and generalized classical polynomials
• The degree sequence of a random graph. I. The models
• The eigenvalues of random symmetric matrices
• The expected eigenvalue distribution of a large regular graph
• The Largest Eigenvalue of Sparse Random Graphs
• Universality at the edge of the spectrum for unitary, orthogonal, and symplectic ensembles of random matrices
• Universality at the edge of the spectrum in Wigner random matrices.
• Universality for generalized Wigner matrices with Bernoulli distribution
• Universality for mathematical and physical systems
• Universality of level correlation function of sparse random matrices
• Universality of local eigenvalue statistics for some sample covariance matrices
• Universality of the distribution functions of random matrix theory

Cited in

(64)

• Eigenvalue location in graphs of small clique-width
• Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree
• The spectral gap of dense random regular graphs
• Size biased couplings and the spectral gap for random regular graphs
• Empirical spectral distributions of sparse random graphs
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• Spectral statistics of sparse Erdős-Rényi graph Laplacians
• Spectral radii of sparse random matrices
• Exchangeable pairs, switchings, and random regular graphs
• Local law for eigenvalues of random regular bipartite graphs
• Quantum ergodicity on graphs: from spectral to spatial delocalization
• Quantum ergodicity on large regular graphs
• On fluctuations of eigenvalues of random permutation matrices
• Eigenvector statistics of sparse random matrices
• On the almost eigenvectors of random regular graphs
• Local Kesten-McKay law for random regular graphs
• Many large eigenvalues in sparse graphs
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• Spectra of large diluted but bushy random graphs
• Use of a Generalized Multivariate Gamma Distribution Based on Copula Functions in the Average Bioequivalence
• On the spectral distribution of large weighted random regular graphs
• Discrepancy properties for random regular digraphs
• Localization in matrix computations: theory and applications
• Remarks on the energy of regular graphs
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Eigenvectors of the discrete Laplacian on regular graphs—a statistical approach
• Functional limit theorems for random regular graphs
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• Cycles and eigenvalues of sequentially growing random regular graphs
• scientific article; zbMATH DE number 1552110 (Why is no real title available?)
• Convergence of graphs with intermediate density
• Moments of the inverse participation ratio for the Laplacian on finite regular graphs
• Spectral properties of the trap model on sparse networks
• The Largest Eigenvalue of Sparse Random Graphs
• On the density of triangles and squares in regular finite and unimodular random graphs
• Sparse random graphs: eigenvalues and eigenvectors
• Poisson eigenvalue statistics for random Schrödinger operators on regular graphs
• Asymptotic normality of eigenvectors of a random regular graph [after Ágnes Backhausz and Balázs Szegedy]
• On the singularity of adjacency matrices for random regular digraphs
• Eigenvector delocalization for non‐Hermitian random matrices and applications
• Synchronization of Network-Coupled Oscillators with Uncertain Dynamics
• The circular law for random regular digraphs with random edge weights
• Local semicircle law for random regular graphs
• Concentration and regularization of random graphs
• Structure of eigenvectors of random regular digraphs
• Spectral experiments+
• Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs
• Top eigenpair statistics for weighted sparse graphs
• Existence of absolutely continuous spectrum for Galton-Watson random trees
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Many nodal domains in random regular graphs
• Localization of eigenvectors in random graphs
• Spectrum of random d‐regular graphs up to the edge
• Spectral gap and edge universality of dense random regular graphs
• Distribution of coefficients of rank polynomials for random sparse graphs
• Bulk eigenvalue statistics for random regular graphs
• Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions
• Randomly twisted hypercubes: between structure and randomness
• Eigenvectors of random matrices: A survey
• On quantum percolation in finite regular graphs
• Vertex-frequency analysis on graphs

This page was built for publication: Sparse regular random graphs: spectral density and eigenvectors

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