Cropper's question and Cruse's theorem about partial Latin squares
✍ Scribed by J. Goldwasser; A. J. W. Hilton; D. Patterson
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 151 KB
- Volume
- 19
- Category
- Article
- ISSN
- 1063-8539
No coin nor oath required. For personal study only.
✦ Synopsis
In 1974 Cruse gave necessary and suf cient conditions for an r×s partial latin square P on symbols r 1 , r 2 ,...,r t , which may have some unfilled cells, to be completable to an n×n latin square on symbols r 1 , r 2 ,...,r n , subject to the condition that the unfilled cells of P must be lled with symbols chosen from {r t+1 , r t+2 ,...,r 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 suf cient 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.