Random generators of the symmetric group: diameter, mixing time and spectral gap
Authors:
- Harald A. HelfgottHHHarald A. Helfgott
- Ákos SeressÁSÁkos Seress
- Andrzej ZukAZAndrzej Zuk
Preprint
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 $n\to \infty$, (a) the diameter of $G$ with respect to $S = \{g,h,g^{-1},h^{-1}\}$ is at most $O(n^2 (\log n)^c)$, and (b) the mixing time of $G$ with respect to $S$ is at most $O(n^3 (\log n)^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).
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Short expressions of permutations as products and cryptanalysis of the Algebraic EraserAdvances in Applied Mathematics, 2012
- Mixing times for random k-cycles and coalescence-fragmentation chainsThe Annals of Probability, 2011
- Mixing Time of the Rudvalis ShuffleElectronic Communications in Probability, 2003
- The action of a few permutations onr-tuples is quickly transitiveRandom Structures & Algorithms, 1998
- Comparison Techniques for Random Walk on Finite GroupsThe Annals of Probability, 1993
- On the Diameter of Random Cayley Graphs of the Symmetric GroupCombinatorics, Probability and Computing, 1992
- Eigenvalues, diameter, and mean distance in graphsGraphs and Combinatorics, 1991
- Small-diameter Cayley Graphs for Finite Simple GroupsEuropean Journal of Combinatorics, 1989
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated AnnealingProbability in the Engineering and Informational Sciences, 1987
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981