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
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.