5
$\begingroup$

According to this thesis, page $28$, the following Latin Square has $3$ $0$-s transversals: $$\begin{bmatrix}1 & 2 & 3 & 4 & 5\\ 2 & 4 & 1 & 5 & 3\\ 3 & 5 & 4 & 2 & 1\\ 4 & 1 & 5 & 3 & 2\\5 & 3 & 2 & 1 & 4\end{bmatrix} \implies \begin{bmatrix}1 & & & &\\ & & & 5 & \\ & & 4 & & \\ & & & & 2\\ & 3\end{bmatrix}, \begin{bmatrix}& & & 4 &\\2 & & & &\\ & & & & 1 \\ & & 5 & &\\ & 3\end{bmatrix}, \begin{bmatrix}& & & &5\\& & 1 & &\\ & & & 2 &\\4 & & & &\\& 3\end{bmatrix}.$$ The definition of a $0$-s transversal for a Latin square of order $n$ is

a set of $n$ ordered triples such that the first and second entries are the rows and columns respectively in which the values $1,\ldots,n$ occur exactly once and the third entry of the triple is the value, of which there are $n$ distinct values.

Basically, we need to visit each row and column only once and we must have $5$ distinct symbols at the end. I can represent each transversal as $$t_1 = \{(1,1,1),(2,4,5),(3,3,4),(4,5,2),(5,2,3)\}$$ $$t_2 = \{(1,4,4),(2,1,2),(3,5,1),(4,3,5),(5,2,3)\}$$ $$t_3 = \{(1,5,5),(2,3,1),(3,4,2),(4,1,4),(5,2,3)\}$$ So why are these the only three? How do I know there are only three of them?

$\endgroup$
1
$\begingroup$

I don't think there's any slick way to determine that this Latin square has exactly $3$ transversals---we just count them. E.g., here's some GAP code:

L:=[[1,2,3,4,5],[2,4,1,5,3],[3,5,4,2,1],[4,1,5,3,2],[5,3,2,1,4]];;

ExtendPartialTransversal:=function(T)
  local i,j,TNew;

  # we try to add entry (i,j,L[i][j]) to T without clashing  

  # looking at row i
  i:=Size(T)+1;

  # looking at column j
  for j in [1..5] do

    # column already used
    if(ForAny([1..i-1],k->T[k][2]=j)) then continue; fi;

    # symbol already used
    if(ForAny([1..i-1],k->T[k][3]=L[i][j])) then continue; fi;

    # add to partial transversal
    TNew:=Concatenation(T,[[i,j,L[i][j]]]);

    # if transversal complete, then print, otherwise extend
    if(Size(TNew)=5) then
      Print(TNew,"\n");
    else
      ExtendPartialTransversal(TNew);
    fi;

  od;
end;;

# start with the empty partial transversal
ExtendPartialTransversal([]);

which returns the three transversals:

[ [ 1, 1, 1 ], [ 2, 4, 5 ], [ 3, 3, 4 ], [ 4, 5, 2 ], [ 5, 2, 3 ] ]
[ [ 1, 4, 4 ], [ 2, 1, 2 ], [ 3, 5, 1 ], [ 4, 3, 5 ], [ 5, 2, 3 ] ]
[ [ 1, 5, 5 ], [ 2, 3, 1 ], [ 3, 4, 2 ], [ 4, 1, 4 ], [ 5, 2, 3 ] ]

and shows there's no others by exhaustive search.

$\endgroup$
  • $\begingroup$ Is there a simple modification to your code that seeks out only disjoint transversals? To the best of my understanding, I noticed that the code selects a row, column, then prints the symbol in that position. It iterates through until something of length $n$ is generated. $\endgroup$ – emka Jun 20 '17 at 18:01
  • $\begingroup$ The code only looks at one transversal at a time. To talk about disjoint transversals, we'd need to look at multiple simultaneously. It could be done, but it'd require substantial modification (not just a one-line edit). $\endgroup$ – Rebecca J. Stones Jun 20 '17 at 20:21
  • $\begingroup$ That's what I was afraid of. I'm working with a larger latin squares (specifically 10x10). In my situation, we already know the position of some transversals. I want to see if, of all the completions I have found, one of them could be decomposed into transversals. $\endgroup$ – emka Jun 20 '17 at 20:25
0
$\begingroup$

A latin square is represented as $t_i=(r,c,s)$ which means that r represents row of the latin square, c represents column of the latin square and s is the number whose location is $row=r\;\;and\;\;column=c$.

$\endgroup$
  • $\begingroup$ Now look at the square.You will understand why it is three. $\endgroup$ – sayan kundu Apr 15 '16 at 7:44
0
$\begingroup$

"I'm working with a larger latin squares (specifically 10x10). In my situation, we already know the position of some transversals. I want to see if, of all the completions I have found, one of them could be decomposed into transversals."

If you find all the transversals of the Latin square, then it is easy to find disjoint transversals.

Example

This diagonal Latin square

0 2 4 7 8 9 5 6 3 1
5 1 9 6 3 2 4 8 0 7
6 7 2 9 1 0 8 3 5 4
9 4 0 3 5 7 2 1 6 8
7 0 3 8 4 6 9 2 1 5
2 8 6 0 7 5 1 4 9 3
1 5 8 4 2 3 6 9 7 0
4 3 5 1 9 8 0 7 2 6
3 9 1 5 6 4 7 0 8 2
8 6 7 2 0 1 3 5 4 9

has 104 diagonal transversals. Among them there are 8 sets of 10 non-intersecting transversals, which gives 8 orthogonal diagonal Latin squares for a given diagonal Latin square

#1
 0 1 2 3 4 5 6 7 8 9
 9 7 4 1 3 0 8 5 2 6
 2 5 8 9 6 7 0 1 4 3
 8 4 3 6 2 9 7 0 5 1
 7 6 9 8 5 4 1 2 3 0
 3 2 6 4 8 1 5 9 0 7
 4 8 7 0 9 2 3 6 1 5
 1 0 5 2 7 3 9 4 6 8
 5 3 1 7 0 6 2 8 9 4
 6 9 0 5 1 8 4 3 7 2

#2
 0 1 2 3 4 5 6 7 8 9
 9 7 4 1 3 0 8 5 2 6
 2 5 8 9 6 7 0 1 4 3
 8 4 3 6 2 9 7 0 5 1
 7 6 9 8 5 4 1 2 3 0
 3 2 6 5 8 1 4 9 0 7
 5 8 7 0 9 2 3 6 1 4
 1 0 5 2 7 3 9 4 6 8
 4 3 1 7 0 6 2 8 9 5
 6 9 0 4 1 8 5 3 7 2

#3
 0 1 2 3 4 5 6 7 8 9
 9 7 4 8 3 0 1 5 2 6
 2 5 8 9 6 7 0 1 4 3
 1 4 3 6 2 9 7 0 5 8
 7 6 9 1 5 4 8 2 3 0
 3 2 6 4 8 1 5 9 0 7
 4 8 7 0 9 2 3 6 1 5
 8 0 5 2 7 3 9 4 6 1
 5 3 1 7 0 6 2 8 9 4
 6 9 0 5 1 8 4 3 7 2

#4
 0 1 2 3 4 5 6 7 8 9
 9 7 4 8 3 0 1 5 2 6
 2 5 8 9 6 7 0 1 4 3
 1 4 3 6 2 9 7 0 5 8
 7 6 9 1 5 4 8 2 3 0
 3 2 6 5 8 1 4 9 0 7
 5 8 7 0 9 2 3 6 1 4
 8 0 5 2 7 3 9 4 6 1
 4 3 1 7 0 6 2 8 9 5
 6 9 0 4 1 8 5 3 7 2

#5
 0 1 2 3 4 5 6 7 8 9
 3 7 4 1 9 6 8 5 2 0
 6 5 8 9 2 3 0 1 4 7
 8 4 9 2 0 7 3 6 5 1
 9 6 7 8 5 4 1 0 3 2
 2 9 0 4 8 1 5 3 7 6
 4 8 3 6 7 0 9 2 1 5
 1 3 5 0 6 2 7 4 9 8
 5 0 1 7 3 9 2 8 6 4
 7 2 6 5 1 8 4 9 0 3

#6
 0 1 2 3 4 5 6 7 8 9
 3 7 4 1 9 6 8 5 2 0
 6 5 8 9 2 3 0 1 4 7
 8 4 9 2 0 7 3 6 5 1
 9 6 7 8 5 4 1 0 3 2
 2 9 0 5 8 1 4 3 7 6
 5 8 3 6 7 0 9 2 1 4
 1 3 5 0 6 2 7 4 9 8
 4 0 1 7 3 9 2 8 6 5
 7 2 6 4 1 8 5 9 0 3

#7
 0 1 2 3 4 5 6 7 8 9
 3 7 4 8 9 6 1 5 2 0
 6 5 8 9 2 3 0 1 4 7
 1 4 9 2 0 7 3 6 5 8
 9 6 7 1 5 4 8 0 3 2
 2 9 0 4 8 1 5 3 7 6
 4 8 3 6 7 0 9 2 1 5
 8 3 5 0 6 2 7 4 9 1
 5 0 1 7 3 9 2 8 6 4
 7 2 6 5 1 8 4 9 0 3

#8
 0 1 2 3 4 5 6 7 8 9
 3 7 4 8 9 6 1 5 2 0
 6 5 8 9 2 3 0 1 4 7
 1 4 9 2 0 7 3 6 5 8
 9 6 7 1 5 4 8 0 3 2
 2 9 0 5 8 1 4 3 7 6
 5 8 3 6 7 0 9 2 1 4
 8 3 5 0 6 2 7 4 9 1
 4 0 1 7 3 9 2 8 6 5
 7 2 6 4 1 8 5 9 0 3

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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