Paperlane

no. 13 · Wednesday 11 November 2026

On the minimum number of entries in a set of maximal mutually orthogonal partial Latin squares

Diane M. Donovan, Mike J. Grannell and Emine Sule Yazici

math.CO · 25 pp

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
pdf ↗ page arXiv:2611.13961 ↗