Last week we celebrated the 29th British Combinatorial Conference in Lancaster, face to face. (As a side observation, this was by far the largest social gathering I have been at since the start of the pandemic; I found it both unfamiliar and exhausting, through no fault of the organisers.)
The BCC has made a couple of judgment calls recently which have fortunately worked out well. Last year, Max Gadouleau and his team decided in advance to run the conference entirely on-line, and to make it the best on-line conference ever. This year, Tony Nixon and his team insisted from the start that it would be a live meeting. Both these proved to be right.
The meeting for me was memorable, and nostalgic. At the business meeting, I stood down as chair of the committee after thirty years. This was in large part because looking after Rosemary on top of everything else has made the last year or two difficult and exhausting, and I don’t think I have done the job very well. But I am very fortunate to be able to hand over the chair to Julia Wolf, with Robert Johnson as secretary and Simon Blackburn as treasurer, and with the committee in a good financial position (due, paradoxically, to the pandemic: we were unable to spend money on our usual support of meetings). So all the best to them in the future.
Rather than try to give a summary, I will concentrate on one topic which, for me, was the highlight: several talks around the Hall–Paige conjecture.
To begin, here is a little background. Let G be a finite group. The Cayley table of G is the square array with rows and columns indexed by G, with the entry in row x and column y being the product xy. It is a Latin square: that is, every element of G occurs once in each row and once in each column.
A transversal of a Latin square L of order n is a set of n cells, one in each row, one in each column, and one containing each symbol. A partition of the cells into transversals is called an orthogonal mate of L, since if we choose n new symbols and associate one with each part of the partition, putting it in the cells in that part, we obtain a Latin square orthogonal to L.
A complete mapping on G is a bijection φ from G to itself with the property that the map ψ defined by ψ(x) = xφ(x) is also a bijection.
The commutator subgroup (or derived group) of G is the subgroup generated by all commutators x−1y−1xy, for all x,y in G. It is the set of elements mapped to the identity in any homomorphism from G to an abelian group.
For a prime p, a Sylow p-subgroup of G is a subgroup whose order is a power of p and whose index is coprime to p. By Sylow’s Theorem, Sylow subgroups always exist, and any two are conjugate, and hence isomorphic.
With that background, I can state the Hall–Paige conjecture. It states that the following five conditions for a finite group G are all equivalent:
- The Cayley table of G has a transversal.
- The Cayley table of G has an orthogonal mate.
- G has a complete mapping.
- The product of the elements of G (in any order) belongs to the commutator subgroup.
- The Sylow 2-subgroups of G are either trivial (this means that G has odd order) or not cyclic.
The equivalence of the first three conditions is straightforward. I will illustrate with one of the implications. Suppose that G has a complete mapping φ. Then the set of cells in row x and column φ(x) for all x is a transversal, since the column numbers and the symbols ψ(x) each comprise the set G with no repetitions.
The equivalence of the fourth and fifth conditions is almost as simple, if you know Burnside’s Transfer Theorem, a result in group theory more than a century old.
Hall and Paige proved that any of the first three conditions implies either of the last two. The conjecture, thus, asserts that the reverse implication also holds.
As a side note, I observed that the combinatorialists in Lancaster who spoke about this only used the first and fourth of the above conditions. This was a little strange, since firstly the existence of an orthogonal mate is superficially stronger than that of a transversal, and in more general situations these conditions are no longer equivalent, so that establishing the second would be a bigger result; and secondly, the fifth condition seems so obviously easier to work with than the fourth.
Anyway, Hall and Paige proved some cases of the reverse implication. Then no substantial progress happened until 2009. In that year,
- Stuart Wilcox reduced the problem to the case where the group G is a non-abelian simple group, and settled it for the groups of Lie type except for the Tits group (the alternating groups had already been done by Hall and Paige);
- Tony Evans did the Tits group and 25 of the sporadic groups;
- John Bray knocked off the final sporadic group, the fourth Janko group.
The work of Wilcox and Evans was published in the Journal of Algebra that year. Bray’s work languished as folklore until 2020. I needed the result to prove that groups of simple diagonal type with more than two factors in their socle are non-synchronizing, so I persuaded John to write it up and include it in the paper I was writing.
In the last two years, there have been two dramatic developments in the story: two new “proofs” of the conjecture. (The quotes are because, if my understanding of the proofs is correct, each proves the result only for “sufficiently large” groups, and it may be that “sufficiently large” is too large for us to finish the proof by examining “small” cases.) Each proof gives a very substantial strengthening of the conjecture.
Last year, Sean Eberhard, Freddie Manners and Rudi Mrazović posted on the arXiv a paper in which they used analytic number theory to obtain an estimate for the number of transversals of the Cayley table of a group. Their estimate shows that the number is positive for sufficiently large groups.
This year, Alp Müyesser and Alexey Pokrovskiy posted on the arXiv a proof of a generalization of the Hall–Paige conjecture for large groups (concerning the existence of complete mappings on large subsets of the group), using methods of probabilistic combinatorics.
Now three of these five spoke at the BCC. Alexey gave a plenary talk on “Rainbow subgraphs and their applications”. His paper in the conference book covered this topic in generality, but in his talk he focused on the Hall–Paige application, and explained in detail what goes on in that proof.
Alp Müyesser talked about how he and Pokrovskiy have used the probabilistic methods to solve a problem of Evans for sufficiently large groups. A group is called harmonious if its elements can be arranged in a cyclic sequence g0, g1, …, gn−1 such that products of consecutive pairs of terms are all distinct, and so also make up the whole group without repetition. It is easy to see that the Hall–Paige conditions are necessary. But there is another obstruction: elementary abelian 2-groups. (In such a group, the identity is never the product of two distinct elements). They have proved that, with these exceptions, and if the group is sufficiently large, then such an arrangement can be found.
Freddie Manners spoke in the minisymposium on additive combinatorics. Kwan has proved that almost all Latin squares have transversals; Manners was able to adapt the methods used for Hall–Paige, together with a notion of quasirandomness for Latin squares based on one by Tim Gowers for groups, to give a new proof and to count the number of transversals asymptotically, extending his earlier work with Eberhard and Mrazović.
A related highlight is one I was forced to miss, since I was speaking in a different minisymposium at the time. Richard Montgomery, in the extremel combinatorics symposium, talked about his proof of the Ryser and Brualdi conjectures, stating that a Latin square of order n always has a partial transversal of size n−1, and indeed has a transversal if n is odd. (Stein’s name is also attached to these conjectures, but I am not sure of exactly who conjectured what.)
Some final observations and problems.
- The relationship between transversals and orthogonal mates for Cayley tables of groups fails for general Latin squares, but finding estimates for the number of orthogonal mates under suitable conditions may be worth a look. Additionally, it should allow the number-theoretic proof to be parlayed into an estimate for the number of orthogonal mates of a Cayley table.
- Since I have read in detail at least one part of the group-theoretic proof of Hall–Paige, I have been left with the feeling that transversals are very easy to find and prolific. Is it possible to extract estimates from the group-theoretic proof?
- Gowers’ notion of quasirandomness for groups involves the degrees of the non-principal irreducible characters of the group being large. Now there is a character theory of quasigroups (algebraic structures whose Cayley table is an arbitrary Latin square) developed mainly by Jonathan Smith. Now for almost all quasigroups, the character degrees are 1 and n−1. This suggests a possible different approach to quasirandomness for Latin squares.