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 $$\begin{equation*} p \geq \frac{(1/2 + \delta) \log n}{n}, \end{equation*}$$then the normalized graph Laplacian of an Erdős–Rényi 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 [24], 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 [35, 39], identifying the cohomology-vanishing threshold of Bernoulli random $d$-complexes. Since we use spectral techniques, it only holds for $\mathbb{Q}$ or $\mathbb{R}$ coefficients rather than finite field coefficients, as in [35] and [39]. However, 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 [33] to obtain sharp cohomology-vanishing thresholds in every dimension for the random flag complex model.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- May 01, 2019
- Source ID
- 10.1093/imrn/rnz077
Entities
People
- Christopher M. Hoffman
- Elliot Paquette
- Matthew Kahle
Organizations
- Alfred P. Sloan Foundation
- American Mathematical Society
- Defense Advanced Research Projects Agency
- National Science Foundation
- National Security Agency
- Ohio State University
- University of Washington