Does there exist Latin square critical sets for which deleting any entry results in arbitrarily many completions?

64 Views Asked by At

For those familiar with Latin squares terminology, I'll get straight to the point:

Q: For all $N \geq 2$, does there exists a critical set $C$ (for a Latin square of any finite order) such that deleting an entry from $C$ always results in $\geq N$ completions?

I'm guessing the answer is yes, but it doesn't strike me as obvious how to construct such critical sets. (Although, as always, I could be missing something.)


For those who aren't familiar (or who are rusty, or use different terminology)...

A partial Latin square is an $n \times n$ matrix with symbols from $\{1,2,\ldots,n\}$ and possibly some empty cells in which no symbol is repeated in a row or column.

A Latin square $L=(l_{ij})$ is said to be a completion of a partial Latin square $P=(p_{ij})$ if $l_{ij}=p_{ij}$ whenever cell $(i,j)$ in $P$ is nonempty.

A critical set is a partial Latin square $P$ that (a) admits a unique completion, and (b) admits $\geq 2$ completions after deleting any entry.

Here is an example of a critical set: $$\begin{array}{|cccc|} \hline 4 & 1 & \cdot & \cdot \\ \cdot & \cdot & \cdot & 2 \\ \cdot & 3 & \cdot & \cdot \\ \cdot & \cdot & 1 & \cdot \\ \hline \end{array}$$ which admits the unique completion $$\begin{array}{|cccc|} \hline 4 & 1 & 2 & 3 \\ 1 & 4 & 3 & 2 \\ 2 & 3 & 4 & 1 \\ 3 & 2 & 1 & 4 \\ \hline \end{array}.$$

If we delete the $1$ in the top row of the critical set, it admits the alternative completion $$\underbrace{\begin{array}{|cccc|} \hline 4 & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & 2 \\ \cdot & 3 & \cdot & \cdot \\ \cdot & \cdot & 1 & \cdot \\ \hline \end{array}}_{\text{exactly } 2 \text{ completions}} \xrightarrow{\text{also completes to}} \begin{array}{|cccc|} \hline 4 & \color{blue} 2 & 3 & 1 \\ 3 & 1 & 4 & 2 \\ 1 & 3 & 2 & 4 \\ 2 & 4 & 1 & 3 \\ \hline \end{array}.$$ It admits no other completions.

I would like, for arbitrary $N \geq 2$, to construct critical sets in which deleting any entry always results in $\geq N$ completions (if possible).