On the diameter of permutation groups

• 成果类型: Article
• 署名作者: Helfgott, Harald A.; Seress, Akos
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2014.179.2.4
• 发表日期: 2014
• 页码: 611-658
• 关键词: graphs; SUBGROUPS

摘要

Given a finite group G and a set A of generators, the diameter diam(Gamma(G, A)) of the Cayley graph Gamma(G, A) is the smallest such that every element of G can be expressed as a word of length at most in AUA(-1). We are concerned with bounding diam(G) := max(A)diam((Gamma 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, root n log n. We give a quasipolynomial upper bound, namely, diam(G) = exp (O((log n)(4) log log n)) = exp ((log log vertical bar G vertical bar)(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 a result of Babai and Seress (1992), our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n.