Girth, words and diameter

2019/03/02 by Martin W. Liebeck, Liebeck, Martin W., Aner Shalev +1 · 1 citation
Mathematics · #05C12 (Secondary) #05C80 #20D06 (Primary) #20P05 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Geometric and Algebraic Topology #Group Theory (math.GR) #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1903.00748

openalex publication_date 2019/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the girth of Cayley graphs of finite classical groups G on random sets of generators. Our main tool is an essentially best possible bound we obtain on the probability that a given word w takes the value 1 when evaluated in G in terms of the length of w, which has additional applications. We also study the girth of random directed Cayley graphs of symmetric groups, and the relation between the girth and the diameter of random Cayley graphs of finite simple groups.

Cited by

• On the asymptotic equidistribution of word values in symmetric groups

Related

• The trivial lower bound for the girth of S_n
• The thresholds for diameter 2 in random Cayley graphs
• Diameters of random Cayley graphs of finite nilpotent groups
• The diameter of a random Cayley graph of Z_q
• Bounds on the diameter of Cayley graphs of the symmetric group