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$

migrated from math.stackexchange.com Jun 25 '13 at 11:55

This question came from our site for people studying math at any level and professionals in related fields.

  • 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$ – Willie Wong Jun 25 '13 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$ – Douglas S. Stones Jun 25 '13 at 12:03
  • 2
    $\begingroup$ Lucky you! You are the proud owner of the first question migrated either way between the two sites. $\endgroup$ – Willie Wong Jun 25 '13 at 12:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.