The Length of a Partial Transversal

Abstract

A Latin square of order $n$ is an $n\times n$ array of cells containing one of the $n$ elements in $\{1,2,\dots ,n\}$ such that in each row and each column each element appears exactly once. A partial transversal $P$ of a Latin square $L$ is a set of $n$ cells such that no two are in the same row and the same column. The number of distinct elements in $P$ is referred to as the length of $P$, denoted by $|P|$, and the maximum length of a partial transversal in $L$ is denoted by $t(L)$. In this paper, we study the technique used by Shor which shows that $t(L)\ge n–5.53{(\ln )}^2$ and we improve the lower bound slightly by using a more accurate evaluation.