Combinatorics Seminar 2018

Speaker: Peter Cameron, University of St Andrews

Date: Mon, Oct 08, 2018

Time: 16:30 - 17:30

Venue: Middle Meeting Room

Title: The existential transversal property


It is reasonable to expect that the structure of a transformation semigroup will be controlled, to some extent, by its permutation group of units, or by its normaliser in the symmetric group. But only recently, using the Classification of Finite Simple Groups, have significant steps in this direction been taken.

A semigroup $S$ is regular if each of its elements $x$ has a (von Neumann) generalised inverse $y$, satisfying $xyx=x$ and $yxy=y$. This is one of the most important properties of semigroups. So we could ask: when is a transformation semigroup $S$ with group of units $G$ regular? In particular, for which pairs $(G,t)$, where $G$ is a permutation group and $t$ a non-permutation, is the semigroup generated by $G$ and $t$ regular?

Two properties of a permutation group $G$ are relevant to this question. We say that $G$ has the $k$-universal transversal property if, for every $k$-set $A$ and $k$-partition $P$, there is an element $g\in G$ such that $Ag$ is a transversal to $P$; it has the $k$-existential transversal property if there exists a set $A$ (a witnessing set) such that, for any $P$, there exists $g$ such that $Ag$ is a transversal for $P$.

For $k\le n/2$, $G$ has the $k$-universal transversal property if and only if, for every map $t$ of rank $k$, $\langle G,t\rangle$ is regular. Analogously we might expect that $G$ has the $k$-existential transversal property if and only if, for every map $t$ whose image is the witnessing set $A$, the semigroup $\langle G,t\rangle$ is regular. This is not true, but we have found an almost complete classification of groups with the $k$-et property for $4\le k\le n/2$, and in most cases we can decide which of them produce regular semigroups in this fashion.

This is joint work with João Araújo and Wolfram Bentz.

Slides: View slides