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.
From: Béla Jónás [view email]
[v1]
Wed, 17 Aug 2022 17:14:48 UTC (1,199 KB)
[v2]
Sun, 9 Aug 2026 05:22:01 UTC (1,201 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。