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

DOI10.1016/J.JALGEBRA.2014.08.033zbMATH Open1310.20003arXiv1311.6742OpenAlexW2963915337WikidataQ64356815 ScholiaQ64356815MaRDI QIDQ468709FDOQ468709

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

Publication date: 7 November 2014

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

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).

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

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.

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)

Cites Work

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

Cited In (14)

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

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)