拉丁矩形的失衡度必须多大？三种方法逼近最小失衡
How Unbalanced Must a Latin Rectangle Be?
AI 导读
一篇 arXiv 论文从构造、精确计算和渐近分析三方面研究 k×n 拉丁矩形的最小失衡度。模拟退火在 8≤n≤13 的 51 个非平方值中改进 33 个，最高提升 39.4%；分支定界证明 3×9 矩形最小失衡为 56，并证明最小失衡对固定 k 为 Θ(n³)。所有结果由 Lean 4 内核验证。
正文 · 原文
Abstract:We view a $k\times n$ Latin rectangle as $n$ points in the grid $[n]^k$. Each symbol gives one point, whose coordinates are the columns it occupies. The rectangle is balanced when these points are pairwise equidistant in the $\ell_1$ metric. Its imbalance measures the distance from this ideal. We study the minimum imbalance from three sides. Constructively, we use a simulated annealing that moves symbols within rows and only penalises column clashes. Against the reference table of Voboril et al. (2025), it improves 33 of the 51 non-square values for $8\le n\le 13$, by up to 39.4%, and matches the rest. A cheap invariant, the row group, certifies that none of the 33 new rectangles is isotopic to rows of a group table, so the earlier column-swapping local search cannot reach any of them. Exactly, a computer-assisted branch and bound proves that the minimum imbalance of a $3\times 9$ rectangle is $56$. Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity $I=2\sum(d-t)^+$, reduces the search tree by a factor of $2.4$ to $3.3$ on the instances with $k\ge3$ that we solve. Asymptotically, the minimum imbalance is $\Theta(n^3)$ for every fixed $k$. A pigeonhole argument gives a lower constant of order $k\,4^{-k}$, and random rectangles give an upper constant of order $\sqrt k$. For $k=2$, the limit of $\min I/n^3$ exists, a permuton attains it, and it lies between $4/375$ and $0.1196$. Perfect balance is an $\ell_1$-equilateral problem, so it forces $k=\Omega(n/\log n)$ rows. For $2\times n$ rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for $14\le n\le 20$. Finally, the Lean 4 kernel checks every rectangle reported in this paper against a 74-line specification that imports only Lean's core library. We also prove the pigeonhole lower bound in Lean with Mathlib.
| Subjects: | Discrete Mathematics (cs.DM); Artificial Intelligence (cs.AI); Combinatorics (math.CO) |
| MSC classes: | 05B15 (Primary) 90C27, 68V15 (Secondary) |
| Cite as: | arXiv:2611.06003 [cs.DM] |
| (or arXiv:2611.06003v1 [cs.DM] for this version) | |
| https://doi.org/10.48550/arXiv.2611.06003 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zhengyu Li [view email]
[v1]
Wed, 4 Nov 2026 05:52:48 UTC (131 KB)
来源：arXiv cs.AI · arxiv.org