---
abstract: |
    A [*Latin array*]{} is a matrix of symbols in which no symbol occurs more than once within a row or within a column. A [*diagonal*]{} of an $n\times n$ array is a selection of $n$ cells taken from different rows and columns of the array. The [*weight*]{} of a diagonal is the number of different symbols on it. We show via computation that every Latin array of order $n{\leqslant}11$ has a diagonal of weight at least $n-1$. A corollary is the existence of near transversals in Latin squares of these orders.

    More generally, for all $k{\leqslant}20$ we compute a lower bound on the order of any Latin array that does not have a diagonal of weight at least $n-k$.

    Keywords: Latin square, Latin array, near transversal, partial transversal, Brualdi’s conjecture\
    Mathematics Subject Classification: 05B15
author:
- 'Darcy Best[^1] '
- 'Kyle Pula[^2]'
- 'Ian M. Wanless[^3]'
title: Small Latin arrays have a near transversal
---

\[s:intro\]Introduction
=======================

In this article, we examine several different types of arrays of symbols. An $m \times n$ array is *row-Latin* (resp. *column-Latin*) if each row (resp. column) contains each symbol at most once. If the array is both row-Latin and column-Latin, then we say that the array is *Latin*. An *equi-$n$-square* is an $n \times n$ array where each symbol is represented exactly $n$ times, with no row or column restrictions. A *Latin square* is a Latin equi-$n$-square.

A *diagonal* of an $n\times n$ array is a selection of $n$ cells from different rows and columns of the array. The *weight* of a diagonal is the number of different symbols on it. An *entry* in an array is a triple $(r,c,s)$ where $s$ is the symbol in cell $(r,c)$ of the array. A *partial transversal of length* $\ell$ is a set of $\ell$ entries, each selected from different rows and columns of a matrix, such that no two of the entries contain the same symbol. In a matrix of order $n$, partial transversals of length $n$ and $n-1$, respectively, are known as *transversals* and *near transversals*. Hence, a diagonal of weight $n$ is a transversal and a diagonal of weight $n-1$ *contains* two near transversals. Note that partial transversals are defined for non-square arrays, but diagonals are not.

It is known that there are a vast number of Latin squares that do not contain a transversal [@CW17]. Thus, the best we can hope for in general is a near transversal. The following conjecture has been attributed to Brualdi (see [@DKI p.103]) and Stein [@Ste75] and, in [@EHNS88], to Ryser. It has recently been proved for Cayley tables of finite groups [@GH20]. For several generalisations of the conjecture, in terms of hypergraphs, see [@AB09] (although some of those generalisations have since been shown to fail [@GRWW19]).

\[conj:brualdi\] Every Latin square of order $n$ contains a near transversal.

The main result of this paper is that every Latin array of order $n{\leqslant}11$ has a diagonal of weight at least $n-1$. In particular, holds for $n{\leqslant}11$. Our method will be computational, but it is worth bearing in mind that the number of Latin squares of orders up to 11 is too large to treat them individually [@MW05], and the number of Latin arrays of these orders is presumably many orders of magnitude larger. Hence the key to the viability of our computation is to eliminate candidate counterexamples on the basis of limited partial information about their structure. In particular, we will need to consider *partial arrays*, where some cells may be empty (contain no symbol). Empty cells cannot be chosen in a partial transversal, but may be included in a diagonal (in which case, they do not contribute to the weight of that diagonal).

Since the result we are proving for small squares is more general than , we now review earlier attempts to broaden that conjecture in various directions. In 1975, Stein [@Ste75] studied transversals in equi-$n$-squares. He made the following seven interrelated conjectures:

\[conj:stein\]

1.  Every equi-$n$-square has a near transversal.

2.  Every $n \times n$ array in which no symbol appears more than $n-1$ times has a transversal.

3.  Every $(n-1) \times n$ array in which no symbol appears more than $n$ times has a transversal.

4.  Every $(n-1) \times n$ row-Latin array has a transversal.

5.  Every $m \times n$ array (where $m < n$) in which no symbol appears more than $n$ times has a transversal.

6.  Every $(n-1) \times n$ array in which each symbol appears exactly $n$ times has a transversal.

7.  Every $m \times n$ array (where $m < n$) in which no symbol appears more than $m+1$ times has a transversal.

Note that modern authors often include a requirement that for an array to be row-Latin it should have the same symbols in each row. However, Stein did not include that restriction, so in this paper we do not either.

Stein’s conjectures are closely related to one another (with some being special cases of others). Unfortunately, all but one of these conjectures has been disproven (only number (4) remains open). In 1998, Drisko [@Drisko98] gave the (transpose of) the following construction. The proof that we give is new, and in the spirit of the Delta Lemma (see [@transurvey]). Here and henceforth, row and column indices always start at 0.

\[t:Drisko\] Let $m$ and $n$ be integers satisfying $m < n {\leqslant}2m-2$. Define an $m\times n$ column-Latin array $A=[a_{ij}]$ on symbols $\{0,\dots,m-1\}$, by $$a_{ij}\mod m{\equiv}\begin{cases}
i&\text{if $j\in\{0,\dots,m-2\}$},\\
i+1&\text{if $j\in\{m-1,\dots,n-1\}$}.
\end{cases}$$ Then $A$ has no transversals.

Define $\Delta(i,j)=a_{ij}-i$ for $0{\leqslant}i<m$ and $0{\leqslant}j<n$. Suppose that $A$ has a transversal on cells $(0,j_0),\dots,(m-1,j_{m-1})$. Then since every symbol in $\{0,\dots,m-1\}$ appears in the transversal it follows that $$\sum_{i=0}^{m-1}\Delta(i,j_i){\equiv}\sum_{i=0}^{m-1}i-\sum_{i=0}^{m-1}i{\equiv}0\mod m.$$ However, this congruence is impossible to satisfy, given that $\Delta(i,j)=0$ for $j{\leqslant}m-2$ and $\Delta(i,j){\equiv}1\mod m$ for $j>m-2$, so that $$\sum_{i=0}^{m-1}\Delta(i,j_i){\equiv}|\{i:j_i>m-2\}|\not{\equiv}0\mod m.\qedhere$$

The $m = n-1$ case of is a direct counterexample to \[conj:stein\] parts (3), (5), (6) and (7). Furthermore, Pokrovskiy and Sudakov [@PS19] recently gave a constructive proof of the following.

\[th:stein-wrong\] For all sufficiently large $n$ there exists an equi-$n$-square that does not have a partial transversal of length more than $n-\frac{1}{42}\log n$.

This is a counterexample to \[conj:stein\](1). Moreover, Pokrovskiy and Sudakov showed how their result can be extended to give counterexamples to statements like \[conj:stein\](2) as well. For some $n>e^{84}$, use \[th:stein-wrong\] to construct an equi-$n$-square $E$ of order $n$ with no partial transversal of length $n-2$. Now, form a matrix $A$ of order $n+1$ by adding one row and one column to $E$, where the new row and column contain $2n+1$ distinct symbols that do not appear in $E$. Since at most two of these new symbols can be used in any partial transversal, $A$ does not have a transversal. By a similar argument, we can pad an appropriate equi-$n$-square with either new symbols or the original symbols to provide counterexamples to parts (3), (5), (6) and (7) that are of a different nature to the counterexamples provided by . Interestingly, [@PS13] shows that almost all equi-$n$-squares have a transversal, so these counterexamples may be viewed as atypical.

The only one of Stein’s conjectures that remains unsolved is (4). While we are quite unsure about this conjecture, it seems much more promising if we also enforce the array to be column-Latin.

\[conj:brualdi-rectangle\] Let $R$ be an $(n-1) \times n$ Latin array. Then $R$ contains a transversal.

Note that this conjecture implies a strengthened form of , where we may choose which row (or column or symbol) is not included in our partial transversal. It is an open question (see [@BW14]) whether an even stronger property holds when $n$ is large: it may be that all large $(n-1) \times n$ Latin arrays on $n$ symbols have a decomposition into transversals. Often such arrays are called *Latin rectangles*. Interestingly, it is not possible to relax the requirement on the number of symbols. We know there are many Latin squares without transversals [@CW17]. If a column of previously unused symbols is appended to such a Latin square we create a Latin array with no decomposition into transversals. Alternatively, if we remove the first two rows and the first column from the Cayley table of an elementary abelian group of order $2^k>2$ then we get an $(2^k-2)\times(2^k-1)$ Latin array on $2^k$ symbols, with no decomposition into transversals. This follows from a result of Akbari and Alireza [@AA04]. Nevertheless, Latin arrays that are in some sense far from being Latin squares are known to have many transversals. Montgomery *et al.* [@MPS20] recently showed that an $n\times n$ Latin array in which at most $(1-o(1))n$ symbols occur more than $(1-o(1))n$ times has $(1-o(1))n$ pairwise disjoint transversals.

A partial transversal is *maximal* if it is not contained in any longer partial transversal. It is not hard to see that a maximal partial transversal of length $\ell$ in a Latin square of order $n$ must satisfy $n/2{\leqslant}\ell{\leqslant}n$. In [@BMSW19] it was shown that for $n{\geqslant}5$ all values of $\ell$ in this range are achieved. Then Evans [@Eva19] constructed an infinite family of Latin squares which simultaneously have maximal partial transversals of each of the permissible lengths. Subsequently, Evans *et al.* [@EMW20] showed that there exists a Latin square of order $n$ which has maximal partial transversals of each permissible length if and only if $n\notin\{3,4\}$ and $n \not\equiv 2 \pmod 4$.

In Latin squares, it is easy to find a partial transversal of length $\lceil n/2 \rceil$ using a greedy algorithm. In 1969, Koksma [@trans-23] showed that there is a partial transversal of length at least $(2n+1)/3$. Over the next decade, the $2/3$ coefficient was improved to $3/4$ and $9/11$ in [@drake-77] and [@part-trans-911], respectively. Then, in 1978, Brouwer [*et al.*]{} [@Brouwer78] and Woolbright [@Woolbright78] independently proved that every Latin square contains a partial transversal of length at least $n-\sqrt{n}$. This result has been reproven in different settings. For example, Aharoni [*et al.*]{} [@AKZ16] proved a related result for matroids. Here, we give a fairly general version of the result. The essence of the proof is not dramatically changed from those original proofs, but the statement is somewhat more general.

\[th:n-sqrt-n\] Let $L$ be an $m \times n$ partial column-Latin array with at most $h$ empty cells per column. If the longest partial transversal in $L$ is of length $t$, then $t {\geqslant}(n-t)(m-t-h)$.

Assume that there are $k$ symbols in $L$ and that the rows, columns and symbols are indexed by $\{0,\dots,m-1\}$, $\{0,\dots,n-1\}$ and $\{0,\dots,k-1\}$, respectively. Without loss of generality, assume that $L(i,i) = i$ for $0 {\leqslant}i < t$. Partition the symbols into two categories: The symbols $\mathcal{S} = \{0,\dots,t-1\}$ in our partial transversal are called *small*, and the remaining symbols $\mathcal{L}=\{t,t+1,\dots,k-1\}$ are called *large*. Build up a sequence of sets in the following way: $$\begin{aligned}
  A_{-1} &= {\varnothing},\\
  A_i &= \left\{r : L(r,t+i) \in A_{i-1} \cup \mathcal{L} \right\}\text{, for }0 {\leqslant}i < n-t.\end{aligned}$$

We claim that $A_i \subseteq \mathcal{S}$ for $0 {\leqslant}i < n-t$.

Assume, on the contrary, that there exists $p \in A_i\cap\mathcal{L}$ and that $i$ is the smallest index where $A_i\cap\mathcal{L}\neq{\varnothing}$. If $L(p,t+i) \in \mathcal{L}$, then we may easily extend our partial transversal since row $p$, column $t+i$ and symbol $L(p,t+i)$ are not in the original partial transversal, which would contradict our assumption of maximality. So let $m_0 = L(p,t+i) \in A_{i-1}$. We now work our way backwards through the $A_i$ in the following manner.

Let $m_j = L(m_{j-1},t+i-j)$ for $0<j{\leqslant}c$ where $c$ is the smallest index such that $m_{c} \in \mathcal{L}$. There exists such a $c{\leqslant}i$, since $L(r,t) \in \mathcal{L}$ for all $r \in A_0$. Note that $m_j\in A_{i-1-j}$ for $j<c$.

We first assume that all $m_i$ are distinct. We can make a partial transversal of length $t+1$ by replacing the entries in the left column of the following table with the entries in the right column. $$\begin{array}{@{}lllc@{\hskip30pt}lll@{}}
  \toprule
  \multicolumn{3}{c}{\text{Original Entry}} && \multicolumn{3}{c}{\text{New Entry}} \\ \midrule
  (m_0,&m_0,&m_0) && (p,&t+i,&m_0) \\
  (m_1,&m_1,&m_1) && (m_0,&t+i-1,&m_1) \\
  (m_2,&m_2,&m_2) && (m_1,&t+i-2,&m_2) \\
  &\vdots& &&&\vdots& \\
  (m_{c-2},&m_{c-2},&m_{c-2}) && (m_{c-3} ,&t+i-c+2,&m_{c-2}) \\
  (m_{c-1},&m_{c-1},&m_{c-1}) && (m_{c-2} ,&t+i-c+1,&m_{c-1}) \\
  &-&     && (m_{c-1} ,&t+i-c  ,&m_{c}) \\
  \bottomrule
\end{array}$$

One may easily check that this forms a partial transversal of length $t+1$, which contradicts the fact that the longest transversal is of length $t$. (The last entry contains a large symbol, so it does not appear on the partial transversal already. The set of rows used in the new partial transversal is $\mathcal{S} \cup \{p\}$. The columns used in the new entries were not used in the original partial transversal.) Now, if $m_a = m_b$ for some $a < b$, then we would be removing some entries multiple times from the partial transversal (for example, $(m_a,m_a,m_a)$ would be removed multiple times). If this is the case, we simply delete the portion of the table corresponding to the rows $(m_{a+1},\dots,m_b)$. By erasing this section, we get a sequence with fewer repetitions, so we may repeatedly remove these repetitions until we arrive at a sequence which has no repetitions. At that stage, we may then do the replacements and arrive at a partial transversal of length $t+1$, which is a contradiction. This completes the proof of our claim that $A_i \subseteq \mathcal{S}$.

We will now show that $|A_i| {\geqslant}(i+1) (m-t-h)$ by induction. First, note that the claim is trivially true for $i=-1$. Now suppose that $i {\geqslant}0$ and $|A_{i-1}| {\geqslant}i(m-t-h)$. Since $A_{i-1} \subseteq
\mathcal{S}$, we may partition $A_i$ into two disjoint sets: $$A_i=\{r:L(r,t+i) \in A_{i-1}\} \cup \{r:L(r,t+i) \in \mathcal{L}\}.$$ Let $\ell=\big|\{r : L(r,t+i)\in A_{i-1}\}\big|$. By the definition of $\ell$, we know that there are at least $|A_{i-1}|-\ell$ small symbols not present in the $(t+i)$-th column. This means that there are at most $t-(|A_{i-1}|-\ell)$ small symbols and at least $m-h-\left(t-|A_{i-1}|+\ell\right)$ large symbols in the column. Thus, by induction, we have $$\begin{aligned}
  |A_i|&{\geqslant}\ell + m-h-(t-|A_{i-1}|+\ell) = |A_{i-1}| + m-t-h{\geqslant}(i+1)(m-t-h).\end{aligned}$$ Since $A_{n-t-1} \subseteq \mathcal{S}$ and $|\mathcal{S}|=t$, we have that $t {\geqslant}(n-t)\dot(m-t-h)$ as desired.

\[cor:n-sqrt-n\] Every Latin array of order $n$ contains a partial transversal of length at least $n+(1-\sqrt{4n+1})/2$.

Simply let $m=n$ and $h=0$ in \[th:n-sqrt-n\] and solve for $t$.

The most often quoted form of \[th:n-sqrt-n\] is the following direct consequence of .

\[cor2:n-sqrt-n\] Every Latin square of order $n$ contains a partial transversal of length at least $n-\sqrt{n}$.

The goal of this paper is to provide, for $k{\leqslant}20$, an improved lower bound on the order $n$ of any Latin array that lacks a partial transversal of length $n-k$. The case $k=1$ is handled in the next section, and the case $2{\leqslant}k{\leqslant}20$ is addressed in the last section. Our results rely heavily on computation. Each computation was verified by at least two independent programs. Preliminary versions of most of our results were given in the PhD theses of the first two authors [@darcy-thesis; @Pula11].

\[s:brualdi\]Near transversals
==============================

In this section we describe our approach to proving that Latin arrays of order $n{\leqslant}11$ have a near transversal. Our method is based on the best known bound for the length of a partial transversal, as given by Shor and Hatami [@HatamiShor08]:

\[th:n-log2\] Every Latin square of order $n$ contains a partial transversal of length at least $n-11.053\log^2n$.

The key idea needed to prove \[th:n-log2\] is the idea of $\#$-swapping. Consider a diagonal, $T$, of weight $w$. Choose two entries from $T$, say $(i_0,j_0,k_0)$ and $(i_1,j_1,k_1)$. If $T\setminus\{(i_0,j_0,k_0),(i_1,j_1,k_1)\}$ still covers $w$ symbols, then we consider the diagonal $$\big(T\setminus\{(i_0,j_0,k_0),(i_1,j_1,k_1)\}\big)\cup\big\{(i_0,j_1,{\bullet}),(i_1,j_0,{\bullet})\big\},$$ where we adopt the convention of using ${\bullet}$ to denote an unknown symbol (possibly a different symbol each time the notation is used). This diagonal is guaranteed to have a weight of $w$, $w+1$ or $w+2$. The act of swapping $\{(i_0,j_0,k_0),(i_1,j_1,k_1)\}$ for $\{(i_0,j_1,{\bullet}),(i_1,j_0,{\bullet})\}$ to obtain a new diagonal is called a $\#$-swap. Note that by repeated use of $\#$-swaps, the weight of the diagonal can never decrease. Thus, if we start with a diagonal of maximum weight, it is impossible to $\#$-swap to a diagonal of larger weight and the set of symbols on each diagonal that we reach by $\#$-swapping will be the same.

Throughout the remainder of the section, we use the symbol [${\times\xspace}$]{}to indicate a cell that must contain a symbol that appears on the original diagonal. For example, if that cell is reachable via a sequence of $\#$-swaps and the original diagonal has maximum weight, then the symbol in the cell must appear somewhere on the original diagonal. In contrast, if a cell is shown as empty, it means that we do not know anything about it.

Here is an example of $\#$-swapping on a diagonal of weight $4 =
  6-2$. If we remove the top left $0$ and $1$ from the diagonal, we still have $4$ symbols left, so we may $\#$-swap on these entries and instead consider the diagonal which contains the two [${\times\xspace}$]{}’s, with the bottom four rows unchanged.

\(A) \[square matrix\][ |\[fill=trans\]|0 &   &   &   &   &  \
  & |\[fill=trans\]|1 &   &   &   &  \
  &   & |\[fill=trans\]|0 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

(2,0) – node\[text width=2.5cm,midway,above,align=center\][\#-swap $(0,0,0)$ and $(1,1,1)$]{} (4,0);

\(A) \[square matrix\][ |\[fill=trans2\]|0 & |\[fill=trans\]|[${\times\xspace}$]{}&   &   &   &  \
|\[fill=trans\]|[${\times\xspace}$]{}& |\[fill=trans2\]|1 &   &   &   &  \
  &   & |\[fill=trans\]|0 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

Note that after performing a $\#$-swap, the two cells that were swapped out will be lightly shaded for further clarity.

The primary purpose of this paper is to describe a proof of a generalisation of for small orders. We try to find near transversals in all Latin arrays rather than just Latin squares. We focus on diagonals of weight $n-2$ and attempt to uncover a new symbol, which would locate a near transversal. The following elementary observation is needed throughout.

\[l:extend\] If every Latin array of order $n$ contains a partial transversal of length $k$, then every Latin array of order $n+1$ contains a partial transversal of length $k$.

Throughout the section, we utilise iteratively. Having shown that all Latin arrays of order $n-1$ contain a near transversal, we will then know that all Latin arrays of order $n$ contain a diagonal of weight at least $n-2$. A diagonal of weight $n-2$ has two essentially different configurations for the duplicated symbols as shown in the following pictures:

\(A) \[square matrix\][ |\[fill=trans\]|0 &   &   &   &   &  \
  & |\[fill=trans\]|0 &   &   &   &  \
  &   & |\[fill=trans\]|1 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-6.north east) – (A-1-1.north west) – (A-6-1.south west); at (\[xshift=0.1cm\]A.south east) [$\ddots$]{};

at (\[yshift=-10pt\]A.south) [Type A]{};

\(A) \[square matrix\][ |\[fill=trans\]|0 &   &   &   &   &  \
  & |\[fill=trans\]|0 &   &   &   &  \
  &   & |\[fill=trans\]|0 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-6.north east) – (A-1-1.north west) – (A-6-1.south west); at (\[xshift=0.1cm\]A.south east) [$\ddots$]{};

at (\[yshift=-10pt\]A.south) [Type B]{};

A diagonal of type A has two symbols which each occur twice on the diagonal, whilst a diagonal of type B has one symbol that occurs thrice on the diagonal. We first start by showing that the existence of a type B diagonal implies the existence of a type A diagonal in maximal cases.

\[lem:weak-trans\] Let $L$ be a Latin array of order $n$ with a diagonal of weight $n-2$ and no diagonal of weight greater than $n-2$. If $L$ has a diagonal of type B, then there exists a diagonal of type A that can be reached by a sequence of $\#$-swaps.

Assume, on the contrary, that no diagonal of type A can be reached. Without loss of generality, the initial diagonal of type B is the main diagonal and the three repeated symbols are in the top 3 rows.

\(A) \[square matrix\][ |\[fill=trans\]|0 &   &   &   &   &  \
  & |\[fill=trans\]|0 &   &   &   &  \
  &   & |\[fill=trans\]|0 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-6.north east) – (A-1-1.north west) – (A-6-1.south west);

at (\[xshift=0.1cm\]A.south east) [$\ddots$]{};

We need to perform $n-2$ $\#$-swaps to arrive at a contradiction. First, we $\#$-swap $(0,0,0)$ and $(2,2,0)$. The symbols in the cells $(0,2)$ and $(2,0)$ must be the same, otherwise this new diagonal would be of type A. Without loss of generality, these cells contain the symbol 1. We now $\#$-swap $(0,2,1)$ and $(3,3,1)$. By a similar argument, the two uncovered cells must contain the same symbols (which is, without loss of generality, 2). We repeat this same argument $n-2$ times in total. On all steps $i$ (except the first one), we $\#$-swap the entries $(0,i,i-1)$ and $(i+1,i+1,i-1)$ and expose the entries $(0,i+1,i)$ and $(i+1,i,i)$. The first three steps are shown in \[fig:steps-weak-trans\].

\(A) \[square matrix\][ |\[fill=trans\]|0 &   &   &   &   &  \
  & |\[fill=trans\]|0 &   &   &   &  \
  &   & |\[fill=trans\]|0 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-6.north east) – (A-1-1.north west) – (A-6-1.south west);

at (\[xshift=0.1cm\]A.south east) [$\ddots$]{};

\(A) \[square matrix\][ |\[fill=trans2\]|0 &   & |\[fill=trans\]|1 &   &   &  \
  & |\[fill=trans\]|0 &   &   &   &  \
|\[fill=trans\]|1 &   & |\[fill=trans2\]|0 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-6.north east) – (A-1-1.north west) – (A-6-1.south west);

at (\[xshift=0.1cm\]A.south east) [$\ddots$]{};

\(A) \[square matrix\][ 0 &   & |\[fill=trans2\]|1 & |\[fill=trans\]|2 &   &  \
  & |\[fill=trans\]|0 &   &   &   &  \
|\[fill=trans\]|1 &   & 0 &   &   &  \
  &   & |\[fill=trans\]|2 & |\[fill=trans2\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-6.north east) – (A-1-1.north west) – (A-6-1.south west);

at (\[xshift=0.1cm\]A.south east) [$\ddots$]{};

\(A) \[square matrix\][ 0 &   & 1 & |\[fill=trans2\]|2 & |\[fill=trans\]|3 &  \
  & |\[fill=trans\]|0 &   &   &   &  \
|\[fill=trans\]|1 &   & 0 &   &   &  \
  &   & |\[fill=trans\]|2 & 1 &   &  \
  &   &  & |\[fill=trans\]|3 & |\[fill=trans2\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-6.north east) – (A-1-1.north west) – (A-6-1.south west);

at (\[xshift=0.1cm\]A.south east) [$\ddots$]{};

However, at step $n-2$, the uncovered symbol must be some symbol that did not appear on the original diagonal. Thus, we have found a heavier diagonal, a contradiction.

Our next result generalises , except that we abandon the condition that we must be able to $\#$-swap to the new diagonal. It also generalises [@CW05 Prop.7], whose proof it mimics. Note that [@CW05 Prop.7] has been generalised in a different direction (namely, to row-Latin arrays of order $n$ containing $n$ symbols) by Aharoni *et al.* [@ABKZ18].

\[lem:partial-to-weak\] Any entry of a Latin array contained in a diagonal of weight $w$ is contained in a diagonal of weight at least $w$ where each symbol appears on the diagonal at most twice.

Let $L$ be a Latin array of order $n$. For convenience, we will assume that the diagonal in question is the main diagonal and let $M$ be the multiset of symbols on the main diagonal. If no symbol appears more than twice in $M$, we are done. Fix some entry $(r,r,{\bullet})$. We will find a diagonal of weight at least $w$ with the desired properties that still contains $(r,r,{\bullet})$.

Select $r_1 \neq r$ such that the symbol $L(r_1,r_1)$ appears in $M$ three or more times. Let $x_i$ be the number of symbols appearing exactly $i$ times in $M$. It follows that $$\sum_{i=0}^n ix_i = n.$$ Thus, $n-(x_1+x_2+\cdots+x_n) = x_2 + 2x_3 + \cdots + (n - 1)x_n > x_2 + x_3 + \cdots + x_n$.

Row $r_1$ contains at least $n-(x_1+x_2+\cdots+x_n)$ symbols that do not appear in $M$ and column $r_1$ contains $(\sum_{i=2}^n
x_i)-1$ symbols that appear more than once in $M$, besides the entry $(r_1, r_1,{\bullet})$. Thus, there are at least two values of $r_2$ such that the symbol $L(r_1, r_2)$ does not appear in $M$ and the symbol $L(r_2, r_1)$ does not appear more than once in $M$. Select $r_2 \neq r$. Observe that $$T = \big(M \setminus\{(r_1,r_1,{\bullet}),(r_2,r_2,{\bullet})\}\big) 
\cup \big\{(r_1,r_2,{\bullet}),(r_2,r_1,{\bullet})\big\}$$ has fewer cells than $M$ that contain symbols that appear more than twice in the diagonal and $(r,r,{\bullet})$ still belongs to $T$. Furthermore, $T$ is of weight at least $w$. By iterating, we will therefore find a diagonal with the desired properties.

Next, we give a simple example of how using $\#$-swaps is useful.

\[lem:ord-6-near\] In any Latin array of order $6$, there exists a diagonal of weight at least $5$.

First, it is quite easy to show that the heaviest diagonal must be at least of weight 4 (for example, use \[th:n-sqrt-n\]). We now assume, on the contrary, that there exists a Latin array that contains a diagonal of weight $4$, but none of weight 5 or 6. Without loss of generality, the original diagonal of length $4$ is along the main diagonal. By \[lem:weak-trans\], we may assume that it takes the form given here.

\(A) \[square matrix\][ |\[fill=trans\]|0 &   &   &   &   &  \
  & |\[fill=trans\]|0 &   &   &   &  \
  &   & |\[fill=trans\]|1 &   &   &  \
  &   &   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

At this point, we are presented with four options for which pair of entries to $\#$-swap (choose either $0$ and either $1$ independently). From this, we can see that we have the following.

\(A) \[square matrix\][ |\[fill=trans\]|0 &   & [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
  & |\[fill=trans\]|0 & [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}& |\[fill=trans\]|1 &   &   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}&   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

As explained above, each [${\times\xspace}$]{}must be one of $0,1,2,3$; otherwise, we would have a heavier diagonal. Consider $\#$-swapping the entries in the first row and the third row. The symbol in the $(2,0)$ cell must be either $2$ or $3$. Without loss of generality, we assume that it is a $2$.

\(A) \[square matrix\][ |\[fill=trans2\]|0 &   & |\[fill=trans\]|[${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
  & |\[fill=trans\]|0 & [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
|\[fill=trans\]|2 & [${\times\xspace}$]{}& |\[fill=trans2\]|1 &   &   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}&   & |\[fill=trans\]|1 &   &  \
  &   &  &   & |\[fill=trans\]|2 &  \
  &   &  & &   & |\[fill=trans\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

Note that we do not know what symbol is in the $(0,2)$ cell, but we do know that it is a duplicate symbol ([*i.e.*]{}it appears at least one more time on the diagonal or at least two more times if it is a $2$). Thus, we are free to $\#$-swap on that entry now. We $\#$-swap that entry and $(4,4,2)$.

\(A) \[square matrix\][ 0 &   & |\[fill=trans2\]|[${\times\xspace}$]{}& [${\times\xspace}$]{}& |\[fill=trans\]|[${\times\xspace}$]{}&  \
  & |\[fill=trans\]|0 & [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
|\[fill=trans\]|2 & [${\times\xspace}$]{}& 1 &   &   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}&   & |\[fill=trans\]|1 &   &  \
  &   & |\[fill=trans\]|[${\times\xspace}$]{}&   & |\[fill=trans2\]|2 &  \
  &   &   & &   & |\[fill=trans\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

The symbol in the $(4,2)$ cell must be either $0$ or $3$ and the symbol in the $(0,4)$ cell is a duplicate (as described above), and so may be used immediately. At this point, we consider both cases for the $(4,2)$ cell separately. In either case, we $\#$-swap the entry in the top row with the appropriate duplicated symbol.

\(A) \[square matrix\][ 0 & |\[fill=trans\]|[${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& |\[fill=trans2\]|[${\times\xspace}$]{}&  \
  & |\[fill=trans2\]|0 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& |\[fill=trans\]|[${\times\xspace}$]{}&  \
|\[fill=trans\]|2 & [${\times\xspace}$]{}& 1 &   &   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}&   & |\[fill=trans\]|1 &   &  \
  &   & |\[fill=trans\]|0 &   & 2 &  \
  &   &   & &   & |\[fill=trans\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

\(A) \[square matrix\][ 0 &   & [${\times\xspace}$]{}& [${\times\xspace}$]{}& |\[fill=trans2\]|[${\times\xspace}$]{}& |\[fill=trans\]|[${\times\xspace}$]{}\
  & |\[fill=trans\]|0 & [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
|\[fill=trans\]|2 & [${\times\xspace}$]{}& 1 &   &   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}&   & |\[fill=trans\]|1 &   &  \
  &   & |\[fill=trans\]|3 &   & 2 &  \
  &   &   & & |\[fill=trans\]|[${\times\xspace}$]{}& |\[fill=trans2\]|3\
]{}; (A-1-1.north west) rectangle (A-6-6.south east);

In either case, the top row now has five entries whose symbol must come from the set $\{0,1,2,3\}$, which is impossible in a Latin array. The result follows.

Hatami and Shor [@HatamiShor08] used this same idea to show \[lem:ord-6-near\]. However, in their description, they did not leave all of the symbols in the top row as unknown ([${\times\xspace}$]{}). Instead, they did extra case analysis to determine what those symbols could be. By leaving the top row as unknown symbols, there is the potential for less branching in the algorithm. Moreover, by continually using the top row to $\#$-swap on, there are only two choices of pairs of entries to $\#$-swap (but one of these choices undoes the last change and reverts to the previous diagonal).

We describe two algorithms whose goal it is to show that there is a near transversal in all Latin arrays of order $n$. describes the basic algorithm to show that all Latin arrays of order $n$ contain a near transversal. This algorithm formalises the method used in the proof of \[lem:ord-6-near\]. This algorithm is then refined in \[alg:hash2\], which works for larger orders than \[alg:hash1\] does.

It is important to note that in both algorithms below, all variables are considered local variables, so changing the value of a parameter does not affect its value outside of that specific instance.

**Input** $L$ is a partial Latin array with some otherwise empty cells marked with ${\times\xspace}$\
**Input** $\sigma$ is a permutation defining a diagonal of weight $n-2$ in $L$\
**Input** $d$ is the depth of the search\
**Input** $r$ is the row we just hashed on\
**Output** <span style="font-variant:small-caps;">True</span> if every Latin array that is a completion of the input has a near transversal.\
**Output** <span style="font-variant:small-caps;">False</span> if the computation is inconclusive.

\[algline:false1\]

  $S \gets L(r,\sigma_r)$ $R \gets $ $\sigma_R = S$, $R > 0$ $R \neq r$

swap$(\sigma_0,\sigma_R)$   $k \gets $ largest symbol in $L$ that appears multiple times\
\
$L(R,\sigma_R) \gets s$

is sufficient to show that all Latin arrays of order $n {\leqslant}7$ contain a near transversal (this result was obtained by an independent calculation in [@BHWWW18]). However, for $n = 8$, \[alg:hash1\] fails to show the desired result as it returns False for \[fig:fail-alg1\].

\(A) \[square matrix\][ 0 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
  & 0 &   &   & 1 & 2 &   &  \
2 &   & 1 & 3 &   &   &   &  \
3 & 2 &   & 1 & 0 &   &   &  \
  & 3 & 0 &   & 2 &   &   &  \
1 &   &   & 0 &   & 3 &   &  \
  &   &   &   &   &   & 4 &  \
  &   &   &   &   &   &   & 5\
]{}; (A-1-1.north west) rectangle (A-8-8.south east);

A total of 14 partial Latin arrays fail \[alg:hash1\] for $n=8$. For $n=9$, one may expect more squares to fail \[alg:hash1\], but interestingly, those 14 squares (with one extra row and column added) are the only squares to fail \[alg:hash1\]. For $n=10$, a total of 82140 squares fail \[alg:hash1\].

Thus, a more refined approach is needed to find near transversals in larger orders. The first observation is that after we have cycled back on ourselves and returned False on line \[algline:false1\] of \[alg:hash1\], we may now choose another row to $\#$-swap on, rather than the first one. Recall that by only using $\#$-swaps on the top row, we are only utilising two of the possible $\#$-swaps available (there are 4 possible if the diagonal is of type A and 3 if it is of type B). In fact, one need not use the main diagonal at all as our starting point (though, in our searches, we always centre around the main diagonal). In \[alg:hash2\], we first $\#$-swap along the top row. Once we cycle around, we then $\#$-swap along the second row, then the third, then the fourth. In \[alg:hash1\], we arbitrarily selected row 3 to be the initial value for $r$. In \[alg:hash2\], when we are $\#$-swapping on rows 0,1,2 and 3, we use the rows 3,2,1 and 0, respectively for the initial value of the “row we just $\#$-swapped on”. It was convenient, but far from essential, to know that $r_0+r_1=3$.

There are two heuristics that can be added to the search that significantly improve its performance when utilised together. (However, there is a minor drawback to using them, which we will discuss in .) The first heuristic is to search for diagonals of weight $n-2$ that may not be reachable via $\#$-swaps. If such a diagonal covers all rows except $r_0$ and $r_1$ and all columns except $c_0$ and $c_1$, then we know that each of the cells $(r_0,c_0), (r_0,c_1), (r_1,c_0)$ and $(r_1,c_1)$ must also contain symbols from $\{0,1,\dots,n-3\}$, or else we would have a near transversal. Thus, if those cells are empty, we may fill them with an [${\times\xspace}$]{}. In practice, every time that we fill a cell with a specific symbol (not an [${\times\xspace}$]{}), we only search for diagonals that go through that cell. The second heuristic is to choose some [${\times\xspace}$]{}in the square and decide what that symbol should be by exhaustively trying each one. We define the *liberties* of a cell to be the number of symbols that could be placed into the cell without violating the Latin property. In practice, we choose an [${\times\xspace}$]{}that has the fewest liberties to limit the branching that our search does. These heuristics are combined in \[alg:hash2\].

**Input** $L$ is a partial Latin array with some otherwise empty cells marked with ${\times\xspace}$\
**Input** $\sigma$ is a permutation defining a diagonal of weight $n-2$\
**Input** $d$ is the depth of the search with the current $r_0$\
**Input** $r_0$ is the row we are mainly $\#$-swapping on (this was the top row in \[alg:hash1\])\
**Input** $r_1$ is the other row that we just $\#$-swapped on\
**Output** <span style="font-variant:small-caps;">True</span> if every Latin array that is a completion of the input has a near transversal.\
**Output** <span style="font-variant:small-caps;">False</span> if inconclusive.

\[algline:loopback2\] \[algline:false2\]

 

$(r,c) \gets $ cell such that $L(r,c) = {\times\xspace}$.\
\

  $S \gets L(r_1,\sigma_{r_1})$ $R \gets $ $\sigma_R = S$, $R \neq r_0$ $R \neq r_1$

swap$(\sigma_{r_0},\sigma_R)$

 

 

$k \gets $ largest symbol in $L$ that appears multiple times $L' \gets L$

$L(r,c) \gets s$ $\{R_1,R_2,C_1,C_2\} \gets$ the two rows and two columns missing from $T$ Fill in cells $(R_1,C_1), (R_1,C_2), (R_2,C_1), (R_2,C_2)$ with [${\times\xspace}$]{}if empty $L \gets L'$

is good enough to show the following result. Both implementations of the algorithm reached Line 5 the same number of times (namely 53 times for $n=10$ and $105\,287$ times for $n=11$ with $r_0=0$ in all cases) providing some corroboration of each other.

\[th:near-trans-11\] Every Latin array of order $n {\leqslant}11$ contains a near transversal.

The cases where $n < 4$ are easy to see (they also follow from \[th:n-sqrt-n\]). We iteratively use and \[alg:hash2\] for $n=4,\dots,11$.

In the search of $n = 11$, every \#-swap included one of the first two rows (that is, $r_0 \in \{0,1\}$ in \[alg:hash2\]). The search for $n {\leqslant}10$ can be completed in a matter of minutes, while a few hours is needed for $n=11$. Based on this progression, we initially believed $n = 12$ to be possible. However, after running our program for several months with several different pruning heuristics on a small grid, we did not think that the program would finish in a reasonable amount of time. Due to the recursive nature of the algorithm, it is difficult to accurately determine what percentage of the search space was covered over those months. Needless to say, all cases that we searched did not provide a counterexample to .

If one wishes to use \[alg:hash2\] to find near transversals in Latin squares (rather than in all Latin arrays), then we would recommend extra heuristics be employed. For example, the partial Latin array in \[fig:loop-back-sqr\] is one of many squares that loops back on \[algline:loopback2\] of \[alg:hash2\] with $r_0=0$. The search continues with $r_0 = 1$, however, no further search is needed if we are only concerned with Latin squares. There are only two symbols which are not on the original diagonal (9 and 10), but there are not enough empty cells left to place them into. In particular, at least $2(n-2)-4$ cells in the top $(n-2) \times (n-2)$ submatrix must be empty in order to fit in the two missing symbols.

\(A) \[square matrix\][ 0 & 6 & [${\times\xspace}$]{}& 5 & 3 & [${\times\xspace}$]{}& 2 & 4 & 1 &   &  \
[${\times\xspace}$]{}& 0 & 3 & [${\times\xspace}$]{}& 1 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
2 & [${\times\xspace}$]{}& 1 & 4 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& 0 & 3 &   &  \
6 & 2 & [${\times\xspace}$]{}& 1 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& 5 &   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}& 0 & 3 & 2 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& 6 & 4 &   &  \
[${\times\xspace}$]{}& 1 & 5 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& 3 & 6 & [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
3 & [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& 5 & [${\times\xspace}$]{}& 4 & [${\times\xspace}$]{}& [${\times\xspace}$]{}&   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& 2 & 1 & 5 & 0 &   &  \
[${\times\xspace}$]{}& [${\times\xspace}$]{}& [${\times\xspace}$]{}& 2 & [${\times\xspace}$]{}& 5 & 0 & [${\times\xspace}$]{}& 6 &   &  \
  &   &   &   &   &   &   &   &   & 7 &  \
  &   &   &   &   &   &   &   &   &   & 8\
]{}; (A-1-1.north west) rectangle (A-11-11.south east);

The fact that all Latin arrays, and not just Latin squares, have near transversals is an encouraging sign for . It is plausible that an even stronger result holds:

\[conj:general-brualdi\] Every Latin array contains a near transversal.

This conjecture is implied by . Of course, the fact that our arrays are Latin seems to be a very important factor in the potential truth of either conjecture. The idea used in \[th:stein-wrong\] relies heavily on clumping all $n$ of each symbol into a small submatrix. The idea cannot be easily changed to accommodate only one of each symbol per row or column. was not optimised in [@PS19]. It would be interesting to know the smallest value of $n$ where an equi-$n$-square exists that does not contain a near transversal.

\[s:nearnear\]Long partial transversals
=======================================

In this final section, we improve the lower bounds on the length of the longest partial tranversal that Latin arrays of all orders $n<1449$ are known to possess. In the proof of \[th:n-log2\] by Shor and Hatami [@HatamiShor08], one of the key ingredients was sets of diagonals with the same weight that were connected by a sequence of $\#$-swaps. A sequence of integers $n_k$ was discussed in detail. To connect those to our results here, $n_2$ is defined as the smallest order such that a diagonal of weight $n-2$ cannot be $\#$-swapped to uncover a new symbol. Note that the heuristics employed in \[alg:hash2\] mean that we cannot use the results from \[th:near-trans-11\] to show that $n_2 {\geqslant}12$. However, we verified that $n_2 {\geqslant}11$ utilising a similar idea to \[alg:hash1,alg:hash2\].

Upon first glance, the $n-11.053\log^2n$ bound shown by Shor and Hatami [@HatamiShor08] is weaker than the $n-\sqrt{n}$ bound for small values of $n$. In fact, for $n {\leqslant}7\,731\,462$, it is better to use the $n-\sqrt{n}$ bound. However, the groundwork laid out in the asymptotic proof in [@HatamiShor08] can be used in a concrete way to show significantly better bounds for lower orders. The key sequence, $n_k$, is a bound on the size that a square must have before being able to \#-swap from a diagonal of weight $n-k$ to a heavier one. In particular, any Latin array of order $n < n_k$ contains a diagonal with weight greater than $n-k$.

The following lemma is taken from [@HatamiShor08], except the first inequality has been strengthened as explained above.

\[lem:shor-eq\] $$\label{eq:shor1} n_2 {\geqslant}11,$$ $$\label{eq:shor2} n_k {\geqslant}n_{k-1} + 2k \quad \text{ for } k > 2 \text { and }$$ $$\label{eq:shor3} (n_k-n_j)(2n_j+n_{k-1}-2n_k+2k-j) {\leqslant}n_j(n_j-n_{j-1}-2j) \quad \text{ for } 3 {\leqslant}j < k.$$

Shor and Hatami used \[eq:shor3\] to show that $k {\leqslant}11.053
\log^2n_k$. While this seems worse than \[th:n-sqrt-n\] for small values, simple induction using \[eq:shor1,eq:shor2\] shows that $n_k {\geqslant}k^2+k+5$, giving a better bound than \[th:n-sqrt-n\] for all $n$. For small values, the value of $11.053\log^2 n$ is far from the truth.

Searching for a single sequence that satisfies inequalities \[eq:shor1,eq:shor2,eq:shor3\] is quite simple. In fact, for any sequence $[n_2, \dots, n_\ell]$ that satisfies \[eq:shor1,eq:shor2,eq:shor3\], you may extend it by setting $n_{\ell+1} = 2n_\ell + 2(\ell+1)$ and it will still satisfy \[eq:shor1,eq:shor2,eq:shor3\]. However, the true interest lies in the smallest value that $n_k$ can achieve for each $k$. Unfortunately, a naive search is not feasible for determining this value for even modest values of $k$, so heuristics are needed to trim the search space. We start by noting that in any minimal sequence, we may assume that $n_2 = 11$ since if $[n_2, n_3, \dots , n_k]$ satisfies \[eq:shor1,eq:shor2,eq:shor3\], then $[11, n_3, \dots, n_k]$ also satisfies \[eq:shor1,eq:shor2,eq:shor3\]. Unfortunately, this greedy nature does not generalise to the remaining parts of the sequence. In order to minimise $n_k$, we may need to use non-optimal values for $n_3, \dots, n_{k-1}$. For example, $n_4 = 28$ is attainable. However, to achieve $n_5=41$, we must use $n_4=31$.

We are attempting to find the smallest value that $n_k$ may obtain. The following heuristic proved very useful in computations. Suppose that we already have a current candidate for the smallest value of $n_k$, say $\kappa$. We say that a pair $(x,y)$ is *viable* if there exists a sequence $[{\tilde n}_x = y, {\tilde n}_{x+1}, \dots, {\tilde n}_k]$ that satisfies \[eq:shor1,eq:shor2,eq:shor3\] and ${\tilde n}_k < \kappa$. Note that \[eq:shor3\] need only be satisfied for $x < j < k$. Thus, in any further computation, we should only use viable pairs of $(x,y)$.

To determine the smallest value that $n_k$ can take, we construct sequences that both satisfy \[eq:shor1,eq:shor2,eq:shor3\] and only contain viable pairs. Each time we find a sequence that has a smaller value for $n_k$, we recompute which pairs of $(i,j)$ are viable. Note that a pair that is marked as not viable will never be marked as viable for a smaller value of $n_k$. shows the smallest values that $n_k$ can take and satisfy \[lem:shor-eq\].

  $k$   One sequence $[n_2, \dots, n_k]$ that minimises $n_k$                               
  ----- ----------------------------------------------------------------------------------- --
  2     $[11]$                                                                              
  3     $[11,17]$                                                                           
  4     $[11,17,28]$                                                                        
  5     $[11,17,31,41]$                                                                     
  6     $[11,17,28,46,58]$                                                                  
  7     $[11,17,28,42,64,78]$                                                               
  8     $[11,17,28,42,63,90,107]$                                                           
  9     $[11,17,28,46,58,91,122,140]$                                                       
  10    $[11,17,28,42,64,78,122,157,177]$                                                   
  11    $[11,17,28,42,63,90,107,165,204,226]$                                               
  12    $[11,17,28,46,58,91,122,140,216,259,283]$                                           
  13    $[11,17,28,42,64,78,122,157,177,272,320,346]$                                       
  14    $[11,17,28,42,64,78,122,157,177,272,356,408,436]$                                   
  15    $[11,17,28,42,63,90,107,165,204,226,346,439,495,525]$                               
  16    $[11,17,28,46,58,91,122,140,216,259,283,432,534,594,626]$                           
  17    $[11,17,28,42,64,78,122,157,177,272,320,346,527,638,702,736]$                       
  18    $[11,17,28,42,64,78,122,157,177,272,356,408,436,662,783,851,887]$                   
  19    $[11,17,28,42,63,90,107,165,204,226,346,439,495,525,796,933,1005,1043]$             
  20    $[11,17,28,46,58,91,122,140,216,259,283,432,534,594,626,948,1110,1192,1234]$        
  21    $[11,17,28,42,64,78,122,157,177,272,320,346,527,638,702,736,1114,1304,1400,1449]$   

  : \[tab:n\_k\]Smallest values of $n_k$ that satisfy \[lem:shor-eq\] for $2 {\leqslant}k {\leqslant}21$ and one possible sequence of $[n_2,\dots,n_k]$ achieving the claimed value.

can be used to show explicit bounds on the length of a partial transversal in a Latin square. For example, \[tab:n\_k\] shows that $n_{21} {\geqslant}1449$. Thus, any Latin array of order $n<1449$ has a partial transversal of length at least $n-20$. By comparison, only implies that any Latin array of order $n<21^2+21=462$ has a partial transversal of length at least $n-20$.

= =

[99]{} \[1\][`#1`]{} \[2\]\[\][[\#2](#2)]{}

R. Aharoni and E. Berger, Rainbow matchings in $r$-partite $r$-graphs, *Electron. J. Combin.* [**16(1)**]{} (2009), R119.

, [E. Berger]{}, [D. Kotlar]{} and [R. Ziv]{}, Degree conditions for matchability in 3-partite hypergraphs, *J. Graph Theory* [**87**]{} (2018), 61–71.

, [D. Kotlar]{} and [R. Ziv]{}, Rainbow sets in the intersection of two matroids, *J. Combin. Theory Ser. B*, **118** (2016), 129–136.

S. Akbari and A. Alireza, Transversals and multicolored matchings, *J. Combin. Des.* [**12**]{} (2004), [325–332]{}.

J. Barát and I.M. Wanless, Rainbow matchings and transversals, *Australas. J. Combin.* [**59**]{}, (2014) 211–217.

, *Transversal this, transversal that*, Ph.D. thesis, Monash University (2018).

D. Best, T. Marbach, R.J. Stones and I.M. Wanless, Covers and partial transversals of Latin squares, *Des. Codes Cryptogr.* [**87**]{} (2019), 1109–1136.

D. Best, K. Hendrey, I.M. Wanless, T.E. Wilson and D.R. Wood, Transversals in Latin arrays with many distinct symbols, *J. Combin. Des.* [**26**]{} (2018), 84–96.

, [A. de Vries]{} and [R.M.A. Wieringa]{}, A lower bound for the length of partial transversals in a Latin square, *Nieuw Archief Voor Wiskunde*, **26** (1978), 330.

and [I.M. Wanless]{}, Latin squares with no transversals, *Electron. J. Combin.*, **24(2)** (2017), \#P2.45.

P.J. Cameron and I.M. Wanless, Covering radius for sets of permutations, *Discrete Math.* [**293**]{} (2005) 91–109.

J. Dénes and A.D. Keedwell, *Latin squares and their applications*, Akadémiai Kiadó, Budapest, 1974.

, Maximal sets of Latin squares and partial transversals, *J. Statist. Plann. Inference*, **1** (1977), 143–149.

, Transversals in row-Latin rectangles, *J. Combin. Theory Ser. A*, **84** (1998), 181–195.

P. Erdős, D.R. Hickerson, D.A. Norton and S.K. Stein, Unsolved problems: Has every Latin square of order $n$ a partial Latin transversal of size $n-1$? *Amer. Math. Monthly* [**95**]{} (1988), 428–430.

A.B. Evans, Maximal partial transversals in a class of Latin squares *Australas. J. Combin.* [**73**]{} (2019), 179–199.

A.B. Evans, A. Mammoliti and I.M. Wanless, Latin squares with maximal partial transversals of many lengths, submitted.

P. Gao, R. Ramadurai, I.M. Wanless and N.C. Wormald, Full rainbow matchings in graphs and hypergraphs, arXiv preprint.

L. Goddyn and K. Halasz, All group-based Latin squares possess near transversals, arXiv:1905.07071.

and [P.W. Shor]{}, A lower bound for the length of a partial transversal in a Latin square, *J. Combin. Theory Ser. A*, **115** (2008), 1103–1113.

, A lower bound for the order of a partial transversal in a Latin square, *J. Combin. Theory*, **7** (1969), 94–95.

B.D. McKay and I.M. Wanless, On the number of Latin squares, *Ann. Comb.* [**9**]{} (2005), 335–344.

R.Montgomery, A. Pokrovskiy and B. Sudakov, Decompositions into spanning rainbow structures, arXiv:1805.07564.

G. Perarnau and O. Serra, Rainbow perfect matchings in complete bipartite graphs: existence and counting, *Combin. Probab. Comput.* [**22**]{} (2013), 783–799.

and [B. Sudakov]{}, A counterexample to Stein’s equi-$n$-square conjecture, *Proc. Amer. Math. Soc.* [**147**]{} (2019), 2281–2287.

, *Approximate transversals of Latin squares*, Ph.D. thesis, University of Denver (2011).

, Transversals of Latin squares and their generalizations, *Pacific J. Math.*, **59** (1975), 567–575.

, *On self-orthogonal Latin squares and partial transversals of Latin squares*, Ph.D. thesis, Ohio State University (1978).

I.M. Wanless, “Transversals in Latin squares: a survey”, in R. Chapman (ed.), *Surveys in Combinatorics 2011*, London Math. Soc. Lecture Notes [**392**]{}, Cambridge University Press, 2011, pp403–437.

, An $n\times n$ Latin square has a transversal with at least $n-\surd n$ distinct symbols. *J. Combin. Theory Ser. A*, **24** (1978), 235–237.

[^1]: Research supported by Endeavour Postgraduate Scholarship and NSERC CGS-D. email: `darcy.best.89@gmail.com`

[^2]: `kylepula@gmail.com`

[^3]: Research supported by ARC grant DP150100506. email: `ian.wanless@monash.edu`
