On the Girth of Random Cayley Graphs
We prove that random d-regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (log(d-1) |G|)(1/2)/2 and that random d-regular Cayley graphs of simple algebraic groups over F(q) asymptotically almost surely have girth at least log(d-1) |G|/dim(G). For the symmetric p-groups the girth is between log log |G| and (log |G|)(alpha) with alpha < 1. Several conjectures and open questions are presented. (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 35, 100-117, 2009
girth random cayley graphs