Expander graphs (ETHZ
HS 2011)

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

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 *SL _{2}(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

Uniform expansion bounds for Cayley graphs of *SL _{2}(F_{p})* 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

Last update 8.8.2012 by E. Kowalski