Partial latin square with $\le n-1$ filled cells

Question

How do we show that is $P$ if a $n\times n$ Latin square with $\le n-1$ filled cells, then $P$ can be completed to a proper Latin square?

Here is the definition of a Latin square.

(WHAT I HAVE DONE SO FAR: I have worked examples for $n=2,3,4$ but am unable to find a pattern that is rigorous, or any pattern for that pattern. A step-by step proof would be appreciated- or if you could tell me what facets here are of paramount importance when it comes to my observation.)

Could someone explain the inductive step in the link provided by Gerry Myerson in Theorem 5? I don't get it.

Answer 1

This is discussed in Chapter 32 of Proofs From The Book. The authors write, "Bohdan Smetaniuk's proof from 1981 ... is a beautiful example of just how subtle an induction proof may be...."

This paper also gives Smetaniuk's proof.

Answer 2

You have a partial Latin square $P$ of order $m+1$ with exactly $m$ filled cells, and you’re assuming that the number of distinct symbols in $P$ is greater than $\frac{m+1}2$. If each of these symbols occurred in more than one cell, they would fill more than $m+1$ cells altogether, contradicting the assumption that $P$ has just $m$ filled cells. Thus, some symbol $s$ appears in exactly one cell of $P$. Here’s an example with $m=4$; I’ve marked the back diagonal in red.

$$\begin{array}{|c|c|c|c|c|} \hline &&&5&\color{red}\cdot\\ \hline &&&\color{red}\cdot&\\ \hline &&\color{red}\cdot&3&\\ \hline &\color{red}\cdot&&&\\ \hline \color{red}5&2&&&\\ \hline \end{array}$$

At this point we use the second of the ‘key ideas’ identified at the top of p. 254 to conclude that the rows and columns of $P$ can be permuted to yield a new partial Latin square $Q$ of order $m+1$ with exactly $m$ filled cells in such a way that $s$ now lies on the back diagonal of $Q$, and the other filled cells of $Q$ lie above the back diagonal. Then we relabel the symbols so that $s$ becomes $m+1$. In my example I change the order of the rows from $12345$ to $13524$, bringing the lone $3$ to the back diagonal, relabel the $3$ as $5$, the $5$’s as $2$’s, and the $2$ as $3$ to get this:

$$\begin{array}{|c|c|c|c|c|} \hline &&&2&\color{red}\cdot\\ \hline &&&\color{red}5&\\ \hline 2&3&\color{red}\cdot&&\\ \hline &\color{red}\cdot&&&\\ \hline \color{red}\cdot&&&&\\ \hline \end{array}$$

The next step is to delete the $m+1$ on the back diagonal and the last row and last column. Note that the only cells in the last row and column that could possibly be filled at this point are the ones in the upper right and lower left corners, on the back diagonal, so the only symbol deleted in this step is the $m+1$ on the back diagonal. In the example above we’d be left with the following partial Latin square of order $4$:

$$\begin{array}{|c|c|c|c|c|} \hline &&&\color{blue}2\\ \hline &&&\color{red}\cdot\\ \hline \color{blue}2&\color{blue}3&\color{red}\cdot&\\ \hline &\color{red}\cdot&&\\ \hline \end{array}$$

The red dots mark the cells that were on the back diagonal of $Q$; the one just below the $2$ in the upper right corner is where the $\color{red}5$ was in $Q$. The blue cells are the entries retained from $Q$.

We now have a partial Latin square of order $m$ with $m-1$ filled cells; by the induction hypothesis, it can be completed to a Latin square $L$. In my example $L$ might be this Latin square:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&3&\color{blue}2\\ \hline 3&2&4&1\\ \hline \color{blue}2&\color{blue}3&1&4\\ \hline 4&1&2&3\\ \hline \end{array}$$

Now construct the partial Latin square $P(L)$ of order $m+1$ as described at the bottom of p. 253 and top of p. 254: erase every symbol below the back diagonal of $L$ and add an empty last column and last row to get a partial Latin square of order $m+1$, and fill the back diagonal of this partial Latin square with the symbol $m+1$. In my example this produces the following partial Latin square $P(L)$, where the blue entries are those retained (or, in the case of the $5$, reintroduced) from $Q$:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&3&\color{blue}2&5\\ \hline 3&2&4&\color{blue}5\\ \hline \color{blue}2&\color{blue}3&5&\\ \hline 4&5&&\\ \hline 5\\ \hline \end{array}$$

Next we apply the other of the two ‘key ideas’ mentioned at the top of the page to conclude that $P(L)$ can be completed.

One possible completion is this:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&3&\color{blue}2&5\\ \hline 3&2&4&\color{blue}5&1\\ \hline \color{blue}2&\color{blue}3&5&1&4\\ \hline 4&5&1&3&2\\ \hline 5&1&2&4&3\\ \hline \end{array}$$

The blue cells, as before, show the cells retained from $Q$.

The final step is to reverse the relabelling and rearrangement of the rows and columns that took us from the original $P$ to $Q$. I changed $3$ to $5$, $5$ to $2$, and $2$ to $3$, so I must now change $3$ to $2$, $2$ to $5$, and $5$ to $3$:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&2&\color{blue}5&3\\ \hline 2&5&4&\color{blue}3&1\\ \hline \color{blue}5&\color{blue}2&3&1&4\\ \hline 4&3&1&2&5\\ \hline 3&1&5&4&2\\ \hline \end{array}$$

I also have to reverse the permutation of the rows; this, finally, yields this Latin square:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&2&\color{blue}5&3\\ \hline 4&3&1&2&5\\ \hline 2&5&4&\color{blue}3&1\\ \hline 3&1&5&4&2\\ \hline \color{blue}5&\color{blue}2&3&1&4\\ \hline \end{array}$$

This is clearly a completion of the original partial Latin square $P$.

Does this help, or were you more worried about the proofs of the two ‘key ideas’, for which the authors refer you to a paper by Lindner?