On the girth of random cayley graphs

Abstract

We prove that random d-regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (logd-1 |G|)1/2/2 and that random d-regular Cayley graphs of simple algebraic groups over Fq asymptotically almost surely have girth at least logd-1 |G|/ dim(G). For the symmetric p-groups the girth is between log log|G|and (log|G|)α with α < 1. Several conjectures and open questions are presented. © 2009 Wiley Periodicals, Inc.