Sparse random graphs: eigenvalues and eigenvectors

DOI10.1002/RSA.20406zbMATH Open1257.05089arXiv1011.6646OpenAlexW2042479609MaRDI QIDQ4903280FDOQ4903280

Authors: Van Vu, Ke Wang, Linh Viet Tran 

Publication date: 21 January 2013

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

Abstract: In this paper we prove the semi-circular law for the eigenvalues of regular random graph $G_{n,d}$ in the case $dightarrowinfty$, complementing a previous result of McKay for fixed $d$. We also obtain a upper bound on the infinity norm of eigenvectors of ErdH{o}s-R'enyi random graph $G(n,p)$, answering a question raised by Dekel-Lee-Linial.

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

Recommendations

• Sparse regular random graphs: spectral density and eigenvectors
• Local semicircle law for random regular graphs
• The Largest Eigenvalue of Sparse Random Graphs
• Spectral radii of sparse random matrices
• Asymptotic normality of eigenvectors of a random regular graph [after Ágnes Backhausz and Balázs Szegedy]

zbMATH Keywords

semi-circular lawsparse random matrixregular random graphsinfinity norm of eigenvector

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (60)

• On the limiting spectral distributions of stochastic block models
• Spectrum of random d‐regular graphs up to the edge
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• On quantum percolation in finite regular graphs
• Emergence of extended states at zero in the spectrum of sparse random 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
• The spectral gap of dense random regular graphs
• The Largest Eigenvalue of Sparse Random Graphs
• Spectral properties for the Laplacian of a generalized Wigner matrix
• Empirical spectral distributions of sparse random graphs
• Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
• The circular law for random regular digraphs with random edge weights
• Local law for eigenvalues of random regular bipartite graphs
• Moments of the inverse participation ratio for the Laplacian on finite regular graphs
• Sparse general Wigner-type matrices: Local law and eigenvector delocalization
• Local Kesten-McKay law for random regular graphs
• Top eigenpair statistics for weighted sparse graphs
• Convergence of graphs with intermediate density
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• Quantum ergodicity on graphs: from spectral to spatial delocalization
• The First Eigenvalue of Random Graphs
• Localization in Matrix Computations: Theory and Applications
• 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
• Discrepancy properties for random regular digraphs
• The skew energy of random oriented graphs
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Eigenvectors of random matrices: A survey
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Sparse regular random graphs: spectral density and eigenvectors
• The circular law for random regular digraphs
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős–Rényi random graphs
• Exponential growth of random determinants beyond invariance
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• No-gaps delocalization for general random matrices
• Delocalization of eigenvectors of random matrices with independent entries
• Large deviation theorem for zeros of polynomials and Hermitian random matrices
• Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree
• Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs
• Sparse matrices: convergence of the characteristic polynomial seen from infinity
• Quantum ergodicity on large regular graphs
• Entrywise bounds for eigenvectors of random graphs
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Spectral techniques applied to sparse random graphs
• Functional limit theorems for random regular graphs
• On the singularity of adjacency matrices for random regular digraphs
• Size biased couplings and the spectral gap for random regular graphs
• The normalized Laplacian spectrum of subdivisions of a graph
• On the spectral distribution of large weighted random regular graphs
• Random weighted projections, random quadratic forms and random eigenvectors
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Synchronization of Network-Coupled Oscillators with Uncertain Dynamics
• Distribution of coefficients of rank polynomials for random sparse graphs
• Poisson eigenvalue statistics for random Schrödinger operators on regular graphs
• The spectral gap of random regular graphs

This page was built for publication: Sparse random graphs: eigenvalues and eigenvectors

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