The action of a few permutations on r-tuples is quickly transitive

We prove that for every r and d≥2 there is a C such that for most choices of d permutations π₁, π₂,…,π_d of S_n, the following holds: for any two r-tuples of distinct elements in {1,…,n}, there is a product of less than C log n of the π_is 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. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 335–350, 1998