5
$\begingroup$

There exists a Latin square of order $8$ which can be partitioned into $2 \times 4$ subrectangles: $$ \begin{bmatrix} \color{red} 1 & \color{red} 2 & \color{red} 3 & \color{red} 4 & \color{purple} 5 & \color{purple} 6 & \color{purple} 7 & \color{purple} 8 \\ \color{red} 2 & \color{red} 3 & \color{red} 4 & \color{red} 1 & \color{purple} 6 & \color{purple} 7 & \color{purple} 8 & \color{purple} 5 \\ 7 & 8 & \color{blue} 1 & \color{blue} 2 & \color{blue} 3 & \color{blue} 4 & 5 & 6 \\ 8 & 5 & \color{blue} 2 & \color{blue} 3 & \color{blue} 4 & \color{blue} 1 & 6 & 7 \\ \color{pink} 5 & \color{pink} 6 & \color{pink} 7 & \color{pink} 8 & \color{green} 1 & \color{green} 2 & \color{green} 3 & \color{green} 4 \\ \color{pink} 6 & \color{pink} 7 & \color{pink} 8 & \color{pink} 5 & \color{green} 2 & \color{green} 3 & \color{green} 4 & \color{green} 1 \\ \color{orange} 3 & \color{orange} 4 & \color{brown} 5 & \color{brown} 6 & \color{brown} 7 & \color{brown} 8 & \color{orange} 1 & \color{orange} 2 \\ \color{orange} 4 & \color{orange} 1 & \color{brown} 6 & \color{brown} 7 & \color{brown} 8 & \color{brown} 5 & \color{orange} 2 & \color{orange} 3 \\ \end{bmatrix} $$ If we take the row-symbol parastrophe of this Latin square (i.e., replace each entry $(i,j,l_{ij})$ with $(l_{ij},j,i)$), then the entry colors define a decomposition of $K_{8,8}$ into $2$-regular spanning subgraphs of $K_{4,4}$. I would like to generalize this.

Question: For which divisors $a$ and $b$ of $n$ does there exist a Latin square of order $n$ that can be partitioned into $a \times b$ subrectangles?

(Note: We assume $a \leq b$. Subrectangles must have $b$ symbols. We don't assume that the boundaries of the subrectangles align.)

Observations:

  • It's trivially possible when

    • $a$ divides $b$ (construct a Latin square with blocks that are $b \times b$ subsquares)
    • $a=1$ or $b=n$.
  • The first non-trivial case is when $a=2$, $b=3$, and $n=6$. If my code is correct, then it is impossible (by exhaustive search). (I'm tempted to think this is just because the parameters are too small.) The best possible is $4$ subrectangles, which is straightforward to construct.

  • My code found a random Latin square which gave an $a=2$, $b=5$, and $n=10$ example: $$ \begin{bmatrix} \color{red} 7 & \color{red} 1 & 9 & 5 & \color{red} {10} & 4 & 8 & \color{red} 2 & 6 & \color{red} 3 \\ \color{red} 3 & \color{red} {10} & 5 & 8 & \color{red} 2 & 6 & 4 & \color{red} 1 & 9 & \color{red} 7 \\ \hline \color{blue} 9 & \color{blue} 6 & 4 & 7 & 1 & \color{blue} 2 & \color{blue} {10} & \color{blue} 3 & 5 & 8 \\ \color{blue} 6 & \color{blue} 3 & 7 & 1 & 5 & \color{blue} 9 & \color{blue} 2 & \color{blue} {10} & 8 & 4 \\ \hline \color{pink} 4 & 5 & 1 & \color{pink} 2 & \color{pink} 8 & 3 & 9 & \color{pink} 7 & \color{pink} {10} & 6 \\ \color{pink} 2 & 9 & 6 & \color{pink} {10} & \color{pink} 4 & 1 & 3 & \color{pink} 8 & \color{pink} 7 & 5 \\ \hline \color{purple} 1 & 2 & \color{purple} 8 & 3 & 7 & \color{purple} {10} & 6 & \color{purple} 5 & 4 & \color{purple} 9 \\ \color{purple} 8 & 4 & \color{purple} {10} & 6 & 3 & \color{purple} 5 & 7 & \color{purple} 9 & 2 & \color{purple} 1 \\ \hline \color{brown} 5 & 8 & \color{brown} 2 & 9 & 6 & 7 & \color{brown} 1 & 4 & \color{brown} 3 & \color{brown} {10} \\ \color{brown} {10} & 7 & \color{brown} 3 & 4 & 9 & 8 & \color{brown} 5 & 6 & \color{brown} 1 & \color{brown} 2 \\ \end{bmatrix} $$

$\endgroup$
2
  • 1
    $\begingroup$ Hi Rebecca. Do you have an example where it isn't possible? $\endgroup$ Jan 23 '16 at 13:35
  • $\begingroup$ I do now. I edited in some results of a computer search. $\endgroup$ Jan 24 '16 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.