Expansion of Random Graphs: New Proofs, New Results
Author:
Preprint
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].Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Functional limit theorems for random regular graphsProbability Theory and Related Fields, 2012
- Word maps and spectra of random graph liftsRandom Structures & Algorithms, 2010
- Lifts, Discrepancy and Nearly Optimal Spectral Gap*Combinatorica, 2006
- Random Lifts Of Graphs: Perfect MatchingsCombinatorica, 2005
- Random Graph Coverings I: General Theory and Graph ConnectivityCombinatorica, 2002
- Random lifts of graphs: Independence and chromatic numberRandom Structures & Algorithms, 2001
- Not Every Uniform Tree Covers Ramanujan GraphsJournal of Combinatorial Theory, Series B, 1998
- Algorithms for Random Generation and Counting: A Markov Chain Approach1993
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- Eigenvalues and expandersCombinatorica, 1986