Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Electronic Research Announcements
Electronic Research Announcements
ISSN 1079-6762

 

Symmetric groups and expanders


Author: Martin Kassabov
Journal: Electron. Res. Announc. Amer. Math. Soc. 11 (2005), 47-56
MSC (2000): Primary 20B30; Secondary 05C25, 05E15, 20C30, 20F69, 60C05, 68R05, 68R10
Published electronically: June 9, 2005
MathSciNet review: 2150944
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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}({Alt}(n), F_n)$ and $\mathcal{C}({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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Electronic Research Announcements of the American Mathematical Society with MSC (2000): 20B30, 05C25, 05E15, 20C30, 20F69, 60C05, 68R05, 68R10

Retrieve articles in all journals with MSC (2000): 20B30, 05C25, 05E15, 20C30, 20F69, 60C05, 68R05, 68R10


Additional Information

Martin Kassabov
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853-4201
Email: kassabov@math.cornell.edu

DOI: http://dx.doi.org/10.1090/S1079-6762-05-00146-0
PII: S 1079-6762(05)00146-0
Keywords: Expanders, symmetric groups, alternating groups, random permutations, property T, Kazhdan constants.
Received by editor(s): March 16, 2005
Published electronically: June 9, 2005
Communicated by: Efim Zelmanov
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.