Cristina Ballantine (Holy Cross) <BR><BR>


Biregular expanders and the Ramanujan Conjecture

<BR><BR>

Expander graphs are well connected yet sparse graphs. The expanssion
property of a graph is governed by the second largest eigenvalue of the
adjacency matrix. I will consider quotients of the Bruhat-Tits building
of  GL(n), n=2,3, and view them as graphs. In this context the
relationship between regular expander graphs and the Ramanujan
Conjecture is well understood and has led to the definition and
construction of asymptotically optimal regular expanders called
Ramanujan graphs. In this talk I will show that biregular bipartite
graphs obtained from the Bruhat-Tits building of a form of U(3) whose
representations satisfy the Ramanujan conjecture are indeed Ramanujan
bigraphs (this is joint work with Dan Ciubotaru). TIme permitting, I
will also introduce a beautiful and simple combinatorial construction of
constant degree expanders which are close to being Ramanujan. This
construction, called the zig-zag product of graphs, is due to Reingold,
Vadhan and Wigderson.