Sparse random matrices have simple spectrum

DOI10.1214/19-AIHP1032zbMath1465.60011arXiv1802.03662OpenAlexW3093563430MaRDI QIDQ2028938

Kyle Luh, Van H. Vu

Publication date: 3 June 2021

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

zbMATH Keywords

random matricesrandom graphssparse matricesgraph isomorphismeigenvalue degeneracy

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Random matrices (algebraic aspects) (15B52) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

On the smallest singular value of symmetric random matrices ⋮ Noise sensitivity for the top eigenvector of a sparse random matrix ⋮ Zero-free neighborhoods around the unit circle for Kac polynomials ⋮ Random Toeplitz matrices: The condition number under high stochastic dependence ⋮ Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks ⋮ Eigenvectors and controllability of non-Hermitian random matrices and directed graphs ⋮ Tail bounds for gaps between eigenvalues of sparse random matrices ⋮ Controllability of Network Opinion in Erdös--Rényi Graphs Using Sparse Control Inputs

Cites Work

• Unnamed Item
• A mathematical introduction to compressive sensing
• Extreme gaps between eigenvalues of random matrices
• The asymptotic distribution of a single eigenvalue gap of a Wigner matrix
• Gap universality of generalized Wigner and \(\beta\)-ensembles
• Invertibility of sparse non-Hermitian matrices
• Random matrices: tail bounds for gaps between eigenvalues
• Random matrices: universality of local eigenvalue statistics
• Optimal inverse Littlewood-Offord theorems
• Random matrices have simple spectrum
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The Littlewood-Offord problem and invertibility of random matrices
• A sparse Johnson
• Dictionary Learning With Few Samples and Matrix Concentration
• Low-Rank Approximation and Regression in Input Sparsity Time
• Wegner Estimate and Level Repulsion for Wigner Random Matrices
• Graph isomorphism in quasipolynomial time [extended abstract]
• Image Super-Resolution Via Sparse Representation
• Invertibility of symmetric random matrices

This page was built for publication: Sparse random matrices have simple spectrum