The spectral gap of random regular graphs

DOI10.1002/rsa.21150zbMath1525.05174arXiv2201.02015OpenAlexW4365149007MaRDI QIDQ6076727

Amir Sarid

Publication date: 17 October 2023

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

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

zbMATH Keywords

eigenvalueFourier analysisspectral gaprandom regular graphsrandom matrixexpander

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random matrices (algebraic aspects) (15B52) Expander graphs (05C48)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expansion of random graphs: new proofs, new results
• On the distribution of the roots of certain symmetric matrices
• Small subgraphs of random regular graphs
• Explicit construction of linear sized tolerant networks
• Eigenvalues and expanders
• The expected eigenvalue distribution of a large regular graph
• The eigenvalues of random symmetric matrices
• On the second eigenvalue of a graph
• The spectral gap of dense random regular graphs
• Size biased couplings and the spectral gap for random regular graphs
• On the concentration of eigenvalues of random symmetric matrices
• Edge rigidity and universality of random regular graphs of intermediate degree
• Subgraphs of Dense Random Graphs with Specified Degrees
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A proof of Alon’s second eigenvalue conjecture and related problems
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Sparse random graphs: Eigenvalues and eigenvectors
• Analysis of Boolean Functions
• Spectral norm of random matrices