2003/12/01 by Yonatan Bilu, Nathan Linial, Bilu, Yonatan +1
Engineering · Mathematics · #05C22 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #graph theory and CDMA systems #math.CO #msc:05C22 #msc:05C50
paper · pdf · doi:10.48550/arxiv.math/0312022
29 pages, 1 figure
openalex publication_date 2003/12/01 · arxiv created 2004/04/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 → 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 √(d log3d), c √(d log3d)] for some constant c. This leads to a polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue O(√(d log3 d)). The proof uses the following lemma: Let A be a real symmetric matrix such that the l1 norm of each row in A is at most d. Let α= max_x,y ∈ \0,1\n, supp(x)∩ supp(y)=∅ \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.