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


Groups and Combinatorics Seminar: On the diameter of permutation groups 
Other events...

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 worstcase 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 unboundedrank 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.
Speaker(s) 
Akos Seress

Location 
Maths Lecture Room 2


Contact 
Michael Giudici
<[email protected]>

Start 
Fri, 07 Oct 2011 13:00

End 
Fri, 07 Oct 2011 13:45

Submitted by 
Michael Giudici <[email protected]>

Last Updated 
Wed, 05 Oct 2011 11:14

Included in the following Calendars: 

 Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
 Download this event as:
Text 
iCalendar

Mail this event:
