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

Donovan D, Grannell M and Yazici ES

arXiv
https://doi.org/10.48550/arXiv.2602.09908

Abstract

It is shown that if F denotes the number of filled cells in a superimposed pair of maximal orthogonal partial Latin squares of order n, then F n²/3. This resolves a conjecture raised in an earlier paper by the current authors. It is also shown that, for n≥21, the least possible number of filled cells in a pair of maximal orthogonal partial Latin squares is [n²/3], and that the structure that achieves this bound is unique up to permutations of rows, columns and entries.

TOP