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

Yonatan Bilu

Hebrew University in Jerusalem

March 5,
refreshments at 3:45pm


The adjacency matrix of a graph on n vertices is a 0-1 nxn matrix, with the (i,j) entry being 1, iff there is an edge between vertices i and j. Often, understanding the eigenvalues of the adjacency matrix sheds light on combinatorial properties of a graph. In a d-regular graph, the largest eigenvalue is d. If the absolute value all other eigenvalues is small, we say that such a graph is an expander. Optimal constructions of such graphs are known, but they rely on group representation theory. In this work we describe a simple, combinatorial construction that is close to being optimal.

A useful property of expander graphs is the so-called Expander Mixing Lemma, which bounds the deviation of the number of edges between two sets of vertices from what is expected in a random graph. We show a converse to this lemma, namely, that if the deviation is small then the graph is an expander. The implication is surprisingly strong, in comparison to other combinatorial properties (edge expansion, vertex expansion) which also imply a bound on the eigenvalues.

The key tool in the construction is a signing of the edges of a d-regular graph by +1 and -1. This yields a 2-lift of a graph - graph on twice as many vertices which is also d-regular. Getting an expander graph in this way reduces to finding a signing of a graph such that the spectral radius of the signed adjacency matrix is small. We show that for all d-regular graphs such a signing exists, and that if the graph we start from is an expander, then such a signing can be found efficiently.

Joint work with Nati Linial.

Speaker's Contact Info: johnblue(at-sign)cs.huji.ac.il

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on February 23, 2004 at 01:53 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.