[CITATION][C] An n× n Latin square has a transversal with at least n− n distinct symbols

DE Woolbright - Journal of Combinatorial Theory, Series A, 1978 - Elsevier
Journal of Combinatorial Theory, Series A, 1978Elsevier
A latin square is an nxn array such that in each row and column each of the integers 1, 2,
3,..., n occurs exactly once. A transuersaz is a collection of n cells, no two of which are in the
same row or column. If T is a transversal then by 1 T 1 is meant the number of distinct
symbols which occur in T. The number 1 T 1 is called the size of the transversal. Koksma [2]
has shown that for all latin squares there is a transversal T such that 1 T 1>(2n+ 1)/3.
Recently Drake [I] has shown 1 T [>(3n)/4 for at least one transversal T. The purpose of this …
A latin square is an nxn array such that in each row and column each of the integers 1, 2, 3,..., n occurs exactly once. A transuersaz is a collection of n cells, no two of which are in the same row or column. If T is a transversal then by 1 T 1 is meant the number of distinct symbols which occur in T. The number 1 T 1 is called the size of the transversal. Koksma [2] has shown that for all latin squares there is a transversal T such that 1 T 1>(2n+ 1)/3. Recently Drake [I] has shown 1 T [>(3n)/4 for at least one transversal T. The purpose of this paper is to substantially improve this lower bound by showing that every n x n latin square has at least one transversal containing at least n-di distinct symbols.
Elsevier