# Open Questions on Latin Squares and Directed Acyclic Graphs

Every Latin square corresponds to a directed acyclic graph (DAG) with a lattice arrangement, and whose $2N(N-1)$ edges indicate label order (<). For example:

For example http://forum.enjoysudoku.com/download/file.php?id=336

If we define an $LDAG$ to be a DAG which corresponds to a Latin square, then there are some open questions concerning these objects:

(1) How many different $LDAG$'s are there, for a given $N$? We know that the same DAG can correspond to many Latin squares. One $N=9$ case we encountered corresponds to 2,748,444 different LS's.

(2) How many $LDAG$'s are unique orderings? That is, how many correspond to only 1 Latin square. We believe that most are, but have only explored small $N$.

(3) How many LS's can share the same $LDAG$?

These questions originally arose in relation to a study of the uniqueness of solutions in Futoshiki puzzles, but we believe these are questions of general interest.

We have some numbers for small $N$ available:

 N Latin Sq LDAG Unique U/LDAG U/LS 3 12 12 12 1.000 1.0000 4 576 418 350 0.837 0.6076 5 161280 115262 82148 0.713 0.5094 6 812851200 385204902 217548736 0.565 0.2676 

These figures are obtained from exhaustive enumeration of the Latin squares, generating a list of $LDAG$'s, reducing this to remove duplicates, then testing each one for uniqueness using a DFS traversal adapted for LS detection (ie. a DFS Futoshiki solver).

For $N>6$, we can approximate fairly accurately $P_u(N)$, the probability of a random Latin square of rank $N$ having a unique ordering (the last column of the table above), by sampling sufficient randomly generated Latin squares.

The observed probabilities for $N=7,8,9$ are $P_u(7)$ = 12%, $P_u(8)$ = 4%, for $P_u(9)$ = 1%.

## 1 Answer

Question (3) asks "what is the maximum number of order-equivalent Latin squares?"

The simplest case of order-equivalence is 2 Latin squares that differ only by an intercalate (in mutually non-adjacent positions) involving (but not restricted to) consecutive symbol values. For example:

$$\begin{bmatrix} 1 & 2 & 5 & 3 & 4 \\ 3 & 5 & \color{red}1 & 4 & \color{red}2 \\ 5 & 1 & 4 & 2 & 3 \\ 2 & 4 & 3 & 1 & 5 \\ 4 & 3 & \color{red}2 & 5 & \color{red}1 \end{bmatrix} \equiv \begin{bmatrix} 1 & 2 & 5 & 3 & 4 \\ 3 & 5 & \color{red}2 & 4 & \color{red}1 \\ 5 & 1 & 4 & 2 & 3 \\ 2 & 4 & 3 & 1 & 5 \\ 4 & 3 & \color{red}1 & 5 & \color{red}2 \end{bmatrix}$$

We call this an order-preserving cycle (OPC). This is really just another way of defining order-equivalence, since being equivalent necessarily involves an OPC of some description, however these can be more complicated than just cycle-swaps on two symbols. They are often multiple cycles interwoven. For example:
$$\begin{bmatrix} 4 & 3 & 5 & 1 & 6 & 2 \\ \color{blue}2 & 5 & \color{blue}1 & 4 & \color{blue}3 & 6 \\ 6 & 1 & \color{blue}4 & 2 & 5 & \color{blue}3 \\ \color{blue}1 & 4 & \color{blue}3 & 6 & \color{blue}2 & 5 \\ 5 & 2 & 6 & 3 & 4 & 1 \\ \color{blue}3 & 6 & \color{blue}2 & 5 & \color{blue}1 & \color{blue}4 \end{bmatrix} \equiv \begin{bmatrix} 4 & 3 & 5 & 1 & 6 & 2 \\ \color{blue}3 & 5 & \color{blue}2 & 4 & \color{blue}1 & 6 \\ 6 & 1 & \color{blue}3 & 2 & 5 & \color{blue}4 \\ \color{blue}2 & 4 & \color{blue}1 & 6 & \color{blue}3 & 5 \\ 5 & 2 & 6 & 3 & 4 & 1 \\ \color{blue}1 & 6 & \color{blue}4 & 5 & \color{blue}2 & \color{blue}3 \end{bmatrix}$$
We can also distinguish weak orderings from strong orderings.

Strongly-ordered squares have longer chains (directed paths in the $LDAG$) than weakly-ordered ones. Chains of length $N$ (it makes sense to define chain length for LS's in terms of vertices, rather than edges) greatly increase the probability of unique orderings.

So it makes sense to consider the weakest possible ordering, and to conjecture that these will correspond to order-equivalence classes with maximum cardinality.

For even $N$, it is easy to construct a square in which every cell is either a source or a sink, thus giving a square with no chains of length greater than 2 (sinks shown in red):

$$\begin{bmatrix} 1 & \color{darkred}6 & 3 & \color{darkred}4 & 2 & \color{darkred}5 \\ \color{darkred}5 & 1 & \color{darkred}6 & 3 & \color{darkred}4 & 2 \\ 2 & \color{darkred}5 & 1 & \color{darkred}6 & 3 & \color{darkred}4 \\ \color{darkred}4 & 2 & \color{darkred}5 & 1 & \color{darkred}6 & 3 \\ 3 & \color{darkred}4 & 2 & \color{darkred}5 & 1 & \color{darkred}6 \\ \color{darkred}6 & 3 & \color{darkred}4 & 2 & \color{darkred}5 & 1 \end{bmatrix}$$

For even $N$, the number of ways, $C_n$ to fix half of the symbols in half of the rows is $C_n=\prod\limits_{k=1}^{n/2} k!$, so there are $C{_n}^4$ latin squares which match this pattern. In this case $C{_6}=24$, so we expect at least $24^4=20,736$ LS's to be equivalent to this one.

For odd $N$, we can have every cell apart from one major diagonal as source or sink. For $N=5$, this construction would be (sinks in red, sources in blue):

$$\begin{bmatrix} 3 & \color{darkred}4 & \color{darkblue}1 & \color{darkred}5 & \color{darkblue}2 \\ \color{darkblue}2 & 3 & \color{darkred}4 & \color{darkblue}1 & \color{darkred}5 \\ \color{darkred}5 & \color{darkblue}2 & 3 & \color{darkred}4 & \color{darkblue}1 \\ \color{darkblue}1 & \color{darkred}5 & \color{darkblue}2 & 3 & \color{darkred}4 \\ \color{darkred}4 & \color{darkblue}1 & \color{darkred}5 & \color{darkblue}2 & 3 \end{bmatrix}$$

This gives $N(N-1)$ sinks/sources, and this LS has 8 members in its order-equivalence class. But in fact we can increase these numbers with the following arrangement:

$$\begin{bmatrix} \color{darkblue}1 & \color{darkred}3 & \color{darkblue}2 & \color{darkred}5 & \color{darkblue}4 \\ \color{darkred}4 & \color{darkblue}1 & 3 & \color{darkblue}2 & \color{darkred}5 \\ \color{darkblue}2 & 4 & \color{darkred}5 & 3 & \color{darkblue}1 \\ \color{darkred}5 & \color{darkblue}2 & 4 & \color{darkblue}1 & \color{darkred}3 \\ \color{darkblue}3 & \color{darkred}5 & \color{darkblue}1 & \color{darkred}4 & \color{darkblue}2 \end{bmatrix}$$

This LS has 16 members in its order-equivalence class, which is the maximum for $N=5$.

For $N=7$, the pattern is similar to $N=5$, except that the 4-cell non-sink/source pattern is found in any of 4 off-center positions: $$\begin{bmatrix} \color{darkblue}6 & \color{darkred}7 & \color{darkblue}3 & \color{darkred}5 & \color{darkblue}2 & \color{darkred}4 & \color{darkblue}1 \\ \color{darkred}7 & \color{darkblue}1 & \color{darkred}5 & \color{darkblue}3 & \color{darkred}6 & \color{darkblue}2 & \color{darkred}4 \\ \color{darkblue}2 & \color{darkred}5 & \color{darkblue}4 & \color{darkred}7 & \color{darkblue}1 & \color{darkred}6 & \color{darkblue}3 \\ \color{darkred}4 & \color{darkblue}3 & \color{darkred}7 & \color{darkblue}2 & 5 & \color{darkblue}1 & \color{darkred}6 \\ \color{darkblue}3 & \color{darkred}6 & \color{darkblue}1 & 4 & \color{darkred}7 & 5 & \color{darkblue}2 \\ \color{darkred}5 & \color{darkblue}2 & \color{darkred}6 & \color{darkblue}1 & 4 & \color{darkblue}3 & \color{darkred}7 \\ \color{darkblue}1 & \color{darkred}4 & \color{darkblue}2 & \color{darkred}6 & \color{darkblue}3 & \color{darkred}7 & \color{darkblue}5 \end{bmatrix}$$

This LS has 156,252 members in its order-equivalence class, and is probably the maximal case. Interestingly, we have found 7 x 7 LS's with more sinks/sources (eg 47), but whose order-equivalence class is smaller.

If we denote the maximum cardinality of equivalence classes as $M_N$, then we have:

• $M_4 \ge 2^4 = 16$ (the actual maximum is 17)
• $M_5 = 16$
• $M_6 \ge 12^4 = 20,736$ (actual maximum 25,498)
• $M_7 \ge 156,152$ (highest found so far)
• $M_8 \ge 288^4$

For even $N$, the value $C_n^{4}$ is only a lower-bound on $M_n$, since these are not the only order-equivalences possible. For example, $M_4 = 2^4 + 1$, the 17th LS obtained from the following equivalence:

$$\begin{bmatrix} \color{blue}3 & 1 & 4 & \color{blue}2 \\ 1 & 3 & 2 & 4 \\ 4 & 2 & 3 & 1 \\ \color{blue}2 & 4 & 1 & \color{blue}3 \end{bmatrix} \equiv \begin{bmatrix} \color{blue}2 & 1 & 4 & \color{blue}3 \\ 1 & 3 & 2 & 4 \\ 4 & 2 & 3 & 1 \\ \color{blue}3 & 4 & 1 & \color{blue}2 \end{bmatrix}$$