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 our proof that the action of $g$ and $h$ on $\ell$-tuples of elements of $\{1,2,\dotsc,n\}$ gives an expander for any constant $\ell$. This generalizes (Broder-Shamir, 1987), which implied the case $\ell=1$.