Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

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  
I migrated this from Math.SE based on request of the OP. (It has been open for 1 month+ and received no answer.) –  Willie Wong Jun 25 '13 at 11:56
    
Thanks Willie Wong! I've been wondering if MathOverflow would upgrade before the 60-day migration time limit was up. –  Douglas S. Stones Jun 25 '13 at 12:03
2  
Lucky you! You are the proud owner of the first question migrated either way between the two sites. –  Willie Wong Jun 25 '13 at 12:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.