Enumerating extensions of mutually orthogonal Latin squares

Abstract

Two n×n Latin squares L1,L2 are said to be orthogonal if, for every ordered pair (x, y) of symbols, there are coordinates (i, j) such that L1(i,j)=x and L2(i,j)=y. A k-MOLS is a sequence of k pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention. Recent work of Keevash and Luria provides, for all fixed k, log-asymptotically tight bounds on the number of k-MOLS. To study the situation when k grows with n, we bound the number of ways a k-MOLS can be extended to a (k+1)-MOLS. These bounds are again tight for constant k, and allow us to deduce upper bounds on the total number of k-MOLS for all k. These bounds are close to tight even for k linear in n, and readily generalise to the broader class of gerechte designs, which include Sudoku squares.