Computer Science/Discrete Mathematics Seminar II

I will present a recent result by Martin Kassabov, which answers affirmatively a 20 year-old open question: Do the symmetric groups S_n contain bounded-size generating sets U_n such that the Cayley graphs C(S_n,U_n) are (bounded-degree) expander graphs (i.e. they have second eigenvalue at most 1-u, for some constant u, independent of n)? Until recently, this answer to this type of question was known to be "yes" only for matrix groups with bounded dimension. By the recent results of Kassabov, Lubotzky, Nikolov and others, we now know that bounded-degree Cayley expanders exist for (almost) all finite simple groups (the current work implies this for the alternating groups). All the proofs actually give explicit generating sets for which this hold. The beautiful proof uses a blend of techniques from combinatorics, probability and representation theory of the symmetric group. However, no special background will be assumed in any of these areas. The starting point of the proof is the following fact, which (as we shall see) is very easy to prove, but is equally fruitful. Suppose S_n contains two groups G,H whose set-union generates S_n, and the corresponding Cayley graph is an expander. Suppose that each of G,H contains a small expanding generating set U_G,U_H. Then the union of U_G,U_H also generates an expander Cayley graph on S_n. This fact shows us that it is enough to analyze the expansion of a huge generating set of S_n, as long as this huge generating set is contained in the union of a few groups who all admit a small number of expanding generators. Kassabov's paper appears on the arxiv at http://arxiv.org/abs/math.GR/0505624