BCC29 at Lancaster

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.

About Peter Cameron

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

5 Responses to BCC29 at Lancaster

  1. Sean Eberhard says:

    Hi Peter,

    I was also happy to hear about the surge of interest in transversals / complete mappings / orthomorphisms. It seems that a couple different toolsets are reaching maturity at the same time, enabling progress on these old problems.

    Some corrections: As far as I understand, Montgomery proved Brualdi’s conjecture but not Ryser’s (full transversal in the odd n case is still open). Amazing progress, but there is at least one big problem still unsolved. Also, Manners’s work is again joint with Rudi and me.

    Regarding your last question, actually we (Freddie, Rudi, and I) know the answer. The problem is that latin squares are much “floppier” than groups, so it is possible that a latin square be maximally quasirandom in the strict character theory sense (character degrees are 1 and sqrt(n-1)), but still behave very like some abelian group. Our favorite example is “PG(d-1, 2)”, which you can define as the Cayley table of F_2^d with the row and column indexed by 0 deleted and x+x redefined to be x for all x. If you compute the character table in the Jonathan Smith sense then you get the same as for a random square, just two characters, but this square behaves very similarly to F_2^d from the point of view of counting transversals, since a constant fraction of the transversals don’t even intersect the main diagonal. There are many similar examples based on perturbing some abelian group. So, character theory in the strict quasigroup sense is inadequate. What we need is some more robust tool which can detect “approximate abelianization”, and it seems the different groups have different ways of trying to make sense of this.

  2. I have thought for some time that, as long as you don’t choose too much of the Latin square, it behaves “randomly” subject to the obvious constraints. Here is a sample problem. The first two rows of a Latin square are permutations such that the second is a derangement of the first. Now, for example, if n=4, then the 4-cycle has just two completions to a full Latin square but the double transposition has four. The number of completions fairly obviously depends only on the conjugacy class of the derangement. I conjecture that the ratio of the maximum and minumum number of completions tends extremely rapidly to 1 as n grows. The best results so far are nowhere near this — the convergence to 1 is not known, for example. This might be a test of the available techniques.

  3. Robert says:

    Thanks for the write-up Peter. There’s another view on the conference here on the Queen Mary Combinatorics Group blog:

    https://www.qmul.ac.uk/maths/research/combinatorics-group/combinatorics-news-and-blog/items/asier-and-belinda-at-the-british-combinatorial-conference.html

    Your guitar even gets a mention!

    • Thanks Robert.
      The concert was completely informal, but someone said it was the best BCC concert ever! We couldn’t not have one after what the Vice-Chancellor said at the opening ceremony,
      I enjoyed the comments. To me the best thing was being back in person at the conference which is in a sense my home and seeing so many old friends.
      Incidentally I happened to be looking at the Erdős Number Project website; Noga Alon is the Erdős coauthor with the greatest number of coauthors (well over 400 as of two years ago).
      I am very much looking forward to BCC30!

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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.