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

Question

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.

Answer 1

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