Abstract

A family of k-regular finite graphs is expanding if the graphs are uniformly highly connected. More precisely, for every partition V(X) = A \cup B of the set of vertices of a graph X in the family, the number of edges connecting A and B must be at least c min{|A|, |B|}, where c>0 is independent of X, A and B.

Such families were first constructed by random methods, but explicit constructions were desirable for applications, e.g. for derandomization of algorithms.

Many families of expander graphs have been constructed as Cayley graphs of non-abelian groups G, i.e. taking G itself as the set of vertices, and connecting vertices g and h with an edge if hg^{-1} belongs to a fixed symmetric generating set S of G.

Much care has been taken in choosing the generating sets S, and in some cases this was shown to be necessary. However, our new result shows that for many standard families of groups, every generating set works.

The talk will begin with a gentle introduction to expander graphs.

Based on joint work with Emmanuel Breuillard.