Covers and partial transverals of Latin squares
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:
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.
A minimal cover in a Latin square of order n has size at most
μn=3(n+1/2-√(n+1/4)).
There are infinitely many orders n for which there exists a
Latin square having a minimal cover of every size from n to μn.
Every Latin square of order n has a minimal cover of a size
which is asymptotically equal to μn.
If 1 ≤ k ≤ n/2 and n≥5 then there is a Latin square of order
n with a maximal partial transversal of size n-k.
For any ε > 0, asymptotically almost all Latin squares have
no maximal partial transversal of size less than n-n2/3+ε.