Sparse regular random graphs: spectral density and eigenvectors

DOI10.1214/11-AOP673zbMATH Open1255.05173arXiv0910.5306MaRDI QIDQ690878FDOQ690878

Authors: Ioana Dumitriu, Soumik Pal 

Publication date: 29 November 2012

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

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.

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

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

zbMATH Keywords

spectral distributionuniversalityrandom regular graphssemicircle law

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (61)

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

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)