The trivial lower bound for the girth of S_n

2017/06/29 by Eberhard, Sean
#Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1706.09972

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→∞. We show that it is at least Ω(n^1/3).

Related

• Girth, words and diameter
• Graphs with large girth and free groups
• Minors in graphs of large θ_r-girth
• On regular hypergraphs of high girth
• Abelian Girth and Girth