Premium
Four random permutations conjugated by an adversary generate S n with high probability
Author(s) -
Pemantle Robin,
Peres Yuval,
Rivin Igor
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20632
Subject(s) - mathematics , combinatorics , intersection (aeronautics) , conjecture , random element , set (abstract data type) , permutation (music) , random permutation , discrete mathematics , transitive relation , group (periodic table) , random variable , symmetric group , computer science , statistics , physics , chemistry , organic chemistry , acoustics , engineering , programming language , aerospace engineering
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