Symmetric groups and expanders

DOI10.1090/S1079-6762-05-00146-0MaRDI QIDQ4681015zbMATH OpenFDO

Authors Martin Kassabov

Publication date 14 June 2005

Published in Electronic Research Announcements of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0503204, https://eudml.org/doc/233451, http://www.emis.de/journals/ERA-AMS/2005-01.html

zbMATH Keywords

alternating groupsCayley graphsexpandersKazhdan constantsproperty Trandom permutationssymmetric groups

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30) Generators, relations, and presentations of groups (20F05) Sums of independent random variables; random walks (60G50)

Abstract: We construct an explicit generating sets $F_n$ and $ilde{F}_n$ of the alternating and the symmetric groups, which make the Cayley graphs $C(Alt(n),F_n)$ and $C(Sym(n),ilde{F}_n)$ 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 other areas of mathematics.

Recommendations

• Symmetric groups and expander graphs.
• Suzuki groups as expanders.
• Iterative construction of Cayley expander graphs
• Finite simple groups as expanders
• scientific article; zbMATH DE number 475373

Cites work

• A new family of Cayley expanders (?)
• Bounded generation and Kazhdan's property (T)
• Diameters of Cayley graphs of Chevalley groups
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expansion properties of Cayley graphs of the alternating groups
• Finite Quotients of the Automorphism Group of a Free Group
• Finite simple groups as expanders
• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• scientific article; zbMATH DE number 475380 (Why is no real title available?)
• scientific article; zbMATH DE number 782054 (Why is no real title available?)
• KAZHDAN CONSTANTS FOR SL_n(ℤ)
• Kazhdan constants for SL (3, Z).
• Ramanujan graphs
• Random Cayley graphs and expanders
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• Small-diameter Cayley graphs for finite simple groups
• SYMMETRIC GROUPS AS PRODUCTS OF ABELIAN SUBGROUPS
• The product replacement algorithm and Kazhdan's property (T)
• Universal lattices and unbounded rank expanders.
• Upper bound on the characters of the symmetric groups

Cited in

(14)

• Expansion properties of Cayley graphs of the alternating groups
• Addendum to ``Random walk in random groups by M. Gromov.
• The spectral gap of graphs arising from substring reversals
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Symmetric groups and expander graphs.
• Dimension expanders
• Nonembeddability theorems via Fourier analysis
• Near-optimal expanding generator sets for solvable permutation groups
• Iterative construction of Cayley expander graphs
• Symmetric groups and conjugacy classes
• scientific article; zbMATH DE number 15662 (Why is no real title available?)
• Local random quantum circuits are approximate polynomial-designs
• Highly symmetric expanders
• Shadows and intersections: Stability and new proofs

This page was built for publication: Symmetric groups and expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4681015)