On the diameter of permutation groups

By Harald Andrés Helfgott, Á. Seress. 2011

59 citations recorded by the source corpus.

Given a finite group G and a set A of generators, the diameter diam(G(G,A)) of the Cayley graph G(G,A) is the smallest l such that every element of G can be expressed as a word of length at most l in A?A -1 . We are concerned with bounding diam(G):=max A diam(G(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 nlogn - - - - - v . We give a quasipolynomial upper bound, namely, diam(G)=exp(O((logn) 4 loglogn))=exp((loglog|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 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 .

Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/35d7498b0f25cec896cb95077071ee87f21ce0c7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

  1. Ben Steinberg
  2. Peter J. Cameron
  3. Leandro Vendramin

In Electrical and Electronic Engineering

  1. Ben Steinberg
  2. Peter J. Cameron

Citations in the corpus