SEMINAR: Groups and Combinatorics Seminar: On the diameter of permutation groups

Groups and Combinatorics Seminar

Akos Seress (UWA)

will speak

On the diameter of permutation groups

at 1pm Friday 7th of October in MLR2

Abstract: Joint work with H. Helfgott. 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 number x such that every element of G can be expressed as a word of length at most x in A and the inverse of A. We are concerned with the diameter under the worst-case generators: diam(G):= max(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 the square root of n (Babai, Seress, 1988). We give a quasipolynomial upper bound for diam(Sym(n)). The same bound applies to the alternating groups.

This addresses a key open case of Babai's conjecture that the diameter of all nonabelian finite simple groups G is bounded by a polylogarithmic function of the group order. The first class of groups for which the conjecture was verified was PSL(2,p), p prime (Helfgott, 2008). This has been generalised to all simple groups of Lie type of bounded rank (Pyber, Szabo, 2011 and Breuillard, Green, Tao, 2011); the unbounded-rank cases are likely to raise combinatorial problems of the type studied in this paper.

By a theorem of Babai, Seress (1992), our result implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n.

Our approach combines ideas on growth in groups (as in (Helfgott, 2008), (Helfgott, 2011)) with an adaptation of older techniques on permutation groups -- most notably (Babai, 1982) and (Pyber, 1993) -- to sets of permutations.