Spectra of lifted Ramanujan graphs |
| |
Authors: | Eyal Lubetzky Benny Sudakov Van Vu |
| |
Affiliation: | aMicrosoft Research, One Microsoft Way, Redmond, WA 98052, USA;bDepartment of Mathematics, UCLA, Los Angeles, CA 90095, USA;cDepartment of Mathematics, Rutgers, Piscataway, NJ 08854, USA |
| |
Abstract: | A random n-lift of a base-graph G is its cover graph H on the vertices [n]×V(G), where for each edge uv in G there is an independent uniform bijection π, and H has all edges of the form (i,u),(π(i),v). A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan.Let G be a graph with largest eigenvalue λ1 and let ρ be the spectral radius of its universal cover. Friedman (2003) [12] proved that every “new” eigenvalue of a random lift of G is with high probability, and conjectured a bound of ρ+o(1), which would be tight by results of Lubotzky and Greenberg (1995) [15]. Linial and Puder (2010) [17] improved Friedman?s bound to . For d-regular graphs, where λ1=d and , this translates to a bound of O(d2/3), compared to the conjectured .Here we analyze the spectrum of a random n-lift of a d-regular graph whose nontrivial eigenvalues are all at most λ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is . This result is tight up to a logarithmic factor, and for λ?d2/3−ε it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical n-lift of a Ramanujan graph is nearly Ramanujan. |
| |
Keywords: | Random lifts Spectral expanders Ramanujan graphs |
本文献已被 ScienceDirect 等数据库收录! |
|