1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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\}$).

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – John
    Feb 11 at 11:15
  • 1
    $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Feb 11 at 20:40
  • $\begingroup$ 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. $\endgroup$
    – John
    Feb 12 at 7:43
  • $\begingroup$ I don't know an easy way, but the counts for small $n$ are $$1,0, 3, 16, 115, 468, 4151, 30208, 329589$$ $\endgroup$
    – RobPratt
    Feb 13 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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