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

DOI10.1016/j.jalgebra.2014.08.033zbMath1310.20003arXiv1311.6742OpenAlexW2963915337WikidataQ64356815 ScholiaQ64356815MaRDI QIDQ468709

Seress, Ákos, Harald Andrés Helfgott, Andrzej Żuk

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 groupspermutation groupsspectral gapsdiametersrandom permutationsrandom generators

Mathematics Subject Classification ID

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

Related Items

Random generation of the special linear group, Aldous’s spectral gap conjecture for normal sets, Limit profile for random transpositions, Growth and expansion in algebraic groups over finite fields, Short laws for finite groups and residual finiteness growth, Girth, words and diameter, Isoperimetric profiles and random walks on some groups defined by piecewise actions, Babai's conjecture for high-rank classical groups with random generators, Growth in groups: ideas and perspectives, Double coset Markov chains

Cites Work

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