Spectral Gaps of Random Graphs and Applications
Spectral Gaps of Random Graphs and Applications
We study the spectral gap of the Erd\H{o}s--R\'enyi 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\H{o}s--R\'enyi graph has all of its nonzero eigenvalues tightly concentrated …