Symmetric groups and expander graphs

By Martin Kassabov. 2005

116 citations recorded by the source corpus.

We construct explicit generating sets Sn and $\tilde{S}_{n}$ of the alternating and the symmetric groups, which turn the Cayley graphs $\mathcal{C}(\text{Alt}(n), S_{n})$ and $\mathcal{C}(\text{Sym}(n), \tilde{S}_{n})$ into a family of bounded degree expanders for all n.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/3e95dae50593e862c04bc7296bdc6a167db07b79

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Expander graphs in pure and applied mathematics (2011, methodology): “Making the symmetric groups (or equivalently the Alternating groups) into a family of expanders in a uniform way has been a challenging problem for almost two decades, until it was solved by Kassabov [K2]. Theorem 2.11. There exists k2Nand 0 <"2Rsuch that for every n 5;Sym(n) has a symmetric”
Local random quantum circuits are approximate polynomial-designs: numerical results (2012, background): “[52] M.”
Growth in groups: ideas and perspectives (2013, unknown): “67]), but the case of general Awas open, just as for n= 2. Kassabov applied what was known for SLn (and linear algebraic groups in general) to prove the existence of expanders for the symmetric group [Kas07]. Other relevant works are [SX91] (giving an elementary treatment of expansion for Aas in (2.”
Expansion in finite simple groups of Lie type (2013, background): “The proofs of the works of Kassabov, Lubotzky and Nikolov [KLN, Lu1] used very different arguments coming from a rather impressive range of mathematical areas.”