Abstract:Completing partial Latin squares is NP-complete. Ryser characterized precisely when an $r\times s$ Latin rectangle can be completed to an $n\times n$ Latin square. We extend this theorem to a broader setting. Let $M$ be an $n\times n$ array whose top-left $r\times s$ subarray is filled with symbols from $\{1,2,\dots,k\}$, where $1\leq k\leq n^2$. We determine necessary and sufficient conditions under which the remaining cells of $M$ can be filled so that each symbol $\ell\in\{1,2,\dots,k\}$ appears exactly $\rho_\ell$ times in total, while the numbers of occurrences of each symbol in any two rows and in any two columns differ by at most one.
Equivalently, our result characterizes when a partial edge-coloring of $K_{r,s}$ can be extended to an edge-coloring of $K_{n,n}$ in which each color class is spanning and almost regular, with prescribed color-class sizes. In this sense, our theorem generalizes Baranyai's construction of almost-regular colorings of complete uniform multipartite hypergraphs, restricted to the bipartite case.
Our theorem unifies and generalizes several classical results. When $s=k=\rho_1=\cdots=\rho_k=n$, it reduces to Hall's theorem, and when $k=\rho_1=\cdots=\rho_k=n$, it yields Ryser's completion theorem for Latin rectangles. Additional special cases recover results of Goldwasser, Hilton, Hoffman, and Özkan, as well as a theorem of Bahmanian. Thus, our work may be viewed as a common generalization of these completion theorems and Baranyai's theorem.
From: Anna Yu [view email]
[v1]
Wed, 24 Jun 2026 19:22:19 UTC (18 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。