SEMINAR: Groups and Combinatorics Seminar: On the diameter of permutation groups
|Groups and Combinatorics Seminar: On the diameter of permutation groups
Groups and Combinatorics Seminar
Akos Seress (UWA)
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.
Maths Lecture Room 2
Fri, 07 Oct 2011 13:00
Fri, 07 Oct 2011 13:45
Michael Giudici <[email protected]>
Wed, 05 Oct 2011 11:14
- Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
- Download this event as:
Mail this event: