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 $\Omega (n\log n)$ with probability tending to $1$ as $n\to \infty$. We show that it is at least $\Omega (n^{1/3})$.

4 pages

Cited by in corpus (3)

• Babai's conjecture for high-rank classical groups with random generators
• Dixon's asymptotic without CFSG
• Girth, words and diameter