12
$\begingroup$

Introduction

Cutler and Öhman (2006) attribute to Pebody (via personal communication) a construction of a set of $k:=\lfloor n/3 \rfloor+1$ partial Latin squares which are unavoidable (i.e., any Latin square of order $n$ has a non-empty intersection with at least one of these $k$ partial Latin squares). This claim was repeated by Andrén (2012). (The construction is described below.) However, neither of these papers provide a proof.

Question: How can we prove this set is unavoidable?

My attempts to prove this claim become somewhat complicated and I feel like I'm heading in the wrong direction (and I feel like I'm missing something more obvious).


Construction

In the $n=7$ case, we can collapse the $k$ partial Latin squares down to the following:

$$\begin{array}{|ccc|ccc|c|}\hline\{1,2,3\}&\{1,2,3\}&\{1,2,3\}&\emptyset&\emptyset&\emptyset&\emptyset\\\{1,2,3\}&\{1,2,3\}&\{1,2,3\}&\emptyset&\emptyset&\emptyset&\emptyset\\\{1,2,3\}&\{1,2,3\}&\{1,2,3\}&\emptyset&\emptyset&\emptyset&\emptyset\\\hline\emptyset&\emptyset&\emptyset&\{4,5,6\}&\{4,5,6\}&\{4,5,6\}&\emptyset\\\emptyset&\emptyset&\emptyset&\{4,5,6\}&\{4,5,6\}&\{4,5,6\}&\emptyset\\\emptyset&\emptyset&\emptyset&\{4,5,6\}&\{4,5,6\}&\{4,5,6\}&\emptyset\\\hline\emptyset&\emptyset&\emptyset&\emptyset&\emptyset&\emptyset&\{7,8,9\}\\\hline\end{array}$$

In general, the construction has the block structure: $$ \begin{array}{|c|c|c|} \hline A & \cdot & \cdot \\ \hline \cdot & B & \cdot \\ \hline \cdot & \cdot & C \\ \hline \end{array} $$ where

  • $A$ is a $k \times k$ block, with every cell containing $\{1,2,\ldots,k\}$.
  • $B$ is a $k \times k$ block, with every cell containing $\{k+1,k+2,\ldots,2k\}$.
  • $C$ is a $(n-2k) \times (n-2k)$ block, with every cell containing $\{2k+1,2k+2,\ldots,n\}$ (where we know $n-2k<k$).

Computation

I've verified the claim computationally for $n \leq 7$, and it holds in these cases. In the $n=8$ case, this Latin square (for example) comes quite close, with just one clash in the bottom-right corner: $$\begin{array}{|ccc|ccc|cc|} \hline 4 & 5 & 6 & 1 & 2 & 3 & 7 & 8 \\ 5 & 4 & 7 & 2 & 1 & 6 & 8 & 3 \\ 6 & 7 & 8 & 4 & 5 & 1 & 3 & 2 \\ \hline 1 & 2 & 4 & 3 & 7 & 8 & 5 & 6 \\ 2 & 1 & 5 & 8 & 3 & 7 & 6 & 4 \\ 3 & 6 & 1 & 7 & 8 & 2 & 4 & 5 \\ \hline 7 & 8 & 3 & 5 & 6 & 4 & 2 & 1 \\ 8 & 3 & 2 & 6 & 4 & 5 & 1 & \mathbf{7} \\ \hline \end{array}$$

UPDATE: We can also set up a system of linear equations, with variables describing the number of copies from any family of symbols in a given block. I found this system of equations has no solutions for $n \leq 100000$ or so, which verifies the claim in these cases.

$\endgroup$
3
  • 2
    $\begingroup$ I migrated this from Math.SE based on request of the OP. (It has been open for 1 month+ and received no answer.) $\endgroup$ Jun 25, 2013 at 11:56
  • $\begingroup$ Thanks Willie Wong! I've been wondering if MathOverflow would upgrade before the 60-day migration time limit was up. $\endgroup$ Jun 25, 2013 at 12:03
  • 2
    $\begingroup$ Lucky you! You are the proud owner of the first question migrated either way between the two sites. $\endgroup$ Jun 25, 2013 at 12:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.