A proof of alon's second eigenvalue conjecture

DOI10.1145/780542.780646zbMath1192.05087OpenAlexW1993418693MaRDI QIDQ3581308

Joel Friedman

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780646

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (42)

High-girth near-Ramanujan graphs with localized eigenvectors ⋮ The expansion and mixing time of skip graphs with applications ⋮ Cutoff on graphs and the Sarnak-Xue density of eigenvalues ⋮ Poisson-Dirichlet distribution for random Belyi surfaces ⋮ The energy of graphs and matrices ⋮ The cover time of a biased random walk on a random cubic graph ⋮ Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey ⋮ Reliable Spanners for Metric Spaces ⋮ Many nodal domains in random regular graphs ⋮ Majority vote in social networks ⋮ Expander graphs and their applications ⋮ A random walk model for infection on graphs: spread of epidemics \& rumours with mobile agents ⋮ Unnamed Item ⋮ The cover time of a biased random walk on a random regular graph of odd degree ⋮ Communication constraints in the average consensus problem ⋮ Kesten's theorem for invariant random subgroups. ⋮ Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems ⋮ Cleaning random \(d\)-regular graphs with brooms ⋮ Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Complexity measures of sign matrices ⋮ The Grothendieck constant of random and pseudo-random graphs ⋮ Community Detection and Stochastic Block Models ⋮ Asymptotically optimal amplifiers for the Moran process ⋮ Sparse universal graphs for bounded‐degree graphs ⋮ Eigenvalues of graphs and a simple proof of a theorem of Greenberg ⋮ \(L^p\)-expander graphs ⋮ The measurable Kesten theorem ⋮ The spectral gap of sparse random digraphs ⋮ Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly ⋮ Spectra of random regular hypergraphs ⋮ On the spread of influence in graphs ⋮ Expansion and Lack Thereof in Randomly Perturbed Graphs ⋮ In a World of P=BPP ⋮ Local law for eigenvalues of random regular bipartite graphs ⋮ Opinion forming in Erdős-Rényi random graph and expanders ⋮ Opinion Forming in Erdös-Rényi Random Graph and Expanders ⋮ More spectral bounds on the clique and independence numbers ⋮ Cutoff on hyperbolic surfaces ⋮ Lower bounds for boxicity ⋮ Graph Powering and Spectral Robustness ⋮ New and explicit constructions of unbalanced Ramanujan bipartite graphs

This page was built for publication: A proof of alon's second eigenvalue conjecture