TY - JOUR
T1 - Spectra of lifted Ramanujan graphs
AU - Lubetzky, Eyal
AU - Sudakov, Benny
AU - Vu, Van
N1 - Funding Information:
* Corresponding author. E-mail addresses: [email protected] (E. Lubetzky), [email protected] (B. Sudakov), [email protected] (V. Vu). 1 The author is supported by NSF CAREER award 0812005 and a USA-Israeli BSF grant. 2 The author is supported by research grants DMS-0901216 and AFOSAR-FA-9550-09-1-0167.
PY - 2011/7/10
Y1 - 2011/7/10
N2 - 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 O(ρ1/2λ11/2) 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 O(Π2/3λ11/3). For d-regular graphs, where ρ1=d and d-1, this translates to a bound of O(d2/3), compared to the conjectured 2√d-1. 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 O((λVρ)logρ). 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.
AB - 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 O(ρ1/2λ11/2) 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 O(Π2/3λ11/3). For d-regular graphs, where ρ1=d and d-1, this translates to a bound of O(d2/3), compared to the conjectured 2√d-1. 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 O((λVρ)logρ). 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.
KW - Ramanujan graphs
KW - Random lifts
KW - Spectral expanders
UR - http://www.scopus.com/inward/record.url?scp=79956050252&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79956050252&partnerID=8YFLogxK
U2 - 10.1016/j.aim.2011.03.016
DO - 10.1016/j.aim.2011.03.016
M3 - Article
AN - SCOPUS:79956050252
SN - 0001-8708
VL - 227
SP - 1612
EP - 1645
JO - Advances in Mathematics
JF - Advances in Mathematics
IS - 4
ER -