ETH HomeD-MATH Home
Expander graphs (ETHZ HS 2011)

This page contains links to the lecture notes and some other interesting documents concerning the class.

8.8.2012: The lecture notes now contain new versions of the proofs of Helfgott's growth theorem for SL2, and of the Bourgain-Gamburd expansion theorem for Cayley graphs of SL2(Z/pZ) with respect to generating sets coming from a Zariski-dense subgroup of SL2(Z), which are not fully explicit (and therefore more readable). See the paper Explicit growth and expansion for SL2 for fully explicit versions of these results.

Here are further useful links and documents.

Expander graphs and their applications by S. Hoory, N. Linial and A. Wigderson. This is the best current reference on expanders in general, with emphasis in particular on their applications in theoretical computer science.

Graph partitioning and expanders by L. Trevisan. This is the website for a recent course on expanders, from a theoretical computer-science point of view.

Expander graphs in pure and applied mathematics by A. Lubotzky. These are the notes for Lubotzky's recent "Colloquium lectures" at the 2011 AMS-MAA-SIAM joint meeting in New Orleans. They emphasize recent applications of expanders to "pure" mathematics.

Discrete groups, expanding graphs and invariant measures by A. Lubotzky. This book is accessible online from the ETH domain.

Growth and generation in SL2(Z/pZ) by H. Helfgott (published in Annals of Math. 167 (2008), 601--623). This paper proves Helfgott's growth theorem, which is the most crucial ingredient of the proof that Cayley graphs modulo primes of a Zariski-dense subgroup of SL2(Z) are expanders.

Uniform expansion bounds for Cayley graphs of SL2(Fp) by J. Bourgain and A. Gamburd, Annals of Math. 167 (2008), 625-642. This paper proves the second half of the main theorem of the course: starting from Helfgott's growth theorem, it shows that congruence Cayley graphs of a Zariski-dense subgroup of SL2(Z) are expanders.

Last update 8.8.2012 by E. Kowalski