MIT Combinatorics Seminar

Symmetric Groups and Expanders

Martin Kassabov  (Cornell University)

Wednesday, May 4, 2005   4:15 pm    Room 2-338


A finite graphs with large spectral gap are called expanders. These graphs have many nice properties and have many applications. It is easy to see that a random graph is an expander but constructing an explicit examples is very difficult. All known explicit constructions are based on the group theory --- if an infinite group G has property T (or its variants) then the Cayley graphs of its finite quotients form an expander family.

This leads to the following question: For which infinite families of groups G_i, it is possible to find generating sets S_i which makes the Cayley graphs expanders?

The answer of the question is known only in few case. It seems that if G_i are far enough from being abelian then the answer is YES. However if one takes `standard' generating sets the resulting Cayley graphs are not expanders (in many cases).

I will describe a recent construction which answers the above question in the case of the family of all symmetric/alternating groups. It is possible to construct explicit generating sets S_n of Alt_n, such that the Cayley graphs C(Alt_n,S_n) are expanders, and the expanding constant can be estimated.

Unlike the usually constructions of expanders, the proof does not use an infinite group with property T (although such group exists) but uses the representation theory of the symmetric groups directly.