Another proof of Cruse's theorem and a new necessary condition for completion of partial Latin squares (Part 3.)

Abstract

A partial Latin square of order n can be represented by a 3-dimensional chess-board of size n x n x n with at most n^2 non-attacking rooks. Based on this representation, we give proofs of the theorems of M. Hall, Ryser and Cruse on the completion of partial Latin squares that share a common device, the cover sheet: in each case the cover sheet is extended to a (0,1)-matrix with constant line sums and decomposed into permutation matrices by Konig's theorem. With the help of this proof, we extend the scope of Cruse's theorem to compact bricks, which appear to be independent of their environment. Without losing any completion you can replace a dot by a rook if the dot must become a rook, or you can eliminate the dots that are known not to become rooks. Therefore, we introduce primary and secondary extension procedures that are repeated as many times as possible. If the procedures do not decide whether a PLSC can be completed or not, a new necessary condition for completion can be formulated for the dot structure of the resulting PLSC, the BUG condition.

27 pages. v2: unified proof of the theorems of Hall, Ryser and Cruse via the cover sheet; extension of Cruse's theorem to compact bricks; a lower bound of 7 on the odd girth of a BUG. Corrected citations, notation clash resolved, figures redrawn, revised abstract