Sparse random graphs: Eigenvalues and eigenvectors

DOI10.1002/rsa.20406zbMath1257.05089arXiv1011.6646OpenAlexW2042479609MaRDI QIDQ4903280

Van H. Vu, Ke Wang, Linh Viet Tran

Publication date: 21 January 2013

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

semi-circular lawsparse random matrixregular random graphsinfinity norm of eigenvector

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Density (toughness, etc.) (05C42)

Related Items

Remarks on the energy of regular graphs ⋮ Adjacency matrices of random digraphs: singularity and anti-concentration ⋮ Random weighted projections, random quadratic forms and random eigenvectors ⋮ Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs ⋮ Functional limit theorems for random regular graphs ⋮ On the spectral distribution of large weighted random regular graphs ⋮ Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law ⋮ Concentration of the spectral norm of Erdős-Rényi random graphs ⋮ Spectral properties for the Laplacian of a generalized Wigner matrix ⋮ Localization and delocalization of eigenvectors for heavy-tailed random matrices ⋮ The skew energy of random oriented graphs ⋮ Large deviation theorem for zeros of polynomials and Hermitian random matrices ⋮ Cycles and eigenvalues of sequentially growing random regular graphs ⋮ Discrepancy properties for random regular digraphs ⋮ On quantum percolation in finite regular graphs ⋮ The spectral gap of random regular graphs ⋮ Local Kesten-McKay law for random regular graphs ⋮ On the limiting spectral distributions of stochastic block models ⋮ Spectrum of random d‐regular graphs up to the edge ⋮ The circular law for random regular digraphs with random edge weights ⋮ Delocalization of eigenvectors of random matrices with independent entries ⋮ Exponential growth of random determinants beyond invariance ⋮ Vertex-frequency analysis on graphs ⋮ Convergence of graphs with intermediate density ⋮ Localization in Matrix Computations: Theory and Applications ⋮ Structure of eigenvectors of random regular digraphs ⋮ Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree ⋮ Sparse general Wigner-type matrices: Local law and eigenvector delocalization ⋮ Moments of the inverse participation ratio for the Laplacian on finite regular graphs ⋮ The spectral gap of dense random regular graphs ⋮ The normalized Laplacian spectrum of subdivisions of a graph ⋮ Poisson eigenvalue statistics for random Schrödinger operators on regular graphs ⋮ Empirical spectral distributions of sparse random graphs ⋮ On the singularity of adjacency matrices for random regular digraphs ⋮ Size biased couplings and the spectral gap for random regular graphs ⋮ Sparse regular random graphs: spectral density and eigenvectors ⋮ Exchangeable pairs, switchings, and random regular graphs ⋮ The random transposition dynamics on random regular graphs and the Gaussian free field ⋮ Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs ⋮ The Marčenko-Pastur law for sparse random bipartite biregular graphs ⋮ No-gaps delocalization for general random matrices ⋮ Synchronization of Network-Coupled Oscillators with Uncertain Dynamics ⋮ Extremal eigenvalues of critical Erdős-Rényi graphs ⋮ Emergence of extended states at zero in the spectrum of sparse random graphs ⋮ The circular law for random regular digraphs ⋮ Eigenvectors of random matrices: A survey ⋮ Local law for eigenvalues of random regular bipartite graphs ⋮ Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors ⋮ Quantum ergodicity on graphs: from spectral to spatial delocalization ⋮ Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős–Rényi random graphs ⋮ Quantum ergodicity on large regular graphs ⋮ Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs ⋮ Top eigenpair statistics for weighted sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Random matrices: universality of local eigenvalue statistics
• Sparse regular random graphs: spectral density and eigenvectors
• Local semicircle law and complete delocalization for Wigner random matrices
• On the distribution of the roots of certain symmetric matrices
• Random matrices: The distribution of the smallest singular values
• The expected eigenvalue distribution of a large regular graph
• On factors in random graphs
• The eigenvalues of random symmetric matrices
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Some geometric aspects of graphs and their eigenfunctions
• Rate of convergence to the semi-circular law
• Concentration of the spectral measure for large matrices
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices
• Random regular graphs of high degree
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Eigenvectors of Random Graphs: Nodal Domains
• The degree sequence of a random graph. I. The models
• Sparse random matrices: the eigenvalue spectrum revisited
• The Spectra of Random Graphs with Given Expected Degrees
• Spectral techniques applied to sparse random graphs
• Random incidence matrices: moments of the spectral density