# A bound on the number of partial transversals of a latin square

A Latin Square (LS) of order $$n$$ is an $$n$$ on $$n$$ matrix, each entry contains one of the symbols $$1,2,\ldots,n$$, and every row and every column contains each symbol exactly once. A (complete) Transversal in a Latin square is a collection of $$n$$ entries of the Latin square with exactly one appearance for each row, each column, and each symbol. For some $$k = 1,\ldots,n$$, a partial transversal of size $$k$$ is a collection of $$n$$ entries of the Latin square with exactly one appearance for each row and each column such that exactly $$k$$ symbols appear in the collection (equivalently for the discussion here, it can be defined over a collection of size $$k$$ with distinct symbols). An equivalent point of view is a complete bipartite graph with $$n$$ vertices of each side, where each edge is colored in one of $$n$$ colors, such that the edges adjacent to each vertex are exactly one edge from each of the $$n$$ colors. In this formulation, a transversal is called a rainbow matching.

Question: I am interested, as part of my research, in finding a Latin square with as few as possible partial transversals of size more than $$n/2$$, which is half of the size of a complete transversal. Formally, for some $$n \geq 1$$ and a Latin square $$L$$ of order $$n$$, define $$a(L)$$ as the number of partial transversals in $$L$$ of size more than $$n/2$$. Define $$a_n$$ as the minimum value of $$a(L)$$ over all Latin squares $$L$$ of order $$n$$. What is the best upper bound we can get on $$a_n$$?

Note that it is irrelevant if the Latin square that satisfies the bound has a complete transversal or not; indeed, it is conjectured that every Latin square either has a transversal or a partial transversal with size $$n-1$$ and thus this does not seem to affect the bound considered in this question.

• $>n/2$ or $\ge n/2$? Feb 7 at 22:58
• I meant > n/2 but it should not be very important either way.
– John
Feb 8 at 5:52

Here are some results for small $$n$$, obtained via integer linear programming.

$$a_1 = 1$$: $$\begin{matrix} 1 \\ \end{matrix}$$

$$a_2 = 0$$: $$\begin{matrix} 1 & 2 \\ 2 & 1 \\ \end{matrix}$$

$$a_3 = 3$$: $$\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{matrix}$$

$$a_4 = 8$$: $$\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \end{matrix}$$

$$a_5 = 107$$: $$\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 5 & 4 \\ 2 & 4 & 5 & 1 & 3 \\ 4 & 5 & 1 & 3 & 2 \\ 5 & 3 & 4 & 2 & 1 \\ \end{matrix}$$

$$a_6 = 432$$: $$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 6 & 3 & 2 & 5 \\ 6 & 5 & 2 & 1 & 4 & 3 \\ 3 & 6 & 5 & 2 & 1 & 4 \\ 2 & 3 & 4 & 5 & 6 & 1 \\ 5 & 4 & 1 & 6 & 3 & 2 \\ \end{matrix}$$

$$a_7 \le 4151$$: $$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 4 & 5 & 6 & 7 & 1 \\ 3 & 4 & 5 & 6 & 7 & 1 & 2 \\ 4 & 5 & 6 & 7 & 1 & 2 & 3 \\ 5 & 6 & 7 & 1 & 2 & 3 & 4 \\ 6 & 7 & 1 & 2 & 3 & 4 & 5 \\ 7 & 1 & 2 & 3 & 4 & 5 & 6 \\ \end{matrix}$$

You could get a general upper bound for $$a_n$$ by counting partial traversals in the pattern that is illustrated for $$n=7$$. (This pattern is not optimal for $$n\in\{4,5,6\}$$).

• Hey thank you for the effort. I do not understand though how can I get a general upper bound on $a_n$ for a general $n$ via the details on $n = 7$.
– John
Feb 11 at 11:15
• Every Latin square for a given $n$ provides an upper bound for that $n$. Computing the number of partial traversals in this "striped" pattern would yield an upper bound on $a_n$. Feb 11 at 20:40
• Thanks. Is there an easy of of computing such an upper bound on this "striped" pattern for a general $n$? I mean something combinatorial without using a computer.
– John
Feb 12 at 7:43
• I don't know an easy way, but the counts for small $n$ are $$1,0, 3, 16, 115, 468, 4151, 30208, 329589$$ Feb 13 at 3:01