Spectral gaps of random graphs and applications

Abstract

We study the spectral gap of the Erdős--Rényi random graph through the connectivity threshold. In particular, we show that for any fixed $\delta >0$ if $$p\ge \frac{(1/2+\delta )\log n}{n},$$ then the normalized graph Laplacian of an Erdős--Rényi graph has all of its nonzero eigenvalues tightly concentrated around $1$. We estimate both the decay rate of the spectral gap to $1$ and the failure probability, up to a constant factor. We also show that the $1/2$ in the above is optimal, and that if $p=\frac{c\log n}{n}$ for $c<1/2,$ then there are eigenvalues of the Laplacian restricted to the giant component that are separated from $1.$ We then describe several applications of our spectral gap results to stochastic topology and geometric group theory. These all depend on Garland's "p-adic curvature" method, a kind of spectral geometry for simplicial complexes. These can all be considered to be high-dimensional expander properties.

final version, 38 pages

References in corpus (5)

• Spectral Statistics of Erd{\H o}s-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues
• Isoperimetric Inequalities in Simplicial Complexes
• Freiheitssatz and phase transition for the density model of random groups
• Random triangular groups at density 1/3
• Random graph products of finite groups are rational duality groups

Cited by in corpus (6)

• What are higher-order networks?
• Low Precision Decentralized Distributed Training over IID and non-IID Data
• Banach space actions and $L^2$-spectral gap
• On the second eigenvalue of random bipartite biregular graphs
• Blind Graph Matching Using Graph Signals
• CO-DEFEND: Continuous Decentralized Federated Learning for Secure DoH-Based Threat Detection