Spectral gaps of random graphs and applications

Christopher Hoffman, Matthew Kahle, Elliot Paquette

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 + δ) \log n}{n…