九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

里泽猜想:奇数阶拉丁方的完整横截

《组合设计中的 50 个公开问题》 · 问题 19 专题综述

题面每个奇数阶拉丁方都有一条完整横截(每行每列每符号各取一次)吗?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

拉丁方:n×n 表,每行每列都是 n 个符号的排列。横截:取 n 个格,行、列、符号各不重复——「每行每列每符号各取一次」。Ryser 1967 年猜想:每个奇数阶拉丁方都有完整横截。偶数阶已有反例(2 阶循环表即无;4 阶有多个)。奇数阶连 «有 n−O(log n) 长的部分横截» 都已是重量级结果(Keevash–Pokrovskiy–Sudakov–Yepremyan 等),最后一步未跨。它与偶数阶的 n−1 猜想(Brualdi–Stein,20 号)构成拉丁方理论的双子星。

主要概念

匹配视角

横截 = 三部超图的完美匹配:顶点为行集、列集、符号集,格 (i,j;符号) 是超边。一般三部超图的完美匹配是 NP 难的,拉丁结构的 «每行每列恰 n 条边» 的正则性给出希望。偶数阶反例的机制是 «奇偶性»:命题 2 用 «符号总和» 论证给出循环表偶数阶无横截的完整证明——这也解释了为何猜想只对奇数阶提出。

部分横截的攻坚机器

当前最好的下界(任意阶)约为 n−O(log²n/log log n)(Keevash–Pokrovskii–Sudakov–Yepremyan 2020 的 «交换贪心+吸收»);更早的里程碑:Woolbright 与 Brouwer 等的 n−√n(1978)。«最后一步»(从 n−缓慢项 到 n)看似只差一个无穷小量,却是 «匹配结构的刚性» 障碍——与 20 号的 Polymath 攻坚经验一致。

主要命题与证明

命题 1(奇数阶循环表的完整横截,完整证明) 奇数 n 的循环群加法表(L(i,j) = i+j mod n)有完整横截。

证明 取格 (i, 2i mod n)(i = 0,…,n−1):i ↦ 2i 是 ℤn 的自同构(2 与 n 互素,因 n 奇)⟹ 列互不重复、行遍历全部;符号 i+2i = 3i 遍历 ℤn(3 与 n 互素,同因 n 奇)⟹ 符号互不重复。故对角线族 {(i,2i)} 是完整横截。□

命题 2(偶数阶循环表无横截,完整证明) 偶数 n 的循环群加法表没有完整横截。

证明 反设横截 {(i, π(i))} 存在。横截取遍全部符号 ⟹ Σi (i+π(i)) ≡ Σs∈ℤn s (mod n)。左端 = Σi + Σπ(i) = 2·Σi i = n(n−1) ≡ 0 (mod n)。右端 = n(n−1)/2 (mod n):n 偶时 ≡ n/2 (mod n) ≠ 0。矛盾。□

命题 3(部分横截的当前纪录;陈述) Woolbright / Brouwer–de Vries–Wieringa(1978):每个拉丁方有 n−√n 长部分横截;Hatami–Shor(2008)改进到 n−O(log²n);Keevash–Pokrovskii–Sudakov–Yepremyan(2020)到 n−O(log²n/log log n)。奇数阶的完整横截(Ryser 本体)未证;奇数阶的 «超越一般阶» 的专属手段尚无。

说明 攻坚机器是 «交换贪心»:维持一个大匹配、允许 «链式交换»(沿交替路改进)并保留 «吸收结构» 应对最后残余——与设计吸收法(02 号)同源,但在三部超图的 «严格正则» 环境里交换自由度更受限。□

进展与文献

Ryser 1967;Brualdi–Ryser《Combinatorial Matrix Theory》的拉丁方章;Woolbright 1978;Hatami–Shor 2008;Keevash–Pokrovskii–Sudakov–Yepremyan 的部分横截改进(2020)。开放核心:奇数阶完整横截;横截计数(偶数阶的 «横截个数奇偶» 与 21 号 Alon–Tarsi 猜想的纠缠);三部正则超图的一般匹配定理的极限。

← 返回问题 19