Some challenges on Latin squares

Following the combinatorial design challenges, here are three questions on Latin squares.

A Latin square is an n×n matrix with entries from an alphabet of size n (typically the integers from 1 to n) such that each letter appears once in each row and once in each column. A transversal is a set of n cells, one in each row, one in each column, and one containing each letter. An orthogonal mate of a Latin square is a partition of the cells into transversals. (If we assign a new letter from a different alphabet to each part, we obtain a second latin square with the property that any pair of letters, one from each alphabet, occur at a unique position.)

Problem 1 (Ryser’s and Brualdi’s conjectures) Ryser conjectured that any Latin square of odd order has a transversal; Brualdi conjectured that any Latin square of order n has a partial transversal of size n−1. These are still open, though bounds on the defect of a partial transversal have recently been improved by Peter Keevash, Alexey Pokrovskiy, Benny Sudakov and Liana Yepremyan.

Problem 2 Find the limiting proportions (assuming they exist) of Latin squares which have (a) a transversal and (b) an orthogonal mate. Find good asymptotics for the rate at which these limits are approached.

My guess for the limits would be 1 and 0 respectively.

Problem 3: a derangement problem. The permutation of columns mapping the first row of a Latin square to the second is a derangement (that is, has no fixed points): this is immediate from the definition. Given a derangement, we can take the first two rows of a potential Latin square to be the identity permutation and this derangement, and ask in how many ways it can be completed to a Latin square. My conjecture is that is surprisingly close to constant, independent of the chosen derangement. In other words, the ratio of the maximum to the minimum number of completions of a derangement tends very rapidly to 1 as n increases. A solution to the problem should include a good estimate for the rate of convergence!

For investigating this, note that conjugate derangements have the same number of completions. So we could ask whether the number of Latin squares having a derangement with given cycle structure is very nearly proportional to the number of derangements with this cycle structure. For n = 4, the double transpositions have twice as many completions as the 4-cycles; so although there are twice as many 4-cycles as double transpositions, the total numbers of squares are equal for the two types (288 each). Even for n = 7, the answer is very different.

I do not know the precise numbers. Latin squares of order 7 where determined in a paper by H. W. Norton in 1939; although this may not be reliable I thought it would give a good indication. But the paper was published in the Annals of Eugenics, and because Latin squares of order 7 are such a potentially racist and offensive topic, the publishers make it difficult to get hold of. When I did, I found that the pages of tables were rotated and it would have been a terrible job to extract the information I wanted.

So instead I turned to the Markov chain, devised by Jacobson and Matthews, for choosing a random Latin square. The limit is the uniform distribution on Latin squares, but unfortunately it is not known how long you should run the chain until it is close to the limit. So I did 100000 trials, with 100 steps of the chain between each sample. These results should maybe taken with a grain of salt…

There are four cycle structures of derangements: 7, 5.2, 4.3, and 3.2.2. The proportions of each, to four places of decimals, are 0.3883, 0.2718, 0.2265 and 0.1132. In my experiment the numbers I obtained were 38610, 27264, 22854 and 11272. Pretty close, and this is only three more than a value for which the ratio of max to min number of extensions is 2.

Nicholas Cavenagh, Catherine Greenhill and Ian Wanless have results on this which, though impressive, are some way from what I believe to be the case.