Let $g, h$ be a random pair of elements of the permutation group $S_n$. Under the assumption that $g, h$ generate $S_n$, we show that ${\rm diam}({\rm Cay}(S_n, \{g, h, g^{-1}, h^{-1}\})) \leq O(n^2(\log n)^c)$ with probabilty $1-o(1)$ for some constant $c$. We base our proof on the fact that Schreier graphs on the set of $r$-tuples of distinct elements of $\{1, 2,\ldots, n\}$ with respect to the set of $d$ random permutations are almost always good expanders, which we also prove.
|
