Premium
Cropper's question and Cruse's theorem about partial Latin squares
Author(s) -
Goldwasser J.,
Hilton A. J. W.,
Patterson D.
Publication year - 2011
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20273
Subject(s) - mathematics , latin square , counterexample , generalization , combinatorics , square (algebra) , inequality , mathematical analysis , geometry , rumen , chemistry , food science , fermentation
In 1974 Cruse gave necessary and sufficient conditions for an r × s partial latin square P on symbols σ 1 ,σ 2 ,…,σ t , which may have some unfilled cells, to be completable to an n × n latin square on symbols σ 1 ,σ 2 ,…,σ n , subject to the condition that the unfilled cells of P must be filled with symbols chosen from {σ t + 1 ,σ t + 2 ,…,σ n }. These conditions consisted of r + s + t + 1 inequalities. Hall's condition applied to partial latin squares is a necessary condition for their completion, and is a generalization of, and in the spirit of Hall's Condition for a system of distinct representatives. Cropper asked whether Hall's Condition might also be sufficient for the completion of partial latin squares, but we give here a counterexample to Cropper's speculation. We also show that the r + s + t + 1 inequalities of Cruse's Theorem may be replaced by just four inequalities, two of which are Hall inequalities for P (i.e. two of the inequalities which constitute Hall's Condition for P ), and the other two are Hall inequalities for the conjugates of P . © 2011 Wiley Periodicals, Inc. J Combin Designs 19:268‐279, 2011