On the diameter of the symmetric group: polynomial bounds.

zbMATH Open1318.20002MaRDI QIDQ5501375FDOQ5501375

Authors: László Babai, Robert Beals, Ákos Seress 

Publication date: 3 August 2015

Recommendations

• Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
• Bounds on the diameter of Cayley graphs of the symmetric group
• Random generators of the symmetric group: diameter, mixing time and spectral gap.
• Permutations of bounded degree generate groups of polynomial diameter
• Applications of character estimates to statistical problems for symmetric group

zbMATH Keywords

permutationsgenerators of symmetric groupspolynomially bounds on word lengths

Mathematics Subject Classification ID

Symmetric groups (20B30) Generators, relations, and presentations of groups (20F05)

Cited In (17)

• Babai's conjecture for high-rank classical groups with random generators
• Bounds on the diameter of Cayley graphs of the symmetric group
• Applications of finite non-abelian simple groups to cryptography in the quantum era
• Probabilistic and asymptotic aspects of finite simple groups.
• On the diameter of permutation groups.
• Growth and expansion in algebraic groups over finite fields
• Short expressions of permutations as products and cryptanalysis of the algebraic eraser
• Random generation of the special linear group
• Navigating directed Cayley graphs of small diameter: a potent Solovay-Kitaev procedure
• Growth in groups: ideas and perspectives
• Random generators of the symmetric group: diameter, mixing time and spectral gap.
• Permutations of bounded degree generate groups of polynomial diameter
• Some things we've learned (about Markov chain Monte Carlo)
• Diameter of Cayley graphs of \(\mathrm{SL}(n,p)\) with generating sets containing a transvection
• Mini-workshop: Growth and expansion in groups. Abstracts from the mini-workshop held April 7--12, 2024
• Computing short generator sequences
• Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group

This page was built for publication: On the diameter of the symmetric group: polynomial bounds.

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