Probability of generation by random permutations of given cycle type

Abstract

Suppose $\pi$ and ${\pi }^{\prime }$ are two random elements of $S_n$ with constrained cycle types such that $\pi$ has $x{n}^{1/2}$ fixed points and $yn/2$ two-cycles, and likewise ${\pi }^{\prime }$ has $x^{\prime }{n}^{1/2}$ fixed points and $y^{\prime }n/2$ two-cycles. We show that the events that $G=⟨\pi ,{\pi }^{\prime }⟩$ is transitive and $G\ge A_n$ both have probability approximately \[(1 - yy')^{1/2} \exp\left(- \frac{xx' + \frac12 x^2 y' + \frac12 {x'}^2 y}{1 - yy'}\right),\] provided $(x,x^{\prime })$ is not close to $(0,\infty )$ or $(\infty ,0)$. This formula is derived from some preliminary results in a recent paper (arXiv:1904.12180) of the authors. As an application, we show that two uniformly random elements of uniformly random conjugacy classes of $S_n$ generate the group with probability about 51%.

4 pages