Monday, 10 September 2007

co.combinatorics - Diagonally-cyclic Steiner Latin squares

A Steiner triple system is a decomposition of KnKn into K3K3, such as S=013,026,045,124,156,235,346S=013,026,045,124,156,235,346. Steiner triple systems give rise to a Steiner Latin squares, such as LL below.



[L=left(begin{matrix}
0 & 3 & 6 & 1 & bf{5} & 4 & 2 \\
3 & 1 & 4 & 0 & 2 & bf{6} & 5 \\
6 & 4 & 2 & 5 & 1 & 3 & bf{0} \\
bf{1} & 0 & 5 & 3 & 6 & 2 & 4 \\
5 & bf{2} & 1 & 6 & 4 & 0 & 3 \\
4 & 6 & bf{3} & 2 & 0 & 5 & 1 \\
2 & 5 & 0 & bf{4} & 3 & 1 & 6
end{matrix}right)]



We define L=(lij)L=(lij) by lii=ilii=i for all ii and lij=klij=k whenever ijkijk is a triangle in SS.



Note: Typically, Steiner Latin squares are viewed in an algebraic context and referred to as "Steiner quasigroups" -- Steiner quasigroups correspond to isomorphism classes of Steiner Latin squares, whereas for this question, I'm interested in the "labelled" case.



In some instances, such as LL above, the Latin square obtained is a diagonally-cyclic Latin square. That is, LL satisfies the identity l(i+1)(j+1)=lij+1pmodnl(i+1)(j+1)=lij+1pmodn, for all i,jinmathbbZni,jinmathbbZn, where the indices are taken modulo nn also. I've highlighted (in bold) an orbit of an entry of LL under this symmetry.




Which Steiner triple systems give rise to diagonally-cyclic Steiner Latin squares?




The above question was my original question, however, as Douglas Zare points out, these are precisely the Steiner triple systems that admit the automorphism (0,1,ldots,n1)(0,1,ldots,n1).



Proof: If LL is a Steiner Latin square derived from SS then (i,j,k)(i,j,k) is an entry in L if and only if it ijk is an element of S. For L to be diagonally-cyclic, if (i,j,k) is an entry of L then so is (i+1,j+1,k+1)pmodn. Therefore (i+1)(j+1)(k+1) is also an element of S. The converse is true by definition.



Since that was such an easy task, lets look at a (hopefully) more interesting question.



Let L=(lij) be a diagonally-cyclic Steiner Latin square. Let sigma be the permutation defined by sigma(j)=l0j (that is, the first row of L). Then sigma is an orthomorphism of mathbbZn. That is, sigma is a permutation of mathbbZn and the map defined by imapstosigma(i)ipmodn is also a permutation of mathbbZn.



In the above example sigma=(0)(13)(26)(45).




Which orthomorphisms of mathbbZn arise from diagonally-cyclic Steiner Latin squares?


No comments:

Post a Comment