Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

DOI10.1002/rsa.20696zbMath1368.05132arXiv1504.07669OpenAlexW822020258MaRDI QIDQ4978431

Tselil Schramm, Miklós Z. Rácz, Ronen Eldan

Publication date: 10 August 2017

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

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

zbMATH Keywords

random graphsspectral gapgraph LaplacianBraess's paradox

Mathematics Subject Classification ID

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

Related Items (6)

Noise sensitivity for the top eigenvector of a sparse random matrix ⋮ On delocalization of eigenvectors of random non-Hermitian matrices ⋮ Spectral dynamics of guided edge removals and identifying transient amplifiers for death-birth updating ⋮ Eigenvector delocalization for non‐Hermitian random matrices and applications ⋮ No-gaps delocalization for general random matrices ⋮ Eigenvectors and controllability of non-Hermitian random matrices and directed graphs

Cites Work

• Unnamed Item
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Random covariance matrices: universality of local statistics of eigenvalues
• Random matrices: universality of local eigenvalue statistics
• On the spectra of general random graphs
• Delocalization of eigenvectors of random matrices with independent entries
• The eigenvalues of random symmetric matrices
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Entrywise bounds for eigenvectors of random graphs
• Braess's Paradox in large random graphs
• Braess's paradox in expanders
• Small Ball Probabilities for Linear Images of High-Dimensional Distributions
• Estimates for the concentration function of combinatorial number theory and probability
• Sparse random graphs: Eigenvalues and eigenvectors
• Eigenvectors of random graphs: Nodal Domains
• Spectra of random graphs with given expected degrees
• Über ein Paradoxon aus der Verkehrsplanung
• On a lemma of Littlewood and Offord

This page was built for publication: Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors