We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on recent deep results in combinatorial group theory. It applies to both regular and irregular random graphs. Let Γ be a random d-regular graph on n vertices, and let λ be the largest absolute value of a non-trivial eigenvalue of its adjacency matrix. It was conjectured by Alon [Alo86] that a random d-regular graph is "almost Ramanujan", in the following sense: for every Friedman famously presented a proof of this conjecture in [Fri08]. Here we suggest a new, substantially simpler proof of a nearly-optimal result: we show that a random d-regular graph satisfies λ < 2 √ d − 1 + 1 asymptotically almost surely. A main advantage of our approach is that it is applicable to a generalized conjecture: A d-regular graph on n vertices is an n-covering space of a bouquet of d/2 loops. More generally, fixing an arbitrary base graph Ω, we study the spectrum of Γ, a random n-covering of Ω. Let λ be the largest absolute value of a non-trivial eigenvalue of Γ. Extending Alon's conjecture to this more general model, Friedman [Fri03] conjectured that for every ε > 0, a.a.s. λ < ρ + ε, where ρ is the spectral radius of the universal cover of Ω. When Ω is regular we get the same bound as before: ρ + 1, and for an arbitrary Ω, we prove a nearly optimal upper bound of √ 3ρ. This is a substantial improvement upon all known results (by Friedman, Linial-Puder, Lubetzky-Sudakov-Vu and Addario-Berry-Griffiths).
In the irregular case, Puder REF has shown that with high probability a high-order lift of a graph G has new eigenvalues that are bounded in absolute value by √ 3ρ, where ρ is the spectral radius of the universal cover of G.
Expansion of Random Graphs: New Proofs, New Results
Inventiones Mathematicae 201 (2015), no. 3, 845-908
Mathematics