An r x n latin rectangle is an r X n array filled with m symbols, say, such that every cell contains one symbol and every symbol occurs at most once in each row and column.
The purpose of this paper is to prove the following result.
Theorem. Let L = (Li,i) be an r X n array of n-sets with r < $n. Then L contains an r X n Latin rectangle.
This goes some way towards a positive answer to a well-known problem by J. Dinitz, who in 1978 conjectured that the theorem could hold even for r = n in place of r < $2. For background see for instance my paper written in collaboration with Amanda Chetwynd [3] and the references therein, in particular the papers by Bollobas and Harris [2] and Erd&, Rubin and Taylor [4]. Further related problems can be found in the extensive literature on the partial latin squares completion problem (see for instance [l] for some fifty references). Before proving the theorem let us give a couple of definitions and a lemma. For a graph G and subsets A, B of G, we denote by N,(A) the set of neighbours of A in G, by &(A, B) the set of edges between A and B in G and by &(A) the minimum vertex degree in G among vertices from A. If B = B(S, T) is a bipartite graph (with bipartition (S, T)) and A c S then we denote by N:(A) the set of neighbours of A joined to A by at least (SI -6,(S) + 2 edges. An S-matching in B is a set of independent edges which covers all of S, and when p is a natural number then a p-matching is a set of p independent edges. For a matching M we denote by V(M) the set of vertices incident with M. Other unexplained graph theoretical notation should hopefully be standard.
With this terminology we have the following lemma.
Lemma. Let F be a matching in the bipartite graph B = B(S, T) and let A c S be a given set of vertices. Add to B -F an (ISI -(Ng(A)I)-matching M between S and T -N;(A). Then the resulting graph B* has an S-matching.
Proof. Consider a set A c S for which IA I 3 6,(S). Then in particular IA -A I 6