Expansion of random graphs: new proofs, new results

• 成果类型: Article
• 署名作者: Puder, Doron
• 署名单位: Hebrew University of Jerusalem
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-014-0560-x
• 发表日期: 2015
• 页码: 845-908
• 关键词: counting primitive elements; random lifts; 2nd eigenvalue; random-walks; coverings; families; SPECTRA

摘要

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 -regular graph on vertices, and let be the largest absolute value of a non-trivial eigenvalue of its adjacency matrix. It was conjectured by Alon (Combinatorica 6(2), 83-96, 1986) that a random -regular graph is almost Ramanujan, in the following sense: for every , asymptotically almost surely. Friedman famously presented a proof of this conjecture in Friedman (Memoirs of the AMS 910, 2008). Here we suggest a new, substantially simpler proof of a nearly-optimal result: we show that a random -regular graph satisfies a.a.s. A main advantage of our approach is that it is applicable to a generalized conjecture: For even, a -regular graph on vertices is an -covering space of a bouquet of loops. More generally, fixing an arbitrary base graph , we study the spectrum of , a random -covering of . Let be the largest absolute value of a non-trivial eigenvalue of . Extending Alon's conjecture to this more general model, Friedman (Duke Math J 118(1),19-35, 2003) conjectured that for every a.a.s. , where is the spectral radius of the universal cover of . When is regular we get a bound of , and for an arbitrary , we prove a nearly optimal upper bound of . This is a substantial improvement upon all known results (by Friedman, Linial-Puder, Lubetzky-Sudakov-Vu and Addario-Berry-Griffiths).