Enumerating extensions of mutually orthogonal Latin squares

Abstract

Two $n\times n$ Latin squares $L_1,L_2$ are said to be orthogonal if, for every ordered pair $(x,y)$ of symbols, there are coordinates $(i,j)$ such that $L_1(i,j)=x$ and $L_2(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 generalize to the broader class of gerechte designs, which include Sudoku squares.

18 pages