Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For even ordered Latin squares, we can create squares in which every cell participates in a $2\times 2$ subsquare by using a simple circulant as for $n=6$ below:

 0 1 2 3 4 5
 1 2 3 4 5 0 
 2 3 4 5 0 1
 3 4 5 0 1 2
 4 5 0 1 2 3
 5 0 1 2 3 4

Or

0 1 2 3 4 5
1 0 3 2 5 4
2 3 4 5 0 1
3 2 5 4 1 0
4 5 0 1 2 3
5 4 1 0 3 2

(I think this is just a permutation of the one above, please tell me if I am correct or wrong, and how.)

In this square it appears that no cell participates in more than one subsquare. What is the relationship between this square and say, the following

 0 1 2 3 4 5
 1 0 3 4 5 2
 2 4 0 5 1 3
 3 5 1 2 0 4
 4 2 5 1 3 0
 5 3 4 0 2 1

that allows the latter to have cells participating in multiple subsquares and not the first? Does the latter's property or the former's lack of it thereof have something to do with the relation between the circulant's form an the even order, or just one or the other?

Also, do squares with some cells participating in multiple $2\times 2$ subsquares, and all cells participating in at least one $2\times 2$ subsquare exist for higher even order(I am aware than this is possible for $2^n$ as per $\mathbb{Z}/2^n$, but what about for $n\neq 2^n, n= 0mod2$) and so so, for what format?

Is it possible to have squares for at least certain even order with all cells participating in at least two $2 \times 2$ subsquares?

share|improve this question
    
In answer to the bracketed question L2=(1,5,3)L1, where L1 and L2 are the first and second Latin squares, and we permute the rows, columns and symbols by the permutation (1,5,3). How? I wrote some GAP code. –  Douglas S. Stones Aug 9 '12 at 6:44

1 Answer 1

up vote 1 down vote accepted

Given a Latin square L of order n in which every entry belongs to an intercalate (a 2x2 subsquare), we can construct a Latin square of order 2n by taking the direct product of L with a 2x2 Latin square. So, this is the direct product of a Latin square of order 2 with itself:

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Basically, after we take the direct product, an intercalate in L becomes a copy of the above Latin square. Combined with the result in the "Intercalates everywhere" paper (cited here), this gives the existence for even orders except 2,6,10,14. Order 2 is trivially impossible. Every entry in this Latin square belongs to 3 intercalates:

1 2 3 4 5 6
2 3 1 5 6 4
3 1 2 6 4 5
4 6 5 1 3 2
5 4 6 2 1 3
6 5 4 3 2 1

Leaving open the cases 10 and 14.

I doubt there will be a nice way to describe/determine when every entry in a Latin square belongs to 2 or more intercalates (or when there is just 1 intercalate intersecting every entry).

One more comment: from Cavenagh, Greenhill and Wanless paper, we know that with probability tending to 1 a random Latin square of order n has fewer than $\frac{9}{5} n^{5/2}$ intercalates. Thus, with probability tending to 1, a random Latin square of order n has an entry that intersects less than $n^{1/2+\varepsilon}$ intercalates for all $\varepsilon>0$.

N. J. Cavenagh, C. Greenhill, and I. M. Wanless, The cycle structure of two rows in a random Latin square, Random Structures Algorithms, 33 (2008), 286-309.

share|improve this answer
    
How was the order 6 square with each cell in three intercalates constructed? –  Xuan Huang Aug 9 '12 at 17:00
    
I flicked through the main classes of order 6 using Brendan McKay's data (there's only 12 squares). If I didn't find one in these 12, then, since subsquares are main class invariants, it would have been an exhaustive search. –  Douglas S. Stones Aug 9 '12 at 22:41

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.