Spectral gaps of random graphs and applications to random topology
Christopher Hoffman, Matthew Kahle, Elliot Paquette · arXiv (Cornell University) · 2012
We prove that for delta > 0, if p > (1/2 + delta) log n / n, then the normalized Laplacian of an Erdos-Renyi random graph has its nonzero eigenvalues tightly concentrated around 1. We also give sharp estimates for the concentration of the eigenvalues. This extends earlier work on spectra of random graphs into and through the threshold for connectivity. These new spectral results establish the existence of several sharp thresholds in random topology and geometric group theory. In particular, we show that the threshold for the fundamental group of random 2-complexes to have Kazhdan's property (T) agrees with the homology-vanishing threshold found earlier by Linial and Meshulam.