Symmetric Groups and Expander Graphs

Simple item page
dc.creatorKassabov, Martin
dc.date2005-05-28
dc.date.accessioned2026-07-07T05:20:20Z
dc.date.available2026-07-07T05:20:20Z
dc.descriptionWe 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.
dc.description30 pages
dc.identifierhttps://arxiv.org/abs/math/0505624
dc.identifierhttp://arxiv.org/abs/math/0505624
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/75345
dc.subjectGroup Theory
dc.subjectCombinatorics
dc.subjectPrimary 20B30; Secondary 05C25, 05E15, 20C30, 20F69
dc.titleSymmetric Groups and Expander Graphs
dc.typetext

Files

Collections

arXiv