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.

Posted in exposition | Tagged , , , | Leave a comment


Today is the 50th anniversary of my arrival in Europe. I arrived in Southampton on the Shaw Savill Line ship “Southern Cross” on 21 August 1968, after a 36-day voyage from Sydney. I intended to stay three years or so to get my doctorate, but in the event I am still living here, having been given indefinite leave to remain in the United Kingdom in 1971.

Southern Cross

When I visit Autralia, it always feels like home. But I feel comfortable in Europe (though a bit less so now, since the rise of nationalism in many parts of the continent, something I don’t understand).

I suppose that in some sense I count as one of the “Windrush generation”.

Posted in history | Tagged , , , | 11 Comments


Derek Robertson

Derek Robertson is an artist based in Balmerino in Fife, site of a ruined abbey and subject of a poem by William McGonagall. His studio is right on the Fife Coastal Path. His main interest is wildlife, and in my view he is extremely good at depicting it. Take a look at his website.

One of his interests was in depicting migrating birds, and he had travelled to North Africa and the Middle East in his researches. A couple of years ago, when the world watched appalled at the plight of human migrants, he recognised some of the places he had visited, and decided that he had to get involved. So he travelled there, helped the migrants in various ways, and produced a series of paintings with the title “Migrations”, combining images of migrating birds and migrating humans (the latter often in terrible conditions).

Indeed, the picture he is pointing to in the photo (work in progress) is based on a remarkable event that he witnessed in Jordan; but I can’t really tell it here, and anyway you can’t even see the incomplete picture very well in my photo.

He was a featured exhibitor at the recent Pittenweem Arts Festival. His exhibition in the Old Town Hall was of wildlife pictures, but a smaller exhibition in the Church Hall showed pictures from his Migrations series.

Enough to say that I was blown away by these, although they were not for sale. But we met Derek later when we got to the Town Hall, and he said that he could arrange for one to be printed for us.

The one I chose was called “For the wayfarer that you meet”, and featured a bee-eater against a background showing the hospitality of the people of Jordan to travelling guests. Apart from the fact that I think it is a great painting, the bee-eater brings back memories of being entertained by this colourful and extremely agile flier in a park in Cairns some years ago. If you go to this page and scroll down, you can see an image of the picture, and also read about the creation of this remarkable series.

Today the print was ready, so I took the bus from St Andrews to Balmerino Road End and walked down into the village to Derek’s cottage to collect the print. Derek was kind enough to make me a cup of tea and then take me to the bus stop afterwards.

Posted in Uncategorized | Tagged , , , , | Leave a comment

Congratulations to Ali Nesin

I was delighted to see, among the list of prizewinners at the ICM, that Ali Nesin has been awarded the Leelavati Prize (for outstanding contributions to public outreach in mathematics by an individual). The citation says the prize is awarded

for his outstanding contributions towards increasing public awareness of mathematics in Turkey, in particular for his tireless work in creating the “Mathematical Village” as an exceptional, peaceful place for education, research and the exploration of mathematics for anyone.

Posted in Uncategorized | Tagged , , | 4 Comments

Open access and the arXiv

HEFCE is dead, long live Research England(?)

This new body is responsible for the REF. Their website makes the following statement about open access:

Open access is central to UK Research and Innovation’s ambitions for research and innovation in the UK. The UK Funding Bodies, including Research England, are committed to supporting successful approaches to open access publishing through the Research Excellence Framework 2021. It is now a requirement that certain research outputs submitted to any research assessment exercise after 2014 be made as widely accessible as possible.

But we have just learned that by far the most successful repository of open access papers in our subject, the arXiv, is to be disallowed. Can they do this retrospectively? Who knows. Experience suggests that protests from the academic community, however well supported, have little effect.

Apparently the reason they gives is that there is no mechanism for linking a paper on the arXiv with the published version of the paper. It appears that they trust panel members to read papers and judge their quality, but they don’t trust them to check that the arXiv version matches the published version.

If this policy is confirmed, it is a denial of the principle in their fine sounding statement above, as well as a total misunderstanding about how open access is used by the academic community. It reinforces the view that the people judging research know little about how research is actually done.

Here, on the arXiv, is a paper arguing that arXiv publication is not only REF-compliant but better for purpose than institutional repositories. (In my case, I haven’t for many years looked on an institutional repository for a paper, but I use the arXiv very frequently.)

Final note: XKCD has had his say on for-profit journals here.

Posted in Uncategorized | Tagged , , , | 10 Comments

Open access, once again

It seems to me that “open access”, in academic publishing, should include authors as well as readers; that is, there should be no heavy page charges for publishing an article (a small administrative charge is probably acceptable), and there should of course be no charges for reading it.

However, as we know, academic publishing has one of the highest profit margins among legitimate industries, and the big publishers are prepared to do what is necessary to keep it that way, including changing the meaning of “open access” so that it does not include readers. They have to do so; it is their legal duty to their shareholders to maximise profits.

So it is our responsibility to keep a close eye on what is going on in the world of academic publishing, and to support the models we believe in by our actions.

I am writing this now because, while browsing this morning (in very constrained free time), I came on two things which are relevant to this discussion.

First, the Fair Open Access Alliance, who enunciate five “Fair Open Access Principles”:

  1. The journal has a transparent ownership structure, and is controlled by and responsive to the scholarly community.
  2. Authors of articles in the journal retain copyright.
  3. All articles are published open access and an explicit open access licence is used.
  4. Submission and publication is not conditional in any way on the payment of a fee from the author or its employing institution, or on membership of an institution or society.
  5. Any fees paid on behalf of the journal to publishers are low, transparent, and in proportion to the work carried out.

I came to this indirectly from Tim Gowers’ blog: he has a post advertising a new open access journal, Advances in Combinatorics, but he also has a discussion of the present situation, in which he mentions that Acta Mathematica is “one of a tiny handful of very top journals”, which is fully open access with no author fees. So, in his opinion, “for a really good paper it is a great option.”

At the same time, a colleague sent me a list of the pure mathematics journals with the highest impact factors. (The figures are from about seven years ago, so maybe a little out of date, but still a fair indication.) As it happens, Acta is top of the list; but, as far as I can see, no other open access journals are there. Other observations can be made from this list. For example, there are six specialist journals in the list. Five of them have the word “geometry” in the title. (The sixth is in dynamical systems.) Not a single specialist journal in any part of algebra, combinatorics, or logic makes the cut. I offer this observation without explanation. It is not a matter of mathematical elitism since impact factors, if not sensible, are at least transparent, based on citations. However, the list is biased against new journals (including many newly-founded open access journals), both because of its age, and also because of the long publication times in mathematics.

The list of current members of the Free Journals Network is very different: a quarter of its mathematics journals are in combinatorics, graph theory, or discrete mathematics (at least in part), with several more involving computational topics. I am pleased to see the Australasian Journal of Combinatorics in the list. On the other hand, there is only one generalist journal among the two dozen in the list. The absence of algebra journals is also noticeable: algebraic geometry, algebraic combinatorics, but no algebra, group theory, etc.

So what should we do?

As usual, the answer is not entirely straightforward. For an old codger like me, it matters not at all where my papers appear, and given the option, I will always choose an open access journal. But there are two complicating factors. First, most of my papers have younger co-authors, for whom the situation is different; and second, some are contributions to a special issue of a journal (maybe in honour or memory of a colleague), where I have no choice.

For young mathematicians, it is still true that getting papers into good journals matters significantly for their future careers. The UK Research Assessment Exercise, when I was involved in it, went to some lengths to ensure that assessors judged the quality of the papers rather than the journals containing them; I am not confident that this principle has been maintained. Certainly for questions of appointment, tenure and promotion, there are plenty of people who look at the impact factors but take little note of the content of the papers. Until this changes, the big switch to open access is not going to take place.

For people in mid-career, this is not so crucial (except for promotion, but let us just consider people who have reached the top of the tree). For these people, it takes a certain amount of courage to opt for, say, Discrete Analysis or Annales Henri Lebesgue rather than a traditional journal. But these are the people who could really make a difference.

And, as long as measures like impact factor are in use, the only way to raise the profile of open access journals is to publish in them papers which will get cited. To that extent, it is in our hands!

Posted in publishing | Tagged , , | 2 Comments


XKCD’s Friday comic concerned the On-line Encyclopedia of Integer Sequences. Take a look!

Posted in Uncategorized | Tagged , | Leave a comment