Random generators of the symmetric group: diameter, mixing time and spectral gap.

DOI10.1016/J.JALGEBRA.2014.08.033MaRDI QIDQ468709zbMATH OpenOpenAlexWikidataFDO

Authors Harald A. Helfgott, Ákos Seress, Andrzej Zuk

Publication date 7 November 2014

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.6742

zbMATH Keywords

symmetric groupsspectral gapsrandom permutationspermutation groupsrandom generatorsdiameters

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30) Generators, relations, and presentations of groups (20F05) Probabilistic methods in group theory (20P05)

Abstract: Let $g$, $h$ be a random pair of generators of $G=Sym(n)$ or $G=Alt(n)$. We show that, with probability tending to $1$ as $noinfty$, (a) the diameter of $G$ with respect to $S=g,h,g^{-1},h^{-1}$ is at most $O(n^2(logn{)}^c)$, and (b) the mixing time of $G$ with respect to $S$ is at most $O(n^3(logn{)}^c)$. (Both $c$ and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott--Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on a combination of the algorithm in (Babai--Beals--Seress, 2004) and the fact that the action of a pair of random permutations is almost certain to act as an expander on $ell$-tuples, where $ell$ is an arbitrary constant (Friedman et al., 1998).

Recommendations

• Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
• On the diameter of the symmetric group: polynomial bounds.
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• scientific article; zbMATH DE number 5150116
• On the diameter of permutation groups.

Cites work

• scientific article; zbMATH DE number 51906 (Why is no real title available?)
• scientific article; zbMATH DE number 1022658 (Why is no real title available?)
• scientific article; zbMATH DE number 2042290 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• Applications of character estimates to statistical problems for symmetric group
• Comparison techniques for random walk on finite groups
• Eigenvalues, diameter, and mean distance in graphs
• Generating a random permutation with random transpositions
• Growth in groups: ideas and perspectives
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing time of the Rudvalis shuffle
• Mixing times for random \(k\)-cycles and coalescence-fragmentation chains
• Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• On the diameter of permutation groups.
• On the diameter of the symmetric group: polynomial bounds.
• Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique
• Short expressions of permutations as products and cryptanalysis of the algebraic eraser
• Small-diameter Cayley graphs for finite simple groups
• Some Characters of the Symmetric Group
• Some things we've learned (about Markov chain Monte Carlo)
• The action of a few permutations onr-tuples is quickly transitive
• Upper bound on the characters of the symmetric groups

Cited in

(14)

• Mini-workshop: Growth and expansion in groups. Abstracts from the mini-workshop held April 7--12, 2024
• Babai's conjecture for high-rank classical groups with random generators
• Upper bounds for the diameter of a direct power of non-abelian solvable groups
• Double coset Markov chains
• Isoperimetric profiles and random walks on some groups defined by piecewise actions
• Limit profile for random transpositions
• On the diameter of the symmetric group: polynomial bounds.
• Growth and expansion in algebraic groups over finite fields
• Aldous's spectral gap conjecture for normal sets
• Girth, words and diameter
• Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
• Random generation of the special linear group
• Short laws for finite groups and residual finiteness growth
• Growth in groups: ideas and perspectives

This page was built for publication: Random generators of the symmetric group: diameter, mixing time and spectral gap.

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