This journal is archived by the American Mathematical Society.
The master copy is available at http://www.ams.org/era/
Symmetric groups and expanders
Martin Kassabov
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.
Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
Retrieve entire article
Article Info
- ERA Amer. Math. Soc. 11 (2005), pp. 47-56
- Publisher Identifier: S 1079-6762(05)00146-0
- 2000 Mathematics Subject Classification. Primary 20B30; Secondary 05C25, 05E15, 20C30, 20F69, 60C05, 68R05, 68R10
- Key words and phrases. Expanders, symmetric groups,
alternating groups, random permutations, property T, Kazhdan constants
- Received by editors March 16, 2005
- Posted on June 9, 2005
- Communicated by Efim Zelmanov
- Comments (When Available)
Martin Kassabov
Department of Mathematics, Cornell University, Ithaca, New York 14853-4201
E-mail address: kassabov@math.cornell.edu
Electronic Research Announcements of the AMS Home page