问题
1-因子(完美匹配):K2n 的 n 条互不相交边覆盖全部顶点;1-因子分解:把全部边分成 2n−1 个 1-因子。分解称为完美的(P1F),若任何两个 1-因子之并是一个哈密顿圈(2n 条边的 «单环»)。Kotzig 1964 年猜想:对每个 n,K2n 都有完美 1-因子分解。已证到数百阶(含全部 «2n−1 为素数» 的构造、若干素数幂族);它是 «把组合设计翻译成群论陪集分解» 的样板问题,与 Room 方(47 号)、循环差集(15–16 号)交织。
主要概念
并环结构与 starter
两个 1-因子之并是 2-正则图=不相交偶圈之并;«完美» ⟺ 永远只有一个圈。构造 P1F 的标准引擎是 starter:在阿贝尔群 G(|G|=2n−1 奇)中取 «覆盖差» 的对集 {xi,yi}(差 ±(xi−yi) 取遍 G∖{0}),加 «无穷点» 后按 «a ↦ a+g» 平移生成全部 1-因子。G = 𝔽p 的 «图式 starter»(x,−x 对)给出 Kp+1 的 P1F——命题 1 给完整证明。组合侧的 «陪集翻译»:P1F 等价于 «有序群作用» 下的循环赛表,其 «任何两轮的并为单环» 是 «差集性质» 的循环赛版本(与 15 号的 «自相关恒零» 平行)。
主要命题与证明
命题 1(K_{p+1} 的 P1F,p 奇素数;完整证明) 2n = p+1(p 奇素数)时 K2n 有完美 1-因子分解。
证明 顶点集 {∞} ∪ 𝔽p。对每个 a ∈ 𝔽p 定义 1-因子 Fa = {{∞,a}} ∪ {{a+x, a−x} : x ∈ 𝔽p*/(±)}——每对 {a+x,a−x} 的中点为 a,p−1 个非零元配成 (p−1)/2 对,加上 {∞,a} 共 (p+1)/2 = n 条边、覆盖全部顶点。边不相交性:{u,v}(u,v∈𝔽p)属 Fa ⟺ a=(u+v)/2 唯一;{∞,a} 型边每 a 恰一次——故 {Fa} 是分解。完美性:取 a≠c,H = Fa∪Fc 是 2-正则图;考察其 «交替行走»:从任意 y ∈ 𝔽p 出发,Fa 把 y 配到 2a−y,Fc 把它配到 2c−y。交替行走两步的净位移:2(c−a),是 𝔽p 的非零常量(2(c−a) ≠ 0)。于是从 y 出发的交替轨道遍历 y + m·2(c−a)(m ∈ ℤ)——由 p 素数、2(c−a) ≠ 0,轨道遍历整个 𝔽p(p 个元素),途中与 ∞ 相连的 «⟨∞, 场元⟩ 边» 恰被经过,故轨道也含 ∞:H 的连通分量为单个 p+1 长圈——哈密顿。□
命题 2(Kotzig 结构定理,1964;陈述) P1F 中存在 «强构形»(若干因子之并出现 «短圈»)时,其余因子被逐级确定——Kotzig 用这类 «构形传播» 论证建立了小阶 P1F 的唯一性与不存在性结果。结构定理是 «唯一性方向» 的主要工具,也是 «完美性如何自我强化» 的机制展示。
说明 «传播» 的直观:一个短圈局部地 «锁定» 相邻因子的边选择,锁定沿因子链扩散;当扩散覆盖全图时分解唯一。完整叙述见 Kotzig 原始系列。□
命题 3(已证的阶谱;陈述) P1F(K2n) 已对以下族证得:2n−1 为奇素数(命题 1);若干素数幂族(𝔽q 上 «图式 starter» 的推广,含 q ≡ 3 (mod 4) 的完整族);数百个具体阶的计算机构造。一般 n 完全开。
说明 构造引擎的统一观察:P1F 的 «完美性» 等价于 «每对 1-因子的交替行走生成元遍历整个群»——把 «群要生成» 与 «群要小而纯» 的张力留给一般 n(复合群会 «分裂» 轨道)。□
进展与文献
Kotzig 1964 的奠基系列;«Starters» 的标准文献(Dinitz–Stinson 的综述);Room 方侧(47 号)与扫描设计的工程文献。开放核心:Kotzig 猜想本体;P1F 的计数与唯一性(«小阶唯一» 之后如何系统化);与循环差集、Room 方的 «谱系合并»——三者的判据地图有望共享引擎。