Sparse random graphs: eigenvalues and eigenvectors

DOI10.1002/RSA.20406MaRDI QIDQ4903280zbMATH OpenOpenAlexFDO

Authors Van 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

infinity norm of eigenvectorregular random graphssemi-circular lawsparse random matrix

Mathematics Subject Classification ID

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

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.

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]

Cites work

• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Concentration of the spectral measure for large matrices
• Eigenvectors of Random Graphs: Nodal Domains
• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• Local semicircle law and complete delocalization for Wigner random matrices
• On factors in random graphs
• On the distribution of the roots of certain symmetric matrices
• On the second eigenvalue and random walks in random d-regular graphs
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Random incidence matrices: moments of the spectral density
• Random matrices: The distribution of the smallest singular values
• Random matrices: universality of local eigenvalue statistics
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Random regular graphs of high degree
• Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices
• Some geometric aspects of graphs and their eigenfunctions
• Sparse random matrices: the eigenvalue spectrum revisited
• Sparse regular random graphs: spectral density and eigenvectors
• Spectral techniques applied to sparse random graphs
• 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 Spectra of Random Graphs with Given Expected Degrees

Cited in

(77)

• Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree
• The spectral gap of dense random regular graphs
• The normalized Laplacian spectrum of subdivisions of a graph
• 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
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Emergence of extended states at zero in the spectrum of sparse random graphs
• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Large deviation theorem for zeros of polynomials and Hermitian random matrices
• Partial sum of eigenvalues of random graphs.
• Spectral radii of sparse random matrices
• Exchangeable pairs, switchings, and random regular graphs
• Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs
• The circular law for random regular digraphs
• Local law for eigenvalues of random regular bipartite graphs
• Quantum ergodicity on graphs: from spectral to spatial delocalization
• Quantum ergodicity on large regular graphs
• Entrywise bounds for eigenvectors of random graphs
• 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
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• Circular law for sparse random regular digraphs
• Sparse matrices: convergence of the characteristic polynomial seen from infinity
• Exponential growth of random determinants beyond invariance
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• A limit theorem for scaled eigenvectors of random dot product graphs
• 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
• Random weighted projections, random quadratic forms and random eigenvectors
• 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
• The skew energy of random oriented graphs
• Cycles and eigenvalues of sequentially growing random regular graphs
• Convergence of graphs with intermediate density
• Sparse general Wigner-type matrices: local law and eigenvector delocalization
• Moments of the inverse participation ratio for the Laplacian on finite regular graphs
• The Largest Eigenvalue of Sparse Random Graphs
• Poisson eigenvalue statistics for random Schrödinger operators on regular graphs
• Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
• Asymptotic normality of eigenvectors of a random regular graph [after Ágnes Backhausz and Balázs Szegedy]
• Spectral properties for the Laplacian of a generalized Wigner matrix
• On the singularity of adjacency matrices for random regular digraphs
• Synchronization of Network-Coupled Oscillators with Uncertain Dynamics
• Spectral techniques applied to sparse random graphs
• The circular law for random regular digraphs with random edge weights
• Local semicircle law for random regular graphs
• Structure of eigenvectors of random regular digraphs
• The First Eigenvalue of Random Graphs
• Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs
• Top eigenpair statistics for weighted sparse graphs
• The spectral gap of random regular graphs
• 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
• Distribution of coefficients of rank polynomials for random sparse graphs
• Sparse Hanson-Wright inequalities with applications
• Tree walks and the spectrum of random graphs
• Sparse regular random graphs: spectral density and eigenvectors
• Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions
• Vertex-wise graph's spectral density decomposition and its applications
• Central limit theorem for linear eigenvalue statistics of the adjacency matrices of random simplicial complexes
• Low eigenvalues of Laplacian matrices of large random graphs
• Tree walks and the spectrum of random graphs
• No-gaps delocalization for general random matrices
• Eigenvectors of random matrices: A survey
• On quantum percolation in finite regular graphs
• Delocalization of eigenvectors of random matrices with independent entries
• Vertex-frequency analysis on 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)