Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap
| dc.creator | Bilu, Yonatan | |
| dc.creator | Linial, Nathan | |
| dc.date | 2003-12-01 | |
| dc.date | 2004-04-08 | |
| dc.date.accessioned | 2026-07-07T05:03:25Z | |
| dc.date.available | 2026-07-07T05:03:25Z | |
| dc.description | 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 $π: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 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 $α= \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 α\log(d/α)$, for some universal constant $c$. An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. | |
| dc.description | 29 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/math/0312022 | |
| dc.identifier | http://arxiv.org/abs/math/0312022 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69413 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C50; 05C22 | |
| dc.title | Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap | |
| dc.type | text |