Symmetric Groups and Expanders

Abstract

We construct an explicit generating sets $F_n$ and ${\tilde{F}}_n$ of the alternating and the symmetric groups, which make the Cayley graphs $C(Alt(n),F_n)$ and $C(Sym(n),{\tilde{F}}_n)$ a family of bounded degree expanders for all sufficiently large $n$. These expanders have many applications in the theory of random walks on groups and other areas of mathematics.

10 pages