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. In Latin squares, a subsystem and its remote mate together have as many rooks as their capacity, which yields a simple capacity condition for completion, in fact Cruse's necessary condition for characteristic matrices.
We prove a closed-form identity for Cruse's capacity function, from which its smallest values follow directly. The capacity of a non-degenerated remote brick couple is at least n-1, with equality precisely when one edge length is 1 and another is n-1; the second smallest value is n, and we list the couples attaining it. Geometrically the capacity is affine in each variable, and its minimum level set on the cube [1,n-1]^3 consists of the six edges adjacent neither to (1,1,1) nor to (n-1,n-1,n-1).
Andersen and Hilton, and then Andersen, listed the partial Latin squares with n, resp. n+1 filled cells that cannot be completed. Identifying the structures that can be overloaded, we obtain that a PLS coming from a chess-board with at most n+1 rooks is completable exactly if it satisfies the capacity condition. Finally, since the two subsystems of a remote couple are in balance within a layer, we formulate a further necessary condition for the completion of a layer, the balance condition.
From: Béla Jónás [view email]
[v1]
Fri, 12 Aug 2022 08:34:13 UTC (5,614 KB)
[v2]
Sat, 8 Aug 2026 05:16:11 UTC (4,436 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。