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

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 \mathrm{\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)themixingtimeof$G$withrespectto$S$isatmost$O(n^3 (\log n)^c)$\mathrm{.}(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 $\mathrm{\ell }$-tuples, where $\mathrm{\ell }$ is an arbitrary constant (Friedman et al., 1998).