no. 13 · Wednesday 11 November 2026
On the minimum number of entries in a set of maximal mutually orthogonal partial Latin squares
Abstract
In superimposed form, a set of $k\ge2$ mutually orthogonal partial Latin squares of order $n$ is said to be maximal if no additional $k$-tuple may be inserted into any empty cell without violating orthogonality or the Latin property. For $k=2$ and $n\ge 21$ it is shown that the minimum number of filled cells in such a square is $\lceil n^2/3 \rceil$. Likewise for $k=3$ and $n\ge 44$ the minimum number of filled cells is $\lceil n^2/4 \rceil$ or $\lceil n^2/4 \rceil+1$, depending on the residue of $n$ modulo 4. In each case it is shown that the extremal systems are essentially those produced by a construction presented in the paper. A similar result is obtained for all $k\ge4$ for minimal systems that have a certain balance property, and it is conjectured that for sufficiently large $n$, even without this balance property, the extremal systems always correspond to those produced by this construction.
- comments
- 25 pages, 4 figures
- fields
- Combinatorics