ÍâÍøÌìÌÃ

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 to both regular and irregular random graphs.Ìý Let G be a random d-regular graph on n vertices. It was conjectured by Alon (86) and provedÌýby Friedman (08) in a ~100 page-long booklet that the highest non-trivialÌýeigenvalue of G is a.a.s. arbitrarily close to 2\sqrt(d-1). We give a new, substantiallyÌýsimpler proof, that nearly recovers Friedman’s result. This approach also has theÌýadvantage of applying to a more general model of random graphs, concerning alsoÌýnon-regular graphs. Friedman (2003) extended Alon’s conjecture to thisÌýgeneral case, and we obtain new, nearly optimal results here too.