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

✍ Scribed by Joel Friedman; Antoine Joux; Yuval Roichman; Jacques Stern; Jean-Pierre Tillich

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 212 KB
• Volume: 12
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199807)12:4<335::aid-rsa2>3.0.co;2-u

✦ Synopsis

We prove that for every r and dG 2 there is a C such that for most choices of d permutations , , . . . , of S , the following holds: for any two r-tuples of distinct 1 2 d n Ä 4 elements in 1, . . . , n , there is a product of less than C log n of the s which map the first i 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 are good expanders.