Monday, 10 September 2007

co.combinatorics - Diagonally-cyclic Steiner Latin squares

A Steiner triple system is a decomposition of KnKn into K3, such as S=013,026,045,124,156,235,346. Steiner triple systems give rise to a Steiner Latin squares, such as L 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) by lii=i for all i and lij=k whenever ijk is a triangle in S.



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 L above, the Latin square obtained is a diagonally-cyclic Latin square. That is, L satisfies the identity l(i+1)(j+1)=lij+1pmodn, for all i,jinmathbbZn, where the indices are taken modulo n also. I've highlighted (in bold) an orbit of an entry of L 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).



Proof: If L is a Steiner Latin square derived from S then (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