arXiv Analytics

Sign in

arXiv:math/0505624 [math.GR]AbstractReferencesReviewsResources

Symmetric Groups and Expander Graphs

Martin Kassabov

Published 2005-05-28Version 1

We construct explicit generating sets S_n and \tilde S_n of the for the alternating and the symmetric groups, which turn the Cayley graphs C(Alt(n), S_n) and C(Sym(n), \tilde S_n) into a family of bounded degree expanders for all n. This answers affirmatively an old question which has been asked many times in the literature. These expanders have many applications in the theory of random walks on groups, card shuffling and other areas.

Comments: 30 pages
Categories: math.GR, math.CO
Subjects: 20B30, 05C25, 05E15, 20C30, 20F69
Related articles: Most relevant | Search more
arXiv:math/0503204 [math.GR] (Published 2005-03-10)
Symmetric Groups and Expanders
arXiv:2107.06248 [math.GR] (Published 2021-07-13)
Abelian sections of the symmetric groups with respect to their index
arXiv:math/0502237 [math.GR] (Published 2005-02-11)
Universal lattices and unbounded rank expanders

Links

Toolbox