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 ρ=2d−1, this translates to a bound of O(d2/3), compared to the conjectured 2d−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((λ∨ρ)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.
%0 Journal Article
%1 lubetzky11
%A Lubetzky, Eyal
%A Sudakov, Benny
%A Vu, Van
%D 2011
%J Advances in Mathematics
%K eigenvalues expander graph.theory lift ramanujan spectral.graph.theory
%N 4
%P 1612--1645
%R 10.1016/j.aim.2011.03.016
%T Spectra of Lifted Ramanujan Graphs
%V 227
%X 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 ρ=2d−1, this translates to a bound of O(d2/3), compared to the conjectured 2d−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((λ∨ρ)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.
@article{lubetzky11,
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 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 ρ=2d−1, this translates to a bound of O(d2/3), compared to the conjectured 2d−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((λ∨ρ)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.},
added-at = {2016-10-29T16:27:47.000+0200},
author = {Lubetzky, Eyal and Sudakov, Benny and Vu, Van},
biburl = {https://www.bibsonomy.org/bibtex/2dc3ab7c28235292533d8e994480ce0f2/ytyoun},
doi = {10.1016/j.aim.2011.03.016},
interhash = {7feb0ee674613e535e29c59f322336bc},
intrahash = {dc3ab7c28235292533d8e994480ce0f2},
issn = {0001-8708},
journal = {Advances in Mathematics},
keywords = {eigenvalues expander graph.theory lift ramanujan spectral.graph.theory},
number = 4,
pages = {1612--1645},
timestamp = {2017-02-23T12:42:01.000+0100},
title = {Spectra of Lifted {Ramanujan} Graphs},
volume = 227,
year = 2011
}