2lifts, QuasiRamanujan graphs and a converse to the Expander Mixing LemmaYonatan BiluHebrew University in Jerusalem
March 5,

ABSTRACT


The adjacency matrix of a graph on n vertices is a 01 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 dregular 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 socalled 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 dregular graph by +1 and 1. This yields a 2lift of a graph  graph on twice as many vertices which is also dregular. 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 dregular 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. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

