Symmetric groups and expanders

DOI10.1090/S1079-6762-05-00146-0zbMath1077.20001arXivmath/0503204MaRDI QIDQ4681015

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

zbMATH Keywords

symmetric groupsCayley graphsalternating groupsKazhdan constantsexpandersproperty Trandom permutations

Mathematics Subject Classification ID

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

Related Items

The spectral gap of graphs arising from substring reversals ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ Shadows and intersections: Stability and new proofs ⋮ Symmetric groups and expander graphs. ⋮ Local random quantum circuits are approximate polynomial-designs ⋮ Dimension expanders ⋮ Nonembeddability theorems via Fourier analysis

Cites Work

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