Four random permutations conjugated by an adversary generate Sn with high probability1. Issue 3 (24th December 2015) - Pemantle, Robin; Peres, Yuval; Rivin, Igor
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