Eigenvectors of random graphs: Nodal Domains

DOI10.1002/rsa.20330zbMath1223.05275arXiv0807.3675OpenAlexW2166207749MaRDI QIDQ5198670

James R. Lee, Nathan Linial, Yael Dekel

Publication date: 9 August 2011

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

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

zbMATH Keywords

eigenvectorsrandom graphsspectral analysis

Mathematics Subject Classification ID

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

Related Items

Principal eigenvector localization and centrality in networks: revisited ⋮ Random weighted projections, random quadratic forms and random eigenvectors ⋮ Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law ⋮ Geodesic geometry on graphs ⋮ Many nodal domains in random regular graphs ⋮ Vertex-frequency analysis on graphs ⋮ Localization in Matrix Computations: Theory and Applications ⋮ Eigenvector delocalization for non‐Hermitian random matrices and applications ⋮ Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree ⋮ Moments of the inverse participation ratio for the Laplacian on finite regular graphs ⋮ Eigenvectors of random matrices of symmetric entry distributions ⋮ Random matrices: tail bounds for gaps between eigenvalues ⋮ Maximizing the algebraic connectivity of meshed electrical pathways used as current return network ⋮ Sparse regular random graphs: spectral density and eigenvectors ⋮ Spectral Experiments+ ⋮ No-gaps delocalization for general random matrices ⋮ Recent progress in combinatorial random matrix theory ⋮ On the distribution of local extrema in quantum chaos ⋮ Eigenvectors and controllability of non-Hermitian random matrices and directed graphs ⋮ Eigenvectors of random matrices: A survey ⋮ Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors ⋮ Tail bounds for gaps between eigenvalues of sparse random matrices

Cites Work

• Random symmetric matrices are almost surely nonsingular.
• The eigenvalues of random symmetric matrices
• Approximating the independence number and the chromatic number in expected polynomial time
• On the concentration of eigenvalues of random symmetric matrices
• Invertibility of random matrices: norm of the inverse
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Smallest singular value of random matrices and geometry of random polytopes
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Expander graphs and their applications
• Nodal domains on graphs - How to count them and why?
• A Panoramic View of Riemannian Geometry
• Euclidean embeddings in spaces of finite volume ratio via random matrices
• Discrete nodal domain theorems
• Unnamed Item