UWA Logo What's On at UWA
   UWA HomeProspective Students  | Current Students  | Staff  | Alumni  | Visitors  | About  |     Search UWA    for      

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

* Login to add events... *
Today's date is Wednesday, October 21, 2020
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 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.
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:
Additional Information:
  • 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:

Top of Page
© 2001-2010  The University of Western Australia
Questions? Mail [email protected]