Hall's theorem and extending partial latinized rectangles

Abstract

We generalize a theorem of M. Hall Jr., that an r x n Latin rectangle on n symbols can be extended to an n x n Latin square on the same n symbols. Let p, n, v(1),v(2),...,v(n) be positive integers such that 1 <= v(i) <= p (1 <= i <= n) and Sigma(n)(i=1) v(i) = p(2). Call an r x p matrix on n Symbols sigma(1), sigma(2),..., sigma(n) an r x p (v(1),v(2),...,v(n))-latinized rectangle if no symbol occurs more than once in any row or column, and if the symbol sigma(i) occurs at most vi times altogether (1 <= i <= n). We give a necessary and sufficient condition for an r x p (v(1), v(2),...,v(n))-latinized rectangle to be extendible to a p x p (v(1),v(2),...,v(n))-latinized square. The condition is a generalization of P. Hall's condition for the existence of a system of distinct representatives, and will be called Hall's (v(1), v(2),..., v(n))-Constrained Condition. We then use our main result to give two further sets of necessary and sufficient conditions. Finally we use our results to show that, given p, n, v(1),v(2),...,v(n) such that 1 <= v(i) <= p, Sigma(n)(i=1) v(i) = p(2), then a p x p (v(1),v(2),...,v(n))-latinized square exists. (C) 2014 Elsevier Inc. All rights reserved.