Spectral gaps of random graphs and applications

////////////////////////////////////////////

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 \ER graph has all of its nonzero eigenvalues tightly concentrated around $1$. This is a strong expander property. 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 method \cite{Garland}, a kind of spectral geometry for simplicial complexes. The following can all be considered to be higher-dimensional expander properties. First, we exhibit a sharp threshold for the fundamental group of the Bernoulli random $2$-complex to have Kazhdan's property (T). We also obtain slightly more information and can describe the large-scale structure of the group just before the (T) threshold. In this regime, the random fundamental group is with high probability the free product of a (T) group with a free group, where the free group has one generator for every isolated edge. The (T) group plays a role analogous to that of a ``giant component'' in percolation theory. Next, we give a new, short, self-contained proof of the Linial--Meshulam--Wallach theorem \cite{LM06,MW09}, identifying the cohomology-vanishing threshold of Bernoulli random $d$-complexes. Since we use spectral techniques, it only holds for $\Q$ or $\R$ coefficients rather than finite field coefficients, as in \cite{LM06} and \cite{MW09}. But it is sharp from a probabilistic point of view, providing for example, hitting time type results and limiting Poisson distributions inside the critical window. It is also a new method of proof, circumventing the combinatorial complications of cocycle counting. Similarly, results in an earlier preprint version of this article were already applied in \cite{flag} to obtain sharp cohomology-vanishing thresholds in every dimension for the random flag complex model.