Four random permutations conjugated by an adversary generate Sn with high probability1. Issue 3 (24th December 2015)

• Record Type: Journal Article
• Authors: Pemantle, Robin; Peres, Yuval; Rivin, Igor
• Is Part Of: Random structures & algorithms. Volume 49:Issue 3(2016)
• Page Start: 409
• Page End: 428
• Publication Date: 2015-12-24
• Subjects: sumset -- cycle -- Poisson -- dimension -- Galois group; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20632
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We prove a conjecture dating back to a 1978 paper of D.R. Musser [11], namely that four random permutations in the symmetric group S n generate a transitive subgroup with probability p n > ε for some ε > 0 independent of n, even when an adversary is allowed to conjugate each of the four by a possibly different element of S n . In other words, the cycle types already guarantee generation of a transitive subgroup; by a well known argument, this implies generation of A n or S n except for probability 1 + o ( 1 ) as n → ∞ . The analysis is closely related to the following random set model. A random set M ⊆ ℤ + is generated by including each n ≥ 1 independently with probability 1 / n . The sumset sumset ( M ) is formed. Then at most four independent copies of sumset ( M ) are needed before their mutual intersection is no longer infinite. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 409–428, 2016