 |
The Action of a Few Permutations on r-tuples 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.
|