Pure Maths Colloquium: Wolfram Bentz

Let \(G\) be a permutation group of degree \(n\) on the domain \(\Omega\), and \(k\) a positive integer with \(k\le n\). We say that \(G\) has the \(k\)-existential property, or \(k\)-et, if there exists a \(k\)-subset \(A\) whose orbit under \(G\) contains transversals for all \(k\)-partitions \(\mathcal{P}\) of \(\Omega\).

This property is a substantial weakening of the \(k\)-universal transversal property, or \(k\)-ut, investigated by my coauthors, which required this condition to hold for all \(k\)-subsets \(A\) of the domain \(\Omega\).

Both of these conditions relate to the regularity of transformation semigroups. In the earlier work, the regularity of \(\langle G,t\rangle\) for any map \(t\) of rank \(k\) (with \(k < n/2\)) was shown to be equivalent to the \(k\)-ut property. The question investigated in our new result is if there is a \(k\)-subset \(A\) of the domain such that \(\langle G, t\rangle\) is regular for all maps \(t\) with image \(A\). This turns out to be much more delicate: the \(k\)-et property (with \(A\) as witnessing set) is a necessary, but not sufficient condition.

In this talk we give a nearly complete characterizations of both \(k\)-et and its corresponding regularity condition in the case that \(4\le k\le n/2\).

This is joint work with João Araújo (Universidade Nova) and Peter J. Cameron (St Andrews).