Discrete mathematics seminar - The relational complexity of a finite permutation group

Speaker: Nick Gill (Open University)

Abstract: Let G be a group acting on a set X. The relational complexity of this action is a positive integer that indicates how efficiently one can represent G as the automorphism group of a homogeneous relational structure with vertex set X. This horrible-sounding definition can actually be rather easily understood by thinking about groups acting on graphs, and for the first third of the talk we will explore this point of view.

In the middle third of the talk we will discuss some of the theorems that model theorists have proved using the idea of relational complexity. These theorems concern the structure and organisation of "the universe of finite permutation groups". In the final third of the talk we will discuss recent attempts by a variety of authors to calculate and/or bound the relational complexity of specific families of finite permutation groups.

I will probably mention joint work with various people including Dalla Volta, Hudson, Hunt, Liebeck, Loda and Spiga.