%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you retrieve the article in DVI,       *
%_ * PostScript, or PDF format.                                             *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{6-JUN-2005,6-JUN-2005,6-JUN-2005,6-JUN-2005}
 
\RequirePackage[warning,log]{snapshot}
\documentclass{era-l}
\issueinfo{11}{06}{}{2005}
\dateposted{June 9, 2005}
\pagespan{47}{56}
\PII{S 1079-6762(05)00146-0}
\copyrightinfo{2005}{American Mathematical Society}
\revertcopyright

\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}


\newcommand{\mySL}{\mathrm{SL}}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\EL}{\mathrm{EL}}
\newcommand{\Hom}{\mathrm{Hom}}
\newcommand{\Mat}{\mathrm{Mat}}
\newcommand{\mb}[1]{\mbox{\rm {#1}}}
\newcommand{\mr}[1]{\mathcal{#1}}
\newcommand{\Rd}{\left.R^*\right.^2}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\T}{\mathbb{T}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Id}{\mathrm{Id}}
\newcommand{\KC}{\mr{K}}
\newcommand{\TC}{\tau}
\newcommand{\SC}{\mr{S}}
\newcommand{\TauC}{$\tau$-constant}
\newcommand{\SelC}{Selberg constant}
\newcommand{\KaC}{Kazhdan constant}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\Alt}{\mathrm{Alt}}
\newcommand{\tolook}[1]{\textbf{#1}}

\newtheorem{theorem}{Theorem}[section]
\renewcommand{\thetheorem}{\arabic{theorem}}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{acknowledgement}[theorem]{Acknowledgment}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}{Case}
\newtheorem{claim}{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{document}
\title{Symmetric groups and expanders}
\author{Martin Kassabov}
\address{Department of Mathematics,
Cornell University,
Ithaca, New York 14853-4201}
\email{kassabov@math.cornell.edu}
\commby{Efim Zelmanov}
\date{March 16, 2005}
\subjclass[2000]{Primary 20B30; Secondary 05C25, 05E15, 20C30, 20F69, 
60C05, 68R05, 68R10}
\keywords{Expanders, symmetric groups,
alternating groups, random permutations, property T, Kazhdan constants.}
\begin{abstract}
We construct explicit generating sets $F_n$ and $\tilde F_n$ of the 
alternating and the symmetric groups,
which turn the Cayley graphs $\mathcal{C}(\textup{Alt}(n), F_n)$ 
and $\mathcal{C}(\textup{Sym}(n), \tilde F_n)$ into
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 in other areas of mathematics.
\end{abstract}
\maketitle

A finite graph $\Gamma$ is called an $\epsilon$-expander for some
$\epsilon \in (0,1)$ if for any subset $A \subseteq \Gamma$ of size
at most $|\Gamma|/2$ we have $|\partial (A)| >\epsilon |A|$
(where $\partial(A)$ is the set of vertices of $\Gamma \backslash A$ of edge
distance 1 to $A$). The largest such $\epsilon$ is called the
expanding constant of $\Gamma$. Constructing families of $\epsilon$-expanders
with 
bounded valency is an important practical problem in computer
science, because such graphs have many nice properties --- for
example, these graphs are highly connected, have a logarithmic diameter
and the random walks mix rapidly.
For an excellent introduction
to the subject we refer the reader to the book~\cite{expanderbook}
by A. Lubotzky.

Using counting arguments it can be shown that almost
any $5$ regular graph is a $1/5$-expander. However, constructing
explicit examples of families of expander graphs is
a difficult problem.


The first explicit construction of a family of expanders was
done by G. Margulis in~\cite{Mar}, using Kazhdan's property T
of $\mySL_3(\Z)$. Currently there are several different construction
of expanders. With the exception of a few recent ones based on
the zigzag products of graphs
(see~\cite{ALW,RVW,RSW}), all constructions are based on group theory and use
some variant of property T (property $\tau$, Selberg's
property, etc.).


Kazhdan's property T is not very interesting for a given finite group $G$
(all finite groups have property T),
but the related Kazhdan constant with respect to some generating set $F$
is. Given an infinite collection of finite groups $G_i$, it is a
challenge to prove or disprove the existence of uniform Kazhdan constants
with respect to properly chosen generating sets.
Problem~\ref{FGE} below is a reformulation of this question.



The original definition of property T uses the Fell
topology of the unitary dual; see~\cite{kazhdan}.
Here we will use an equivalent
definition (only for discrete groups) which also addresses the
notion of \KaC s.


\begin{definition}\label{expander}
Let $G$ be a discrete group generated by a finite set $S$.
Then $G$ has Kazhdan's property T if there exists
$\epsilon  >0$
such that for every unitary
representation $\rho: \ G \rightarrow U(\mr{H})$ on a
Hilbert space $\mr{H}$ without $G$ invariant vectors and
every  vector $v \not = 0$ there
exists some $s \in S$ such that $\|\rho(s)v-v\|> \epsilon \|v\|$.
The largest $\epsilon$ with this property is called the \emph{\KaC}
for $G$ with respect to $S$ and is denoted by $\KC(G;S)$.
\end{definition}
For a 
group $G$ the property T is independent on the
choice of the generating set $S$; however, the Kazhdan constant
depends also on the generating set.


There is a well-known connection between property T and expander graphs:

\begin{theorem}[{\cite{expanderbook}}, Theorem 4.3.2]\label{CGexpanders}
Let $G$ be a discrete group having property T, and let
$S$ be a finite generating set of $G$.
Then there exists an
$\epsilon=\epsilon(S) >0$ such that
the Cayley graphs $\mr{C}(G_i,S_i)$ (and all their quotients) of the finite
images of $G_i$ of $G$ (with respect to the images $S_i$ of $S$)
form a family of $\epsilon$-expanders. The largest $\epsilon_0(S)$
with this property is related to the \KaC\ $\KC(G,S)$,
in particular we have
$\epsilon_0(S) \geq \KC(G;S)^2/4$.
\end{theorem}


Using this approach and property T of $\mySL_n(\Z)$
one can make the Cayley graphs of $\mySL_n(\F_p)$ for fixed $n\geq 3$ a family
of expanders
.\footnote{
The Cayley graphs of $\mySL_2(\F_p)$ can also be made expanders although
the group $\mySL_2(\Z)$ does not have property T or
even $\tau$; see~\cite{LPS}.}
Until recently the only way to
prove Kazhdan's property T was via representation theory of
high rank Lie groups. These methods are not
quantitative and do not lead to estimates for the
\KaC s and the corresponding expanding constants of
the resulting Cayley graphs.

A breakthrough in this direction is due to Y.~Shalom \cite{YSh}, who
used the bounded generation of the $\mySL_n(\Z)$ and
M.~Burger's estimate (see~\cite{Bur})
of the relative \KaC\ of $\mySL_2(\Z)\ltimes \Z^2$
to obtain a lower bound for the \KaC\ of $\mySL_n(\Z)$. His methods were refined
in~\cite{K} to give the exact asymptotic of the \KaC\ of $\mySL_n(\Z)$
with respect to the set of all elementary matrices.
This yields an asymptotically exact estimate for the expansion
constant of the form $n^{-1}$ of the Cayley graphs of
$\mySL_n(\F_p)$ with respect to the set of all elementary
matrices.
It is interesting to note that if the size of the matrices
increases, then the resulting Cayley graphs do not form an
expander family, even though the degree of these graphs
goes to infinity.

Using the relative property T of the pair
$\mySL_2(R)\ltimes R^2, R^2$ for finitely generated noncommutative rings
$R$, the Cayley graphs of $\mySL_n(\F_q)$ for any prime power $q$
and all $n \geq 3$ can be
made expanders simultaneously by choosing a suitable generating
set; see~\cite{KSL3k}. An important building block
in this construction is that the group $\mySL_n(\F_q)$
can be written as a product of $20$ abelian subgroups and this number is
independent of $n$ and $q$.


The examples lead to the following problem:
\begin{problem}\label{FGE}
Let $G_i$ be an infinite family of finite groups. Is it possible
to make their Cayley graphs expanders using suitably chosen
generating sets?
\end{problem}
Currently there is no theory which can give
a satisfactory answer to this question. The answer is known
only in a few special cases: If the family of finite groups
comes from a finitely generated infinite group with
property T (or its weaker versions),
then the answer is YES.
Also if all groups in the family are
``almost'' abelian, then the answer is NO (see~\cite{lubwiess}),
and this is practically the only case where a negative answer
is known.


Motivated by the above remark A.~Lubotzky
conjectured~\cite{Lpr} that Problem~\ref{FGE} should have
a positive answer in the case of finite simple groups:
\iffalse
Motivated by the classification of the finite simple groups A.~Lubotzky
suggested~\cite{Lpr} that the results from~\cite{KSL3k} could be generalized
and give a positive answer to Problem~\ref{FGE} in the case of finite simple groups:
\fi
\begin{conjecture}\label{FSGE}
There exist constants $L>0$ and $\epsilon>0$ such that any
nonabelian finite simple group $G$ has  a
generating set $F$ such that $|F|\leq L$ and
the
Cayley graphs $\mr{C}(G;F)$ form a family of
$\epsilon$-expanders. Equivalently, we have that
$\KC(G;F)>\epsilon$ (with a different constant $\epsilon$).
\end{conjecture}


This conjecture is supported by
several results --- it is known (see~\cite{BLK} and~\cite{KR})
that for any nonabelian finite simple
group there exists a $4$ element generating set such that the
diameter of the corresponding Cayley graph is logarithmic in
the size of the group.

As with many similar results,
one expects that the proof of Conjecture~\ref{FSGE}
will use the classification of the finite simple groups.
It seems that almost all finite simple groups of Lie type groups can
be made expanders using an idea from~\cite{KSL3k}. 
The alternating groups form the only other infinite family of
finite simple groups, and it was believed that this is the most difficult
case of the Lubotzky conjecture.

The methods from~\cite{KSL3k} cannot be applied directly to
the symmetric/alternating groups because these groups cannot be written
as a product of a fixed number of abelian subgroups ---
the size of $\Sym(n)$ or $\Alt(n)$ is
approximately $n^{n}$, and every abelian subgroup
has at most $2^n$ elements; see~\cite{A}.
This suggests that the groups $\Alt(n)$ are ``further from the abelian groups''
than all other finite simple groups, and therefore
they should have more expanding properties.
Unfortunately, this also
significantly complicates the construction of expanders
based on the alternating groups.



The main result announced in the paper  can be
viewed as a major step toward proving Conjecture~\ref{FSGE}.
Theorem~\ref{main1}, together with the results
from~\cite{KSL3k}, proves the Lubotzky conjecture in all but a few
cases; see~\cite{KNFS} for details.


If one allows unbounded generating sets, there are only
a few partial results known. A classical result of N.~Alon and Y.~Roichman
(and its improvements in~\cite{LR} and~\cite{LS}) says that
any group is an $\epsilon$-expander%
\footnote{There are two different definitions of $\epsilon$-expanders,
which are equivalent for graphs of bounded degree but not in general:
A ``weak'' one corresponding to Definition~\ref{expander},
and a ``strong'' one using the spectral gap of the Laplacian.
The random Cayley graphs obtained from Theorem~\ref{AlRo} are
expanders in both definitions.}
with respect to a random large generating set:
\begin{theorem}[\cite{AR}]\label{AlRo}
For any $\epsilon>0$ there exists $c(\epsilon)>0$ such that
the Cayley graph of any finite group $G$ is an $\epsilon$-expander
with respect to a random generating set of size
$c(\epsilon) \log |G|$.
\end{theorem}
The bound $c(\epsilon) \log |G|$ is the optimal one in the
class of all finite groups, because the large abelian groups
are not expanders with respect to small generating sets.
It is believed that if the group $G$ is far from being abelian,
the bound $c\log |G|$ can be improved.
Note that Theorem~\ref{AlRo}
implies a version of Conjecture~\ref{FSGE}, where the
size of the generating set is allowed to increase.

Theorem~\ref{AlRo} also gives that the Cayley graphs of the
alternating groups $\Alt(n)$ are expanders with respect to a
random generating set of size $n \log n$.
This was the best known result in this direction, and even there
were no known explicit sets of size less than
$n^{\sqrt{n}}$ which make the Cayley graphs expanders. In view of the
main results in this paper it is very interesting to understand
the expanding properties of the Cayley graphs of $\Alt(n)$  and
other finite simple groups with respect
to a random generating set of a small (even bounded) size.


One of the main results announced in this paper
answers affirmatively an old question, which has been asked
several times in the literature; see~\cite{BHKLS,expanderbook,lu,LubZuk}:
\begin{theorem}\label{main}
There exist constants $L>0$, $\epsilon >0$ and an infinite
sequence $n_s$ with the property:
There exists a constructible generating set
$F_{n_s}$ of size at most $L$ of the alternating group $\Alt(n_s)$ such that
the Cayley graphs $\mr{C}(\Alt(n_s);F_{n_s})$ form a family of
$\epsilon$-expanders.
\end{theorem}


From the proof of Theorem~\ref{main}, it can be seen that
the sequence $n_i$ does not
grow too fast, which leads to the following generalization:

\begin{theorem}\label{main1}
There exist constants $L>0$ and $\epsilon >0$, with the
property: For any $n$ there exist
explicit generating sets $F_{n}$ and $\tilde F_{n}$
of the alternating group $\Alt(n)$
and the symmetric group $\Sym(n)$ respectively such that
the Cayley graphs $\mr{C}(\Alt(n);F_{n})$ and
$\mr{C}(\Sym(n);\tilde F_{n})$ form a family of
$\epsilon$-expanders. Moreover all generating sets $F_n$ and
$\tilde F_n$ have at most $L$ elements.
\end{theorem}


Theorem~\ref{main1} has interesting applications:
It provides one of the few constructions of an expander family
of Cayley graphs $\mr{C}(G_i,S_i)$ such that the groups $G_i$
are not quotients of some infinite group having a variant
of Kazhdan's property T.%
\footnote{For any infinite family of finite groups $G_i$ the existence of generating
sets $S_i$ such that the Cayley graphs $\mr{C}(G_i,S_i)$ are a family of expanders
is equivalent to the existence of a finitely generated subgroup of $\prod G_i$ which has
a variant of property T. The main point here is that
we prove that the Cayley graphs are expanders without using the representation
theory of this infinite group.}
It also provides a supporting evidence
for the conjecture that the automorphism groups of the free
groups have property $\tau$; see~\cite{Gilman} and \cite{LP}.


Theorem~\ref{main1} implies that the expanding constant of
$\Alt(n)$ with respect to the set $F_n^{10^{10}}$ is large enough.%
\footnote{More precisely we have that the spectral gap of the Laplacian of
the Cayley graph is very close to $1$.}
The size of the set $F_n^{10^{10}}$ is independent of $n$, and
if $n$ is sufficiently large, then $|F_n^{10^{10}}| < 10^{-30}n^{1/30}$.
The last inequality allows us to use the expander
$\mr{C}(\Alt(n);F_n^{10^{10}})$ as a
``seed'' graph for the Rozenman, Shalev, and Widgerson
recursive construction of expanders; see~\cite{RSW}.
This construction produces a family of expander graphs
based on the Cayley graphs of the automorphism group of
large $n$-regular rooted tree of depth $k$. A slight modification of
this construction gives another recursive expander family based on
$\Alt(n^k)$ for a fixed large $n$ and different $k$'s.


Theorem~\ref{main1} gives that the Cayley graphs $\mr{C}(\Alt(n); F_n)$ and
$\mr{C}(\Sym(n); \tilde F_n)$ have many expanding properties which
imply that the random walks on $\Alt(n)$ and $\Sym(n)$,
generated by $F_n$ and $\tilde F_n$
respectively, have mixing time of approximately
$\log |\Alt(n) | = n \log n$ steps.

\begin{proof}[Sketch of the proof of Theorem~\ref{main}]
This sketch 
describes all main steps in the construction and omits the proofs
of several technical claims. The proofs of these claims are
relatively easy and follow from standard combinatorial and
probabilistic arguments. A complete proof of Theorem~\ref{main}
can be found in~\cite{Ksymfull}.


We start with a very brief explanation of the main idea:
Let $\rho$ be a representation of $\Alt(N)$ with
almost invariant vector $v$ with respect to some generating set $F$
(to be chosen later), where $N=k^d$ for some $k$ and $d$. We will use two 
different arguments to show that
$\rho$ contains an invariant vector.

First, we show that the vector $v$ is almost invariant with respect to
the union of several abelian groups. After that
we will split the representation $\rho$ into
two components --- one corresponding
to partitions $\lambda$ with $\lambda_1 < N - h$ and
second one containing all other partitions for some suitably chosen $h$.
The decomposition of the regular representation of $\Alt(N)$ into two
components depending on the first part of the partition $\lambda$
comes from~\cite{Ro1}. In this paper, Roichman uses a similar
argument to show that the Cayley
graphs of the symmetric/alternating group with respect to a conjugacy
class with a large number of
nonfixed points have certain expanding properties.

We will show that the projection of the vector $v$ in the first representation
is small provided that $h \gg K$. Also, if $h \ll N^{1/4}$, 
the projection of $v$
in the second one is close to an
invariant vector.%
\footnote{We believe that the argument also works 
even in the case $h \ll N^{1/2}$;
however, we are unable to prove it.
If such generalization is true, it will allow us to use $d=4$,
which will improve the estimates
for the \KaC s by a factor of $10$.}
In order to satisfy these restrictions we need that
$N \gg K^4$, i.e., $d>4$. In order to simplify the argument a little, we also
require that $d$ is even, which justifies our choice of $d=6$ and $N=K^6$.
Also we need that $K \ll h \ll K^{3/2}$; therefore, we choose $h=K^{5/4}$
and define $\mr{H}_1$ to be the subrepresentation of
$\mr{H}$ corresponding to all partitions
with $\lambda_1 < N - K^{5/4}$.
As an additional assumption, we require that $K+1$ is a
power of some prime number and we use
$K=2^{3s}-1$ for a sufficiently large $s$.%
\footnote{It can be shown that $s>15$ suffices; however, the estimate depends on
the constants involved in the character estimates from~\cite{Ro},
which are not in the literature.}


We will think that the alternating group $\Alt(N)$ acts
on a set of $N$ points which are arranged into a $6$-dimensional
cube of size $K$, and we will identify these points with ordered
$6$-tuples of nonzero elements from the field $\F_{2^{3s}}$.

Let $\rho:\Alt(N) \to U(\mr{H})$ be a fixed unitary representation of
the alternating group, and let $v \in \mr{H}$ be
an $\epsilon$-almost invariant unit vector for some generating set
$F$. We will fix the set $F$ and the number $\epsilon$ later.
Without loss of generality, we may assume that
$\mr{H}$ is generated by the orbit of the vector $v$.



Let $H_s$ denote the group $\mySL_{3s}(\F_2)$. The group $H_s$
has a natural action on the set $V\setminus \{0\}$ of $K$ nonzero
elements of a vector space $V$ of dimension $3s$ over $\F_2$.
The elements of $H_s$ act by even permutations on $V\setminus \{0\}$, because
$H_s$ is a simple group and does not have $\Z/2\Z$ as a factor.
If we identify $V$ with $\F_{2^{3s}}$, then the
existence of a generator for the multiplicative group of $\F_{2^{3s}}$ implies
that some element in $H_s=\GL_{2s}(\F_2)$ acts as a $K$-cycle on $V\setminus\{0\}$.%
\footnote{We can use some other family of groups instead of $\{H_s\}_s$ --- the only
requirements for groups in $\{H_s\}_s$ are that they act 
transitively on a set of $K(s)$ points
(where $K(s) \to \infty $ as $s \to \infty$)
and that $\big\{{H_s}^{\times {K(s)^5}}\big\}_s$ can be made a bounded degree expanders.
For example, we can use the groups $\mySL_3(\F_p)$ acting on ${\F_p}^3 \setminus \{0\}$ or
on the projective plane ${P^2\F_p}$ for different primes $p$.}


Let $\Gamma$ be the direct product of $K^5$ copies of the group $H_s$.
The group $\Gamma$ can be embedded into $\Alt(N)$ in $6$ different ways,
which we denote by $\pi_i$, $i=1,\dots, 6$. The image of
each copy of $H_s$ under $\pi_i$ acts as $\mySL_{3s}(\F_2)$
on a set of $K=2^{3s}-1$
points where all
coordinates but the $i$th one are fixed. It is clear that
$\Gamma$ contains an abelian subgroup $\overline{\Gamma}$
isomorphic to $(\Z/K\Z)^{\times K^5}$.



Using Theorem~5 from~\cite{KSL3k}, we can find a small generating set
$S$ of the group $H_s$ such that the \KaC\ $\KC(H_s;S) > 1/400$.
This allows us to construct a generating set $\tilde S$ with $40$ elements
of $\Gamma$ with similar properties, i.e., the \KaC\
$$
\KC(\Gamma;\tilde S) > 1/500.
$$

Now we can define the generating set $F_N$ of $\Alt(N)$ such that the
\KaC\ $\KC(\Alt(N);F_N)$ can be estimated --- the set $F_N$ will be the
union of the images of $\tilde S$ under the embeddings $\pi_i$:
$$
F_N = \bigcup_i \pi_i(\tilde S).
$$
The group generated by the set $F_N$ contains the $6$ images
of $\Gamma$ and therefore
is the whole alternating group $\Alt(N)$. From now on, we will assume
that the vector $v\in\mr{H}$ is $\epsilon$-almost invariant with
respect to the set $F_N$ defined above.

Using the \KaC\ of $\KC(\Gamma;\tilde S)$, it can be seen that if
$v$ is an $\epsilon$-almost invariant vector with respect to the set $F_N$
in some representation $\rho$ of $\Alt(N)$, then $v$ is close to a $\Gamma_i$
invariant vector, i.e.,
$$
\|\rho(\pi_i(g))v -v \| \leq 10^3 \epsilon \|v\|,
$$
for all $g \in \Gamma$ and any $i=1,\dots, 6$.
If the diameters of the Cayley graphs of $\mr{C}(\Alt(N),\bigcup \Gamma_i)$ 
were
bounded independently on $N$, this would gives us that the
representation $\rho$
has an invariant vector, provided that $\epsilon$ is small enough.
Unfortunately this is not the case, because the size of $\bigcup \Gamma_i$ is
small compared to $\Alt(N)$, i.e., the ratio  $\ln |\Alt(N)| / \ln | \bigcup 
\Gamma_i|$ is not bounded.


Let $\overline{\Gamma_i}$ denote the image of $\overline{\Gamma}$
under the embedding $\pi_i$ and let $C$ be the union of $\overline{\Gamma_i}$.
Thus, 
we may assume that the vector $v$ is almost invariant with respect to the set $C$.


As mentioned before we will break the representation $\rho$ into two components.
The space $\mr{H}$ decomposes as a sum of irreducible representations
$$
\mr{H} = \bigoplus_\lambda c_\lambda M^\lambda,
$$
where the sum is over all partitions $\lambda$ of $N$, $M^\lambda$ denotes the
irreducible representations corresponding to the partition $\lambda$,
and $c_\lambda$ is the multiplicity of $M^\lambda$ in $\mr{H}$, which is
either $0$ or $1$, since $\mr{H}$ is generated  by 1 element.
Let $\mr{H}_1$ be the sum of all irreducible subrepresentations
of $\mr{H}$ which correspond
to the partitions $\lambda=[\lambda_1,\lambda_2,\dots]$ of $N$
with
$$
\lambda_1 < N - K^{5/4},
$$
and let $\mr{H}_2$ be the orthogonal complement of $\mr{H}_1$ in $\mr{H}$.

This allows us to decompose the almost invariant vector $v$ as
$v=v_1 + v_2$, where
$v_i \in \mr{H}_i$. We will use two different arguments to
show that the vector $v_1$
is small and that $v_2$ is close to an invariant vector in $\mr{H}_2$.


Using the definition of the set $C$, it can be seen that $C^{440}$
acts almost transitively
on the set of all ordered tuples of $K^5/10$ points.
Here $C^{440}$ denotes the set
of all products of less than $440$ elements from the set $C$,
and by almost transitivity we mean that if we are
given $2$ ordered tuples, then with large probability $\kappa$
(approaching $1$ as $s\to \infty$), there
exists an element in $C^{440}$ which sends one tuple to the other.
Therefore, the set $C^{440}$ contains almost all elements in some
conjugacy class $B$ of permutations
in $\Alt(N)$ with at least $K^5/10$ nonfixed points.

The vector $v$ is almost preserved by any element of $C$,
which implies that $v$
is moved little by most of the elements inside the
conjugacy class $B$, i.e.,
\mbox{$\|\rho(g) v -v\|$}${} \leq 440\times 1000 \epsilon $ for any
$g \in B \cap C^{440}$. This gives
\begin{align*}
\left\| \frac{1}{|B|}\sum_{g\in B} \rho_1(g) v_1 -v_1 \right\|
& \leq
\frac{1}{|B|}\sum_{g\in B} \|  \rho(g) v -v \|\\
& \leq
 2(1-\kappa) \|v_1\| +
\frac{1}{|B|}\sum_{g\in B \cap C^{440}}
         \|\rho(g) v -v \| \\
& <
\frac{\|v_1\|}{6} + 4.5 \times 10^5 \epsilon ,
\end{align*}
provided that $\kappa$ is sufficiently close to $1$.
The decomposition of  $\mr{H}_1$ as
$$
\mr{H}_1 = \bigoplus_\lambda c_\lambda M^\lambda
$$
gives a decomposition of the vector $v_1 = \sum v_\lambda$.
The set $B$ is a conjugacy class; therefore,
$\frac{1}{|B|}\sum_{g\in B} \rho(g) v_\lambda =
   \bar \chi_{\lambda}(B) v_\lambda $
for any vector $v_\lambda$  in an irreducible representation $M^{\lambda}$.
Here $\bar \chi_{\lambda}(B)$ is the normalized character of the representation
$M^{\lambda}$,
defined as $\bar \chi_{\lambda}(B) := \chi_{\lambda}(B)/ \dim M^{\lambda}$.
Thus we have
$$
\left\| \frac{1}{|B|}\sum_{g\in B} \rho_1(g) v_1 \right\| \leq
\|v_1\| \max_{\lambda} |\bar \chi_{\lambda}(B)|,
$$
where the maximum is taken over all partitions which appear in
the representation $\rho_1$, i.e.,
all partitions $\lambda$ with  $\lambda_1 < N - K^{5/4}$.
There are various estimates of the values of the normalized characters of the
symmetric/alternating groups. Applying the bounds from~\cite{Ro}, 
Theorem~1 yields
$$
\begin{array}{l@{}c@{}l}
\displaystyle
\max_{\lambda} |\bar \chi_{\lambda}(B)|
& {} \leq {}&
\displaystyle
\max_{\lambda} \left\{ \max
        \left\{ \lambda_1/N ,q \right\}^{c\, \mbox{\tiny supp}|B|} \right\}
\\
& \leq &
\displaystyle \rule[20pt]{0pt}{0pt}
\left(1-\frac{K^{\frac{5}{4}}}{K^6}\right)^{\frac{c K^5}{10} } \leq
  \exp\left(-\frac{cK^{\frac{1}{4}}}{10}\right)
  < \frac{1}{3},
\end{array}
$$
where $c$ and $q$ are universal constants. The last inequalities are 
valid only if $K$ is large enough.
The two inequalities above imply that
\begin{equation}\label{v1}
\|v_1\| < 9 \times 10^{5} \epsilon.
\end{equation}


The above argument does not work for the representation $\mr{H}_2$, because the first
part of the partition $\lambda$ can be close to $N$. This means that
the sum
$$
\lambda_2+ \lambda_3 + \dots < K^{5/4}
$$
is small. Therefore,
$\mr{H}_2$ can be embedded in the representation $M$ arising from
the action of $\Alt(N)$ on the set of all ordered tuples of size $K^{5/4}$.
Let $E$ denote the set of ordered tuples of size $K^{5/4}$
which is a basis of $M$.

We have $K^{K^5} \gg N^{K^{5/4}}$, i.e., the
number of elements in the set $C$ is much larger than the size of the set $E$.
Using this inequality and the definition of the set $S$,
it can be shown that the random walk on the set $E$,
where the moves are given by the permutations from some subset
$\widetilde{C} \subset C^6$, mixes in a few steps
independent of $N$.
Therefore, if we define the operator $\Delta$ on $M$ by
$$
\Delta:=\frac{1}{|\widetilde{C}|}\sum_{g\in \widetilde{C}} \rho_2(g),
$$
then $\Delta^8$ has a single eigenvalue $1$ with eigenvectors the
invariant vectors in $M$, and
all other eigenvalues are less than $1/2$ in absolute value.
Thus we have:
$$
\|\Delta^8 v_2 -v _2 \|\geq
\frac{1}{2}\|v_2 - v_{||}\|,
$$
where $v_{||}$ is the projection of $v_2$ onto the space of
all invariant vectors in $M$.
On the other hand,
$$
\|\Delta^8 v_2 -v _2 \|\leq
 8 \| \Delta v_2 -v _2 \| \leq
\frac{8}{|\widetilde{C}|}\sum_{g\in \widetilde{C}}
         \| \rho_2(g) v_2 - v_2 \| \leq 48 \times 1000 \epsilon,
$$
which gives that
\begin{equation}\label{v2}
\|v_2 - v_{||}\| < 10^5 \epsilon.
\end{equation}

The inequalities (\ref{v1}) and (\ref{v2})
imply that
$$
\|v-v_{||}\|  \leq  \| v_1 \| + \| v_2 - v_{||}\| < 10^6 \epsilon.
$$
In particular, if $\epsilon$ is small enough,
then $\|v-v_{||}\| < 1$ and the vector $v_{||}$ is not zero, which shows that there
exist invariant vectors in the representation $\mr{H}$.
Thus, we have shown that
$$
\KC(\Alt(N);F_N) \geq 10^{-6},
$$
which concludes the proof of Theorem~\ref{main}.
\end{proof}


\begin{proof}[Proof of Theorem~\ref{main1}]
By Theorem~\ref{main} the alternating groups $\Alt(n_s)$
are expanders with respect
to some generating set $F_{n_s}$ for $n_s=\left(2^{3s}-1\right)^6$.
The sequence $\left\{n_s\right\}_{s}$
grows exponentially; therefore, for
any sufficiently large $n$ there exists $s$
such that $1< n/n_s < 10^6$. The group $\Alt(n)$ can be written as a product of
a fixed number (less than $~10^{8}$) of copies of $\Alt(n_s)$
embedded in $\Alt(n)$. Using the images of
the sets $F_{n_s}$ one can construct a generating set $F_n$ such that
$$
\KC\left(\Alt(n); F_n\right) \geq 10^{-15}
$$
and $|F_n| \leq 10^{10}$, which completes the proof of the 
first part of Theorem~\ref{main1}.
The construction of the
generating sets $\tilde F_n$ of the symmetric groups is similar.
\end{proof}

The generating set $S$ of $\mySL_{3s}(\F_2)$ can be defined so that all elements
of $S$ are involutions. This allows us to construct an expanding generating
set $F_n$ that consists only of involutions.

The bounds for the size of the generating set $F_n$ and the \KaC\ in the 
proof of Theorem~\ref{main1}
can be significantly improved ---
it is possible to construct a $10$ element generating set
$\bar F_n$  consisting of
involutions such that
$\KC\left(\Alt(n); \bar F_n\right) \geq 10^{-8}$, provided that
$n$ is large enough. N.~Nikolov \cite{Npr} suggested that it is possible
to further improve the bound for the \KaC\ by
using the groups $\mySL_3(\F_q)$ instead of $\mySL_{3s}(\F_2)$,
but this will double the size of the generating set.

\section*{Acknowledgements}

I wish to thank Alex Lubotzky and Nikolay Nikolov 
for their encouragement and useful discussions during the work on this
project. I am also very grateful to Yehuda Shalom and Efim Zelmanov for
introducing me to the subject.



\begin{thebibliography}{10}

\bibitem{A}
M.~Ab{\'e}rt, \emph{Symmetric 
groups as products of abelian subgroups},
Bull. London Math. Soc. \textbf{34} (2002), no.~4, 451--456.
 \MR{1897424 (2002m:20006)}

\bibitem{ALW}
N.~Alon, A.~Lubotzky, and A.~Wigderson, \emph{Semi-direct product in
groups and zig-zag product in graphs: connections and applications (extended
abstract)}, 42nd IEEE Symposium on Foundations of Computer Science (Las
Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, 2001, pp.~630--637.
\MR{1948752}

\bibitem{AR}
N.~Alon and Y.~Roichman, \emph{Random {C}ayley graphs and expanders},
Random Structures Algorithms \textbf{5} (1994), no.~2, 271--284.
\MR{1262979 (94k:05132)}

\bibitem{BHKLS}
L.~Babai, G.~Hetyei, W.~M. Kantor, A.~Lubotzky, and {\'A}.~Seress, \emph{On the
diameter of finite groups}, 31st Annual Symposium on Foundations of Computer
Science, Vol.\ I, II (St.\ Louis, MO, 1990), IEEE Comput. Soc. Press, Los
Alamitos, CA, 1990, pp.~857--865. 
\MR{1150735}

\bibitem{BLK}
L.~Babai, W.~M. Kantor, and A.~Lubotzky, \emph{Small-diameter {C}ayley graphs
for finite simple groups}, European J. Combin. \textbf{10} (1989), no.~6,
507--522. 
\MR{1022771 (91a:20038)}

\bibitem{Bur}
M.~Burger, \emph{Kazhdan constants for {${\rm SL}(3,{\mathbb{Z}})$}}, 
J. Reine Angew.
Math. \textbf{413} (1991), 36--67. 
\MR{1089795 (92c:22013)}

\bibitem{Gilman}
R.~Gilman, \emph{Finite quotients of the automorphism group of a free
group}, Canad. J. Math. \textbf{29} (1977), no.~3, 541--551. 
\MR{0435226 (55:8186)}

\bibitem{K}
M.~Kassabov, \emph{{Kazhdan constants for ${\mathrm{SL}}_n(\mathbb{Z})$}},
\texttt{arXiv:math.GR/0311487}.

\bibitem{Ksymfull}
M.~Kassabov, \emph{{Symmetric groups and expanders}}, in preparation.

\bibitem{KSL3k}
M.~Kassabov, \emph{{Universal lattices and unbounded rank expanders}},
\texttt{arXiv:math.GR/0502237}.

\bibitem{KNFS}
M.~Kassabov and N.~Nikolov, \emph{{Finite simple groups and
expanders}}, in preparation.

\bibitem{KR}
M.~Kassabov and T. R.~Riley, \emph{{Diameters of Cayley graphs of
${\mathrm{SL}}_n(\mathbb{Z}/k\mathbb{Z})$}},\\ 
\texttt{arXiv:math.GR/0502221}.

\bibitem{kazhdan}
D. A.~Kazhdan, \emph{On the connection of the dual space of a group with
the structure of its closed subgroups}, Funktsional. Anal. i Prilozhen.
\textbf{1} (1967), 71--74. 
\MR{0209390 (35:288)}

\bibitem{LR}
Z.~Landau and A.~Russell, \emph{Random {C}ayley graphs are expanders:
a simple proof of the {A}lon-{R}oichman theorem}, Electron. J. Combin.
\textbf{11} (2004), no.~1, Research Paper 62, 6 pp. (electronic).
\MR{2097328}

\bibitem{LS}
P.~Loh and L.~Schulman, \emph{Improved expansion of random cayley graphs},
Disc. Math. and Theor. Comp. Sci. \textbf{6} (2004), 523--528. 
\MR{2097328}

\bibitem{LPS}
A.~Lubotzky, R.~Phillips, and P.~Sarnak, \emph{Ramanujan graphs}, Combinatorica
\textbf{8} (1988), no.~3, 261--277. 
\MR{963118 (89m:05099)}

\bibitem{lubwiess}
A.~Lubotzky and B.~Weiss, \emph{Groups and expanders}, Expanding graphs
(Princeton, NJ, 1992), DIMACS Ser. Discrete Math. Theoret. Comput. Sci.,
vol.~10, Amer. Math. Soc., Providence, RI, 1993, pp.~95--109. 
\MR{1235570 (95b:05097)}

\bibitem{Lpr}
A.~Lubotzky, \emph{private communication}.

\bibitem{expanderbook}
A.~Lubotzky, \emph{Discrete groups, expanding graphs and invariant measures},
Progress in Mathematics, vol. 125, Birkh\"auser Verlag, Basel, 1994.
\MR{1308046 (96g:22018)}

\bibitem{lu}
A.~Lubotzky, \emph{Cayley graphs: eigenvalues, expanders and random walks}, Surveys
in combinatorics, 1995 (Stirling), London Math. Soc. Lecture Note Ser., vol.
218, Cambridge Univ. Press, Cambridge, 1995, pp.~155--189. 
\MR{1358635 (96k:05081)}

\bibitem{LP}
A.~Lubotzky and I.~Pak, \emph{The product replacement algorithm and
{K}azhdan's property ({T})}, J. Amer. Math. Soc. \textbf{14} (2001), no.~2,
347--363 (electronic). 
\MR{1815215 (2003d:60012)}

\bibitem{LubZuk}
A.~Lubotzky and A.~{\.Z}uk, \emph{On property $\tau$}, preprint.\newline
\texttt{http://www.ma.huji.ac.il/~alexlub/BOOKS/On\%20property/On\%20property.pdf}

\bibitem{Mar}
G. A.~Margulis, \emph{Explicit constructions of expanders}, Problemy Peredachi 
Informatsii \textbf{9} (1973), no.~4, 71--80. 
\MR{0484767 (58:4643)}

\bibitem{Npr}
N.~Nikolov, \emph{private communication}.
\pagebreak

\bibitem{RVW}
O.~Reingold, S.~Vadhan, and A.~Wigderson, \emph{Entropy waves, the
zig-zag graph product, and new constant-degree expanders and extractors
(extended abstract)}, 41st Annual Symposium on Foundations of Computer
Science (Redondo Beach, CA, 2000), IEEE Comput. Soc. Press, Los Alamitos, CA,
2000, pp.~3--13. 
\MR{1931799}

\bibitem{Ro}
Y.~Roichman, \emph{Upper bound on the characters of the symmetric groups},
Invent. Math. \textbf{125} (1996), no.~3, 451--485. 
\MR{1400314 (97e:20014)}

\bibitem{Ro1}
Y.~Roichman, \emph{Expansion properties of {C}ayley graphs of the alternating
groups}, J. Combin. Theory Ser. A \textbf{79} (1997), no.~2, 281--297.
\MR{1462559 (98g:05070)}

\bibitem{RSW}
E.~Rozenman, Aner Shalev, and Avi Wigderson, \emph{A new family of Cayley
expanders},  Proceedings of the 36th Annual ACM Symposium on Theory of
Computing,  445--454 (electronic),
ACM, New York, 2004. \MR{2121630}

\bibitem{YSh}
Y.~Shalom, \emph{Bounded generation and {K}azhdan's property ({T})}, Inst.
Hautes \'Etudes Sci. Publ. Math. no.~90 (1999), 145--168 (2001).
\MR{1813225 (2001m:22030)}

\end{thebibliography}

\end{document}