The existential transversal property: A generalization of homogeneity and its impact on semigroups

Let $G$ be a permutation group of degree $n$, and $k$ a positive integer with $k\le n$. We say that $G$ has the $k$-existential transversal property, or $k$-et, if there exists a $k$-subset $A$ (of the domain $\Omega$) 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 the first and third author, which required this condition to hold for all $k$-subsets $A$ of the domain $\Omega$.

Our first task in this paper is to investigate the $k$-et property and to decide which groups satisfy it. For example, it is known that for $k< 6$ there are several families of $k$-transitive groups, but for $k\ge 6$ the only ones are alternating or symmetric groups; here we show that in the $k$-et context the threshold is $8$, that is, for $8\le k\le n/2$, the only transitive groups with $k$-et are the symmetric and alternating groups; this is best possible since the Mathieu group $M_{24}$ (degree 24) has $7$-et. We determine all groups with $k$-et for $4\le k\le n/2$, up to some unresolved cases for $k=4,5$, and describe the property for $k=2,3$ in permutation group language. These considerations essentially answer Problem 5 proposed in the paper on $k$-ut referred to above; we also slightly improve the classification of groups possessing the $k$-ut property.

In that earlier paper, the results were applied to semigroups, in particular, to the question of when the semigroup $\langle G,t\rangle$ is regular, where $t$ is a map of rank $k$ (with $k<n/2$); this turned out to be equivalent to the $k$-ut property. The question investigated here is when 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 condition, and the combination of $k$-et and $(k-1)$-ut is sufficient, but the truth lies somewhere between.

Given the knowledge that a group under consideration has the necessary condition of $k$-et, the regularity question for $k\le n/2$ is solved except for one sporadic group.

The paper ends with a number of problems on combinatorics, permutation groups and transformation semigroups, and their linear analogues.