Abstract

Lifts, discrepancy and nearly optimal spectral gaps

Nathan (Nati) Linial
Hebrew University, Jerusalem, Israel
Computer Science

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^3d}, c \sqrt{d \log^3d}]$ for some constant $c$. This leads to a probabilistic algorithm for constructing arbitrarily large $d$-regular graphs, with second eigenvalue $O(\sqrt{d \log^3 d})$, a.s. in polynomial time. 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/\alpha)$, for some universal constant $c$. An interesting consequence of this lemma is a converse to the Expander Mixing Lemma.