The trivial lower bound for the girth of $S_n$

Abstract

Consider the Cayley graph of $S_n$ generated by a random pair of elements $x,y$. Conjecturally, the girth of this graph is $Ω(n \log n)$ with probability tending to $1$ as $n\to\infty$. We show that it is at least $Ω(n^{1/3})$.

4 pages