Four random permutations conjugated by an adversary generate S n with high probability

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 probabilityp n > ε for some ε > 0 independent of n , even when an adversary is allowed to conjugate each of the four by a possibly different element ofS 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 orS nexcept 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