Analysis on Graphs and Fractals

From arithmetic to combinatorics and back

A Gamburd, Univ. of California, Santa Cruz, USA

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 Jean Bourgain and Peter Sarnak tools from additivecombinatorics were used to prove that a wide class of number theoretic graphs are expanders; this expansion property plays a crucial role in establishing novel sieving results towards non-abelian generalizations of Dirichlet's theorem on primes in arithmetic progressions.