
The Action of a Few Permutations on rtuples is Quickly Transitive
 Postscript version.
 Dvi version.
 PDF version.

Abstract:
We prove that for every $r$ and $d \geq 2$ there is a $C$ such that
for most choices of $d$ permutations $\pi_1,\pi_2,\dots,\pi_d$ of
$S_n$, the following holds: for any two $r$tuples of distinct elements
in $\{1,\ldots,n\}$, there is a product of less than $C \log n$ of the
$\pi_i$'s which map the first $r$tuple to the second. Although we came
across this problem while studying a rather unrelated cryptographic
problem, it belongs to a general context of which random Cayley graph
quotients of $S_n$ are good expanders.
