The trivial lower bound for the girth of $S_n$

Sean Eberhard

Consider the Cayley graph of $S_n$ generated by a random pair of elements $x,y$. Conjecturally, the girth of this graph is $\Omega (n\log n)$ with probability tending to $1$ as $n\to\in…