Abstract
We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on deep results from Combinatorial Group Theory. It applies both to regular and irregular random graphs. Let G be a random d-regular graph on n vertices, and let \lambda_ be the largest absolute value of a non-trivial eigenvalue of its adjacency matrix. It was conjectured by Alon (86') that for every \epsilon>0, most d-regular graphs satisfy \lambda < 2\sqrt(d-1) + e. Friedman (08') famously presented a proof of this conjecture. Here we suggest a new, substantially simpler proof of a nearly-optimal result: we show that for d even, a random d-regular graph satisfies \lambda < 2\sqrt{d-1} + 1 asymptotically almost surely. A random d-regular graph on n vertices in the permutation model is, in fact, a random n-covering space of a bouquet of d/2 loops. More generally, fixing an arbitrary base graph H, we study the spectrum of G, a random n-covering of H. Let \lambda_ be the largest absolute value of a non-trivial eigenvalue of G. Extending Alon's conjecture to this more general model, Friedman (03') conjectured that for every \epsilon>0, a.a.s. \lambda < \rho + e, where \rho_ is the spectral radius of the universal cover of H. Here we prove a nearly optimal upper bound of \sqrt{3}\rho. This is a substantial improvement upon all known results ([Fri03, LP10, LSV11, AbG10]). The techniques and results from combinatorial group theory which underlie the proofs come mainly from [Pud11] and [PP12].

This publication has 17 references indexed in Scilit: