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.