Say we have a generalization of a Latin square, where the square is of size $n \times n$, $n = ab$ and each row and each column has $b$ occurrences of each of $[1, \dots, a]$. Is there always guaranteed to be a subsquare (a subset of a rows and a possibly different subset of a columns) which forms a proper $a \times a$ Latin square?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ One could generalize this question to balanced frequency rectangles. In other words, the rectangle is a $ar\times as$ matrix with entries in $\{1,\dots,a\}$ where each entry $i$ appears in each row $s$ times and each column $r$ times. But this generalized question is probably easier to answer in the negative. $\endgroup$– Joseph Van NameCommented Jul 4 at 14:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
For this problem, it is best to use computational software to construct balanced frequency squares and then to test whether these balanced frequency squares have Latin subsquares of the right shape or not.
It is not too hard to construct balanced frequency squares using computational software. For example, I started off with the matrix $(i+j\mod 5)_{i,j}$ which is a balanced frequency square, and then I repeatedly swapped pairs in this matrix and if the process of swapping takes the matrix too far away from being a balanced frequency square I undo the swapping process (I used this strategy since it was easy to code). This way, after each swap, I am not too far away from being a balanced frequency square. And when I wanted a balanced frequency square, I changed the update rule so that I only keep the swap if it makes the square more like a balanced frequency square.
There are other ways of obtaining random looking balanced frequency squares. For example, one can use Birkhoff's algorithm for decomposing a doubly stochastic matrix into a convex combination of permutation matrices to decompose the square matrix $(1)_{i,j}$ into a sum of permutation matrices. One can then turn this decomposition into permutation matrices into a Latin square or a balanced frequency square.
I did a brute force search for all 5 by 5 Latin submatrices of my $10$ by $10$ matrix, and the brute force search returned no Latin submatrices within the $252^2$ possibilities. Performing a brute force search was easier for me to code than doing a backtracking search.
-
1$\begingroup$ So you're saying you found a counterexample for the case $a=5$ and $b=2$? $\endgroup$– bofCommented Jul 5 at 1:15
$\begingroup$
$\endgroup$
2
Nice question! A comment about terminology. The object you are considering is a "balanced frequency square". Frequency squares generalise Latin squares in the sense that each row and column is a permutation of the same multiset of symbols. The term "balanced" means that each symbol occurs the same number of times.
I think these might be counterexamples:
112323
113232
232311
323211
231123
321132
or
11223344
12142433
21241433
24433112
32131244
34412321
43314212
43324121
-Ian
-
$\begingroup$ @Ian Wanless: your $F$ looks like a Latin square to me. This is the case $b=1$. Every $a\times a$ Latin square certainly contains an $a\times a$ Latin square, namely, itself. $\endgroup$ Commented Jul 4 at 14:47
-
$\begingroup$ Indeed, I goofed (rushed my reply). Have now edited the original post, with my next attempt at counterexamples. $\endgroup$ Commented Jul 9 at 13:01