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

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)

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

• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• 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
• 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 up to the edge
• Random matrices: universality of local eigenvalue statistics
• 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 Spectra of Random Graphs with Given Expected Degrees
• 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

Cited in

(70)

• Spectral properties for the Laplacian of a generalized Wigner matrix
• Sparse matrices: convergence of the characteristic polynomial seen from infinity
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Spectrum of random d‐regular graphs up to the edge
• On the spectral distribution of large weighted random regular graphs
• On the limiting spectral distributions of stochastic block models
• The spectral gap of random regular graphs
• Exponential growth of random determinants beyond invariance
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices
• Top eigenpair statistics for weighted sparse graphs
• A limit theorem for scaled eigenvectors of random dot product graphs
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Quantum ergodicity on graphs: from spectral to spatial delocalization
• On quantum percolation in finite regular graphs
• The spectral gap of dense random regular graphs
• Entrywise bounds for eigenvectors of random graphs
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Asymptotic normality of eigenvectors of a random regular graph [after Ágnes Backhausz and Balázs Szegedy]
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Discrepancy properties for random regular digraphs
• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• Poisson eigenvalue statistics for random Schrödinger operators on regular graphs
• The skew energy of random oriented graphs
• Empirical spectral distributions of sparse random graphs
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• The circular law for random regular digraphs with random edge weights
• Quantum ergodicity on large regular graphs
• Size biased couplings and the spectral gap for random regular graphs
• The normalized Laplacian spectrum of subdivisions of a graph
• The Largest Eigenvalue of Sparse Random Graphs
• Circular law for sparse random regular digraphs
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Structure of eigenvectors of random regular digraphs
• Local law for eigenvalues of random regular bipartite graphs
• Sparse general Wigner-type matrices: local law and eigenvector delocalization
• Sparse regular random graphs: spectral density and eigenvectors
• Spectral techniques applied to sparse random graphs
• Cycles and eigenvalues of sequentially growing random regular graphs
• Spectral radii of sparse random matrices
• Synchronization of Network-Coupled Oscillators with Uncertain Dynamics
• Eigenvectors of random matrices: A survey
• Functional limit theorems for random regular graphs
• Localization in matrix computations: theory and applications
• Many large eigenvalues in sparse graphs
• The First Eigenvalue of Random Graphs
• Distribution of coefficients of rank polynomials for random sparse graphs
• Convergence of graphs with intermediate density
• Moments of the inverse participation ratio for the Laplacian on finite regular graphs
• Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
• Random weighted projections, random quadratic forms and random eigenvectors
• Local semicircle law for random regular graphs
• 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
• Large deviation theorem for zeros of polynomials and Hermitian random matrices
• The circular law for random regular digraphs
• Low eigenvalues of Laplacian matrices of large random graphs
• Remarks on the energy of regular graphs
• Eigenvector statistics of sparse random matrices
• Adjacency matrices of random digraphs: singularity and anti-concentration
• On the almost eigenvectors of random regular graphs
• Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs
• No-gaps delocalization for general random matrices
• Local Kesten-McKay law for random regular graphs
• Exchangeable pairs, switchings, and random regular graphs
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• Emergence of extended states at zero in the spectrum of sparse random graphs
• On the singularity of adjacency matrices for random regular digraphs
• 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)