36 Completing Latin squares

Lemma 36.1

Any \((r \times n)\)-Latin rectangle, \(r {\lt} n\), can be extended to an \(((r+1) \times n)\)-Latin rectangle and hence can be completed to a Latin square.

Proof ▶

We apply Hall’s theorem 30.4 (see Chapter 30). Let \(A_j\) be the set of numbers that do not appear in column \(j\). An admissible \((r+1)\)-st row corresponds then precisely to a system of distinct representatives for the collection \(A_1, \dots , A_n\). To prove the lemma we therefore have to verify Hall’s condition (H). Every set \(A_j\) has size \(n - r\), and every element is in precisely \(n - r\) sets \(A_j\) (since it appears \(r\) times in the rectangle). Any \(m\) of the sets \(A_j\) contain together \(m(n - r)\) elements and therefore at least \(m\) different ones, which is just condition (H).

Lemma 36.2

Let \(P\) be a partial Latin square of order \(n\) with at most \(n - 1\) cells filled and at most \(\frac{n}{2}\) distinct elements, then \(P\) can be completed to a Latin square of order \(n\).

Proof ▶

TODO

Theorem 36.3 Smetaniuk’s theorem

Any partial Latin square of order \(n\) with at most \(n - 1\) filled cells can be completed to a Latin square of the same order.

Proof ▶