Lifts, Discrepancy and Nearly Optimal Spectral Gaps

Abstract

Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π: H → G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range [−2 √ d − 1,2 √ d − 1] (If true, this is tight, e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree √ d has a 2-lift such that all “new ” eigenvalues are in the range [−c dlog 3 √ d,c dlog 3 d] for some constant c. This leads to a polynomial time algorithm for constructing √ arbitrarily large d-regular graphs, with second eigenvalue O ( dlog 3 d). The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix such that the l1 norm of each row in A is at most |xAy| d. Let α = maxx,y∈{0,1} n,supp(x)∩supp(y)= ∅ ||x||||y||. Then the spectral radius of A is at most cα log(d/α), for some universal constant c. An interesting consequence of this lemma is a converse to the Expander