2011/09/16 by H. A. Helfgott, Ákos Seress, Helfgott, Harald A. +1 · 1 citation
Computer Science · Mathematics · #05C25 #20B05 #20B30 #20D60 #20F69 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #Limits and Structures in Graph Theory #Number Theory (math.NT) #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1109.3550
openalex publication_date 2011/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a finite group G and a set A of generators, the diameter diam(Γ(G,A)) of the Cayley graph Γ(G,A) is the smallest ℓ such that every element of G can be expressed as a word of length at most ℓ in A ∪ A-1. We are concerned with bounding diam(G):= maxA diam(Γ(G,A)). It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n, but the best previously known upper bound was exponential in √(n log n). We give a quasipolynomial upper bound, namely, diam(G) = exp(O((log n)4 loglog n)) = exp((log log |G|)O(1)) for G = Sym(n) or G = \Alt(n), where the implied constants are absolute. This addresses a key open case of Babai's conjecture on diameters of simple groups. By standard results, our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n.