Can we show that $P$ is a partial latin square that is $n \times n$ where $n$ is even, where the upper quadrant $\frac{n}{2} \times \frac{n}{2}$ is filled and the rest is blank, then $P$ can be completed to a Latin square?
Partial Latin squares of even order
3
$\begingroup$
combinatorics
latin-square
1 Answers
5
Yes it can always be completed. This is a consequence of an important result in design theory/combinatorics, proved by Ryser in:
Ryser, H. J., A combinatorial theorem with an application to latin rectangles. Proc. Amer. Math. Soc. 2, (1951). 550–552.
More generally: an $r \times s$ matrix containing symbols from $\{1,2,\ldots,n\}$ can be completed to an $n \times n$ Latin square if and only if the number of copies of the symbol $i$ is at least $r+s-n$, for all $i \in \{1,2,\ldots,n\}$.
In the specific case of $r=s=n/2$, Ryser's condition is trivially satisfied.