Can equi-$n$-squares be seen as wavy-latin $n$-squares?

56 Views Asked by At

An equi-$n$-square (S.K.Stein, 1975) is a square $n$-matrix with digits (colors) $0 \ldots n-1$ occurring $n$ times each. Latin squares have the stronger property that each digit occurs once in each row and once in each column. In general, a set of positions in an equi-$n$-square is called latin if its positions are all colored differently.

Rows can be seen as a particular kind of function graph: a set of positions with one position in each column. Let us call these H-graphs. Similarly, columns can be seen as a kind of vertically oriented graph, with one position in each row. Let us call these V-graphs. Note that a complete transversal is just an H-graph which is also a V-graph. H-graphs and V-graphs can be seen as "wavy" rows, resp., columns.

It is not difficult to prove (e.g., with network flows) that the positions of an equi-$n$-square can be partitioned into $n$ latin sets which are H-graphs. The same goes with latin V-graphs. This suggests to look for wavy-latin $n$-squares in an equi-$n$-square: a partition into latin H-graphs and a partition into latin V-graphs such that each H-graph intersects each V-graph in one position. Here are three examples of equi-$n$-squares which are not a wavy-latin square:

$$\left(\begin{array}{cc}1&0\\1&0\end{array}\right),$$ $$ \left(\begin{array}{ccc}1&2&1\\1&0&0\\2&2&0\end{array}\right),$$ $$\left(\begin{array}{cccc}1&1&3&2\\1&1&3&3\\3&2&0&0\\2&2&0&0\end{array}\right).$$

I reported on this question in my paper "shuffled equi-$n$-squares, available at

http://arxiv.org/abs/1701.02325

Exhaustive computer search has shown that among all isotopism types and modulo transposition, there is only 1 example of a non-wavy equi-$3$-square (on 9 types). For $n = 4$ there are $3160$ types among which only $8$ are not wavy-latin. For $n = 5$ we searched a random sample of $2000$ types and found no counterexample (a full computer search in one type takes $10$ minutes on average; it is hard to search much larger samples). I could verify that an equi-5-square, where each color somewhere has a row or column with 4 members of that color, must be wavy-latin.

Question. Does the ratio (wavy-latin $n$-squares / equi-$n$-squares) tend to $1$ with increasing $n$? Is there a size $n_0$ such that for each $n \ge n_0$ all equi-$n$-squares are wavy-latin (perhaps $n_0 = 5$)?

Lack of latin $n$-size transversals is obviously a major obstacle.