Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let $G$ be a graph on $n$ vertices. A 2-lift of $G$ is a graph $H$ on $2n$ vertices, with a covering map $\pi :H\to 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\sqrt{d-1},2\sqrt{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\sqrt{d{\log }^{3}d},c\sqrt{d{\log }^{3}d}]$ for some constant $c$. This leads to a polynomial time algorithm for constructing arbitrarily large $d$-regular graphs, with second eigenvalue $O(\sqrt{d{\log }^{3}d})$. The proof uses the following lemma: Let $A$ be a real symmetric matrix such that the $l_1$ norm of each row in $A$ is at most $d$. Let $\alpha = \max_{x,y \in {0,1}^n, supp(x)\cap supp(y)=\emptyset} \frac {|xAy|} {||x||||y||}$. Then the spectral radius of $A$ is at most $c\alpha \log (d\mathrm{/}\alpha )$, for some universal constant $c$. An interesting consequence of this lemma is a converse to the Expander Mixing Lemma.