Algebra Seminar "Bases and relational complexity", by Colva Roney-Dougal (University of St Andrews)

Title: Bases and relational complexity

Abstract: Let G be a permutation group on a set X. An irredundant base for G is a sequence (x_1, ..., x_b) of elements of X such that the corresponding sequence of point stabilisers satisfies
 

G > G_{x_1} > G_{x_1, x_2} > ... > G_{x_1, ..., x_b} = 1.

As well as giving insight into the nature of group actions, bases have important applications to computational group theory, and this talk will start with lots of examples and a survey of key results in the area.  We’ll then go on to look at an unexpected connection to model theory, via the notion of relational complexity. Informally speaking, the relational complexity of a permutation group measures the extent to which local information about the action of group elements determines global information. We’ll finish with some results from  this rapidly-developing field.