Four random permutations conjugated by an adversary generate Sn with high probability

Robin Pemantle, Yuval Peres, Igor Rivin

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)

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 Sn generate a transitive subgroup with probability pn > ε for some ε > 0 independent of n, even when an adversary is allowed to conjugate each of the four by a possibly different element of Sn. In other words, the cycle types already guarantee generation of a transitive subgroup; by a well known argument, this implies generation of An or Sn except for probability 1 + o(1) as n → ∞. The analysis is closely related to the following random set model. A random set M ⊆ Z + 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.
Original languageEnglish
Pages (from-to)409-428
Number of pages20
JournalRandom Structures and Algorithms
Volume49
Issue number3
Early online date24 Dec 2015
DOIs
Publication statusPublished - Oct 2016

Keywords

  • Sumset
  • Cycle
  • Poisson
  • Dimension
  • Galois group

Fingerprint

Dive into the research topics of 'Four random permutations conjugated by an adversary generate Sn with high probability'. Together they form a unique fingerprint.

Cite this