Partition homogeneity

This post discusses a paper by Jorge André, João Araújo and me, which has just been accepted for the Journal of Algebra. There is a slight tangle to the history of this paper, which I want to describe.

First a pair of definitions. The first goes back to the earliest days of permutation group theory; the second dates from the twentieth century. Throughout this post, G is a permutation group on the finite set Ω = {1,…,n}. Let k be a positive integer smaller than n.

  • G is ktransitive if, given any two sets of k distinct elements of Ω, there are elements of G mapping the first to the second in all possible orders.
  • G is khomogeneous if, given any two sets of k distinct elements of Ω, there is an element of G mapping the first to the second in some order.

Clearly a k-transitive group is k-homogeneous. Conversely, Don Livingstone and Otto Wagner proved in 1964 the lovely result that, if 5 ≤ k ≤ n/2, then a k-homogeneous group is k-transitive. Subsequently, Bill Kantor determined all groups which are k-homogeneous but not k-transitive for k = 2, 3, 4.

The determination of all k-transitive groups for k ≥ 2 had to await the Classification of Finite Simple Groups, and is one of its best-known consequences (though requiring quite a bit of further work by many mathematicians).

It was not until 2006 that Bill Martin and Bruce Sagan extended the definition of transitivity to apply to partitions rather than subsets. Let λ be a partition of n (a non-increasing sequence of positive integers with sum n). A partition of Ω has shape λ if the sizes of its parts are the parts of λ. Now a permutation group G is λ-transitive if, given any two partitions of Ω with shape λ, there is an element of G carrying the ith part of the first partition to the ith part of the second, for all i. Martin and Sagan proved several nice results about such groups. For example, if λ dominates μ in the natural partial order on partitions of n, then a μ-transitive group must be λ-transitive.

The stabiliser of a partition (in the symmetric group) is a corresponding Young subgroup.

Later, Alex Dent and I defined a notion of orbit λ-transitivity, applying to intransitive groups. Instead of requiring that we map between any two partitions of the same shape, we only ask this if the two set partitions induce partitions of the same shape on each orbit of the group. This was motivated by a question in design theory that had arisen in Alex’s thesis.

What was missing is the notion of a λ-homogeneous group, one in which, given any two partitions of Ω of shape λ, there is a permutation in the group mapping the first to the second in some order. Thus, in the case of the partition λ = (nk,1,…1) (with k ones), λ-transitivity is equivalent to k-transitivity, and λ-homogeneity to k-homogeneity.

(The stabiliser of an (unordered) partition contains the Young subgroup, but is allowed to permute among themselves parts of the same size.)

This gap has now been filled, and all permutation groups which are λ-homogeneous or λ-transitive have been satisfactorily classified.

But there is a complication. Jorge André, João Araújo and I wrote a paper including these results, with an application to transformation semigroups, discussed below. We put our paper on the arXiv on 28 April 2013, and submitted it to a journal which once prided itself on its interdisciplinarity. After a long delay, the editor reported being unable to find a referee who understood both the group theory and the semigroup theory, and suggested that we submit the paper to a specialist journal (a somewhat curious response, I thought). So we submitted it to the Journal of Algebra, and it has just been accepted.

Meanwhile, and without our knowledge, Ted Dobson and Aleksander Malnič wrote a paper “Graphs that are transitive on all partitions of given shape” containing this classification, which was published in J. Algebraic Combinatorics 42 (2015), 605–617. The journal lists it as “Received 2 December 2013”. This paper was never put on the arXiv. It is not possible for me to say who was first, since it may be that Dobson and Malnič also had a delay with another journal.

Actually I don’t care at all who was first. Michael Atiyah, in an interview in the European Mathematical Society Newsletter in September 2004, defended the view that it is always good to have more than one proof of an important theorem:

I think it is said that Gauss had ten different proofs for the law of quadratic reciprocity. Any good theorem should have several proofs, the more the better. For two reasons: usually, different proofs have different strengths and weaknesses, and they generalise in different directions – they are not just repetitions of each other.

In this case, Dobson and Malnič used the result to determine which Johnson graphs are Cayley graphs.

Our application is completely different. We determine all permutation groups G having the property that, for any non-permutation a, the non-units in the transformation monoid generated by G and a are the same as those in the monoid generated by the symmetric group Sn and a. Since in the latter case the semigroups of non-invertible elements are very well studied (beginning with Levi and McFadden in 1994, who called them Sn-normal semigroups) and have many beautiful properties, we are able to extend these properties to the much more general situation where an arbitrary group replaces the symmetric group, wherever possible.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, history 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.