Covers and partial transversals of Latin squares

Abstract

We define a cover of a Latin square to be a set of entries that includes at least one representative of each row, column and symbol. A cover is minimal if it does not contain any smaller cover. A partial transversal is a set of entries that includes at most one representative of each row, column and symbol. A partial transversal is maximal if it is not contained in any larger partial transversal. We explore the relationship between covers and partial transversals. We prove the following: (1) The minimum size of a cover in a Latin square of order $n$ is $n+a$ if and only if the maximum size of a partial transversal is either $n-2a$ or $n-2a+1$. (2) A minimal cover in a Latin square of order $n$ has size at most ${\mu }_n=3(n+1/2-\sqrt{n+1/4})$. (3) There are infinitely many orders $n$ for which there exists a Latin square having a minimal cover of every size from $n$ to ${\mu }_n$. (4) Every Latin square of order $n$ has a minimal cover of a size which is asymptotically equal to ${\mu }_n$. (5) If $1\le k\le n/2$ and $n\ge 5$ then there is a Latin square of order $n$ with a maximal partial transversal of size $n-k$. (6) For any $\epsilon >0$, asymptotically almost all Latin squares have no maximal partial transversal of size less than $n-n^{2/3+\epsilon }$.