The University of Michigan Combinatorics Seminar
Fall 2007
November 9, 4:10-5:00, 3866 East Hall



Expanders: from arithmetic to combinatorics and back

Alexander Gamburd

UC Santa Cruz and Institute for Advanced Study


Abstract

Expanders are highly-connected sparse graphs widely used in computer science. The optimal expanders (Ramanujan graphs) were constructed in 1988 by Margulis, Lubotzky, Phillips and Sarnak using deep results from the theory of automorphic forms. In recent joint work with Bourgain and Sarnak tools from additive combinatorics were used to prove that a wide class of "congruence graphs" are expanders; this expansion property plays a crucial role in establishing novel sieving results.