COVERING WITH LATIN TRANSVERSALS

Given an n x n matrix A = [a(ij], a transversal of A is a set of elements, one from each row and one from each column. A transversal is a latin transversal if no two elements are the same. Erdos and Spencer showed that there always exists a latin transversal in any n x n matrix in which no element appears more than s times, for s less-than-or-equal-to (n - 1)/16. Here we show that, in fact, the elements of the matrix can be partitioned into n disjoint latin transversals, provided n is a power of 2 and no element appears more than epsilon n times for some fixed epsilon > 0. The assumption that n is a power of 2 can be weakened, but at the moment we are unable to prove the theorem for all values of n.