Resumen de On the diameter of permutation groups

Harald Andrés Helfgott , Akos Seress

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