The existential transversal property

One of the first things that João Araújo introduced me to when we started collaborating, after synchronization, was the universal transversal property: a permutation group G on the set {1,…,n} has the k-universal transversal property (k-ut for short) if, given any k-subset A and k-partition P of the domain, there is an element of G mapping A to a transversal to P. (Here I say “k-subset” for a subset with k elements, and “k-partition” for a partition with k parts.

This appealed to me because it resembles the classical notion of k-homogeneity (or k-set transitivity): G has this property if, given any two k-sets A and B, there is an element of G mapping the first to the second.

One of the first results on this was by Livingstone and Wagner in 1964. Their paper has three main theorems; the first says that, if k ≤ n/2, then a k-homogeneous group is (k−1)-homogeneous. The proof of this theorem is a short and elegant application of character theory, which can be rewritten as pure combinatorics. João and I were able to prove that, under the same restriction, a group with the k-ut property also has the (k−1)-ut property. Our proof, however, was much less short and elegant, involving some nontrivial group theory (including the Classification of Finite Simple Groups.)

It turns out that this is relevant to semigroup theory. Let t be a mapping of the domain which has rank k (image of size k). Semigroup theorists will not be surprised to learn that, if G has k-ut, then every such map is regular in ⟨G,t⟩ (that is, has a von Neumann inverse). But then our result implies that the same is true for all elements of smaller rank as well; that is, the entire semigroup ⟨G,t⟩ is regular.

In the paper we went on to classify the groups with k-ut (with some exceptions we were unable to decide) for 3 ≤ k ≤ n/2. (It turns out, happily, that the 2-ut property is exactly equivalent to primitivity, so we didn’t feel obliged to give a complete list.)

So what next? We went on to consider the k-existential transversal property, or k-et for short. This requires that there is a “witnessing” k-set A such that, for any k-partition P, there is an element of G mapping A to a transversal for P. This is substantially weaker than the k-ut property, but does have the consequence for semigroups that, if the image of t is a witnessing set for k-et, then t is regular in ⟨G,t⟩. The problems are considerably harder, and we had to recruit Wolfram Bentz to help us.

It turns out that one can say quite a bit. We suppose that G satisfies k-et, with k ≤ n/2, as before. We can deal completely with the case that G is intransitive: for k ≥ 3, it must fix a point and act (k−1)-homogeneously on the remaining points. So we can suppose that G is transitive. Here are some of our conclusions.

  • If k ≥ 8, then G must be the symmetric or alternating group. 8 is best possible here: the Mathieu group M24 has the 7-et property.
  • There are groups satisfying k-et but not (k−1)-et: indeed, just two of them, the groups 24:A8 and 24:A7, with degree 16, satisfy k-et for k = 1,2,3,4,6 but not for k = 5.
  • If k ≥ 4, then G is is primitive (for n ≥ 9); and it is 2-homogeneous, with just two exceptions: the Higman–Sims group and its automorphism group, acting on 100 points.

Now if G is k-et with witnessing set A, and also is (k−1)-ut, and t is a map with image A, then ⟨G,t⟩ is regular; since as we explained above the elements of rank k (whose images are of the form Ag for gG) are regular, and the (k−1)-ut property ensures that all maps of smaller rank in the semigroup are regular. But the condition of (k−1)-ut is not necessary for regularity; if it fails, then the semigroup may or may not be regular, and in most cases we can say which possibility occurs.

The methods we needed to develop to tackle this harder problem turn out to be useful in advancing further our knowledge of groups with the k-ut property, so we also had a glance at this, which included correcting a couple of small mistakes in the earlier paper.

The et paper has just appeared on the arXiv: 1808.06085.

What next? There is a dual form of k-et, where we specify a witnessing k-partition P, and ask that any k-set has an image under G which is a transversal for P. A job for another day.

Of course, the ultimate in this line would be a complete characterisation of the pairs (G,t) for which ⟨G,t⟩ is regular. This is not currently on our radar screen, though.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.