7
$\begingroup$

For a latin square (LS) of order $n$, we will define a cut (or maybe general transversal, I don't know whether there is an entrenched name for this) as a collection of $n$ cells such that no two share the same row or column.
Call the number of different symbols of such a cut its rank. Thus a $n$-cut, i.e. a cut of rank $n$, is the same thing as a transversal, and a $(n-1)$-cut yields two partial transversals of length $n-1$.
Define the signature of a LS as the vector $(c_1,\dots,c_n)$ of the numbers of its $k$-cuts for $k=1,\dots,n$.

I am wondering how much the signature can tell us about a latin square.
So I have taken some of the lists given here.

For $n=4$, the cyclic square $\mathbb Z_4$ (i. e. the addition table of $\mathbb Z/4\mathbb Z$) has signature $(4,4, 16, 0)$ and the one of the Klein four-group has $(4,12, 0, 8)$.

For $n=5$, we have $(5,0, 100, 0, 15)$ for $\mathbb Z_5$ and $(5,8, 72, 32, 3)$ for the only other (isotopy class of) LS.

For $n=6$, the 22 isotopy classes of latin squares have 15 different signatures. The complete list follows: \begin{array}{cccccccc} entries&c_1&c_2&c_3&c_4&c_5&c_6\\ 012345153024245130324501401253530412&6&12& 270& 270& 162& 0\\ 012345103254235410324501451023540132&6&30& 216& 324& 144& 0\\ 012345150432245013304521423150531204&6&30& 216& 324& 144& 0\\ 012345150432245013304521431250523104&6&30& 216& 324& 144& 0\\ 012345153420231504340152425013504231&6&30& 216& 324& 144& 0\\ 012345120534234150305412451203543021&6&30& 204& 348& 132& 0\\ 012345130524254130345012403251521403&6&30& 204& 348& 132& 0\\ 012345143520205413321054450231534102&6&38& 188& 356& 132& 0\\ 012345104523231054325410450132543201&6&42& 172& 376& 124& 0\\ 012345104523230154325401451032543210&6&\color{blue}{66}&\color{blue} {108}& 432& 108& 0\\ 012345123450254013305124431502540231&6&12& 254& 310& 130& 8\\ 012345134520245031351204403152520413&6&14& 248& 316& 128& 8\\ 012345143502231450350124425031504213&6&14& 248& 316& 128& 8\\ 012345135024201453324510450132543201&6&14& 244& 324& 124& 8\\ 012345153204231450340521425013504132&6&14& 244& 324& 124& 8\\ 012345105234253410324501431052540123&6&18& 240& 320& 128& 8\\ 012345104253235014351420420531543102&6&26& 220& 336& 124& 8\\ 012345143250254031305124430512521403&6&26& 212& 352& 116& 8\\ 012345104532235104321450453021540213&6&30& 180& 420& 60& 24\\ 012345134052201534325401450123543210&6&30& 180& 420& 60& 24\\ 012345105234234150340512453021521403&6&50& 140& 440& 60& 24\\ 012345103254234501325410451032540123&6&30& 184& 420& 48& 32\\ \end{array} Some remarks about this list:

  • The first row corresponds to the only 6x6 square that has no intercalates (=2x2 Latin subsquares). Note that all its values are extremal ($c_2,c_4,c_6$ are minimal, $c_3,c_5$ are maximal).
  • The cyclic square $\mathbb Z_6$ is one of the rows 2-5, thus its signature has nothing distinctive. Even though $6$ is not a prime, this is rather surprising!
  • For the square in row 10, $c_2$ is maximal, $c_3$ minimal (both in blue) and $c_4$ next-to-maximal. (Note that the maximal $c_4=440$ occurs in the penultimate row and goes along with the next-to-maximal $c_2=50$, thus a sort of dual LS to that.)
  • For the LS corresponding to the very last row, $c_5$ is minimal and $c_6$ maximal, i.e. it has more transversals than any other one.

Do those "extremal" squares (i.e. rows 1, 10, 21, 22) exhibit other features making them special among all 6x6 squares?

For $n=7$, the following list shows for each column, sorted independently, the three smallest and the three biggest values occurring among the 564 isotropy classes. ($c_1\equiv7$ omitted)

\begin{array}{cccccccc} &c_2&c_3&c_4&c_5&c_6&c_7\\ smallest&0&399&1372&1795&0&3\\ &0&511&1804&1795&336&7\\ &6&527&1804&1797&352&7\\ &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ &78&737&2108&2037&516&55\\ &86&774&2108&2073&516&63\\ biggest&126&882&2156&2646&528&133\\ \end{array}

  • As can be expected, $\mathbb Z_7$ is extremal with its signature $(7, 0, 882, 1372, 2646, 0, 133)$: for this LS, $c_2,c_4,c_6$ are minimal, $c_3,c_5,c_7$ are maximal.
  • Almost "dual" to that (in a certain sense) is the LS given by the entries 0123456105263423615403240165463502154162036504312. It has signature $(7, 126, 399, 2156, 1953, 336, 63)$, and here $c_2$ is maximal, $c_3$ is minimal, $c_4$ is maximal, $c_6$ is next-to-minimal and $c_7$ is next-to-maximal. Moreover, this one and $\mathbb Z_7$ are the only ones of all the 564 isotopy classes where $c_k\equiv 0\pmod 7\ \forall k$.

This is a lot at once. I am sure that this LS has some unique properties among all 7x7 squares. But which ones?
In terms of its automorphism group? Or its number of orthogonal mates? orthogonal subsquares? What might be other relevant properties here?

EDIT: This one is in fact isomorphic to the cyclic Steiner Latin square $$\begin{array}{ccccccc} 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{array}$$
which has indeed several features showing a high symmetry, e.g.

  • it is symmetric w.r.t. the main diagonal
  • each of the 7 entries on the main diagonal belongs to exactly 3 of the 7 $3\times3$ Latin subsquares, while each off-diagonal entry $a_{ij}$ belongs to exactly one, which is made up of $a_{ij}, a_{ii}, a_{jj}$.
  • $3\times3$ Latin subsquares exist for the set $\{0,1,3\}$ and its cyclic shifts.
  • each off-diagonal entry (and only those) belongs to four $2\times2$ Latin subsquares (there are $42$ of them, two for each of the $7\choose2$ pairs $0\le i<j\le6$).

In spite of the asymmetry of the cyclic permutation $(0361542)$, I guess there must be a close connection between this Latin square and the Fano plane. (END OF EDIT)

  • Further on, the (unique) LS with the least number of transversals, thus having $c_7$ minimal, is given by 0123456120563420143653652140456120354360216340512 with signature $(7, 54, 591, 2060, 1797, 528, 3)$, where $c_6$ is maximal.

  • And the only LS of order $7$ other than $\mathbb Z_7$ with $c_2=0$ is 0123456150634223150643042615426150356341206450231 with signature $(7, 0, 774, 1804, 1998, 432, 25)$, where $c_3$ is next-to-maximal. Similar question for those two ones.

Some results and conjectures about transversals, but rather concentrating on partial transversals, are summarized in Ian Wanless, Transversals in Latin Squares.
For 8x8 squares, it would take my computer almost a year to get the signatures of all 1676267 isotopy classes, but the following question about min-max patterns might be feasible:

Knowing that always $\sum c_k=n!$, it seems somewhat plausible that a LS where a certain $c_k$ is minimal may have a certain other $c_\ell$ maximal (and vice versa). Can that be shown particularly for $(k,\ell)=(3,2)$ and $(k,\ell)=(n-1,n)$?

$\endgroup$
  • $\begingroup$ @YBerman If you mean asking people who have access to big computing power and you know some, then yes please, feel free to help... $\endgroup$ – Wolfgang Mar 17 '17 at 14:21
  • $\begingroup$ The cyclic permutation (0361542) which produces the Steiner square can be replaced by its "dual" (0532614). The new square is obtained by applying the permutation (16)(25)(34) to lines, columns and entries. There don't seem to exist other permutations of $S_7$ with this property. What does that mean? $\endgroup$ – Wolfgang Mar 17 '17 at 20:49
  • $\begingroup$ Your reply to my offer for help annoyed me, but I decided to partially solve your problem anyways. $\endgroup$ – yberman Mar 19 '17 at 1: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.