Transversals in Latin arrays with many distinct symbols


Abstract in English

An array is row-Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row-Latin. A transversal in an $ntimes n$ array is a selection of $n$ different symbols from different rows and different columns. We prove that every $n times n$ Latin array containing at least $(2-sqrt{2}) n^2$ distinct symbols has a transversal. Also, every $n times n$ row-Latin array containing at least $frac14(5-sqrt{5})n^2$ distinct symbols has a transversal. Finally, we show by computation that every Latin array of order $7$ has a transversal, and we describe all smaller Latin arrays that have no transversal.

Download