New Classes of Premature Partial Latin Squares
Abstract
A partial (i.e., partially filled) latin square PLS is called premature, if it is not completable to a full latin square (of the same order) but completable to such a latin square after deletion of any of its symbols. The complete knowledge of this kind of PLS would give an answer to the completability problem for latin squares in the following sense: a PLS can be completed if and only if it does not contain a premature PLS as a subsquare. One may also think of a hypergraph whose maximal independent sets are given by the full latin squares of a given order and whose hyperedges are to be described explicitly.
We survey some known examples for a premature PLS and present 3 new classes in particular one obtained from a combination of two well-known types.