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 (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.

20 pages

Cited by in corpus (12)

• High-dimensional structure estimation in Ising models: Local separation criterion
• Lower Bounds for Local Approximation
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Regular graphs of large girth and arbitrary degree
• Diophantine properties of nilpotent Lie groups
• First-order limits, an analytical perspective
• Expansion in finite simple groups of Lie type
• Cutoff on Graphs and the Sarnak-Xue Density of Eigenvalues
• Thin II_1 factors with no Cartan subalgebras
• The spectrum of the random environment and localization of noise
• Dixon's asymptotic without CFSG
• Expansion of coset graphs of PSL_2(F_p)