CS 298-2
Theory Seminar

Yonatan Bilu
Hebrew University

Quasi-Ramanujan 2-lifts and a converse to the Expander Mixing Lemma

Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map p:H -> G. It turns out that all eigenvalues of G are also eigenvalues of H. In addition, H has n ``new'' eigenvalues.

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 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 with zero on the diagonal, such that the $l_1$ norm of each row in A is at most d, and for every $x,y \in \{0,1\}^n$ with disjoint support, |xAy|/(||x|| ||y||) < f. Then the spectral radius of A is $O(f (\log(d/f) + 1))$. An interesting consequence of this lemma is a converse to the Expander Mixing Lemma.

Joint work with Nati Linial