Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture

技术摘要：萨比杜西（Sabidussi）兼容性猜想的证明

问题陈述
本文在有限连通多重图的语境下探讨了萨比杜西的兼容性猜想。具体而言，考虑一个欧拉多重图 $G$（其中每个顶点的度均为偶数），且其最小度 $\delta(G) \geq 4$。给定一个遍历每条边且仅一次的闭迹 $T$（即欧拉回路），问题在于：是否可以将 $G$ 的边划分为若干个回路（连通的 2-正则子图），使得没有任何一个回路包含 $T$ 中连续出现的两条边。

在转移系统的语言中，一个欧拉回路在每个顶点处诱导了一组半边的配对。回路分解是“兼容”的，如果没有任何回路将被指定为该回路转移的半边进行配对。该猜想断言，在给定的度约束下，这样的兼容分解总是存在的。

方法论
证明过程通过将图论问题归约为涉及循环词（cyclic words）的组合问题，随后利用 $\mathbb{F}_2$ 域上的奇偶性论证进行代数构造。

1. 归约为循环词：
   作者定义了一个循环词 $w = (v_0, v_1, \dots, v_{m-1})$，代表欧拉回路 $T$ 访问的顶点序列。回路的边对应于这些字母之间的“间隙”。问题被重新表述为：为这些间隙进行来自 $\mathbb{F}_2^2$（一种 4-着色）的着色，使得：

   • 相邻的间隙（对应于回路中连续的边）获得不同的颜色。
   • 对于图中的每个顶点 $v$，分配给与 $v$ 的出现相关的间隙的颜色必须满足奇偶条件：每种颜色在间隙入射中出现的次数均为偶数。

2. 代数框架：
   证明的核心依赖于第 3 节中建立的两个引理：

   • 引理 3.1（四色奇偶性）： 一个元素族中每个元素出现的次数均为偶数，当且仅当它们的线性和为零，且它们的二次和（通过特定的双线性形式 $q(x) = x_1x_2$ 定义）也为零。
   • 引理 3.2（三状态平衡）： 一个全局选择原理。对于有限集 $U$ 和三元素集 $\Sigma$，如果函数 $\beta$ 满足特定的对称性和零和条件，则满足系统局部约束的赋值数量为奇数（因此非零）。

3. 着色构造：
   证明通过以下步骤构造所需的间隙着色：

   • 为循环词中的每个字母 $a$ 定义“局部模式” $\Delta_{a,t}$，它们为 $a$ 的出现分配 $\mathbb{F}_2^2$ 中的非零值，使得它们的和为零。
   • 基于不同字母在词中的出现顺序，定义字母间的交互项 $\beta_{ab}$。
   • 应用引理 3.2 来为每个字母 $a$ 选择一个特定的状态 $t_a \in \Omega$（其中 $\Omega = \mathbb{F}_2^2 \setminus \{0\}$）。这种选择确保了交互约束消失。
   • 利用这些选择来定义序列 $y_i$（间隙颜色之间的差异），并通过积分恢复间隙颜色 $x_i$。
   • 通过证明每个顶点的颜色类之和及二次形式之和均消失，从而验证所得着色满足每个顶点的偶度条件，此处调用了引理 3.1。

主要贡献与结果

• 定理 1.1： 本文证明了对于任何最小度至少为 4 的有限欧拉多重图以及任何欧拉回路 $T$，都存在一个着色 $\chi: E(G) \to \mathbb{F}_2^2$，使得 $T$ 中连续的边具有不同的颜色，且每个顶点在每种颜色类中的度数均为偶数。
• 推论 1.2： 作为结果，图 $G$ 拥有一个与 $T$ 诱导的转移系统兼容的回路分解。
• 对圈双覆盖（Cycle Double Covers）的改进： 文中指出，在存在支配回路（dominating circuit）的情况下，该结果意味着三次图 $H$ 拥有一个包含该回路的 5-圈双覆盖。这改进了近期证明的针对具有支配回路的图的 8-圈双覆盖定理（文中归功于 OpenAI）。
• 形式化： 该证明已在 Lean 定理证明器中完成了完全形式化。

意义与主张
本文声称提供了萨比杜西兼容性猜想的完整证明，该问题自 Kotzig (1968) 和 Fleischner (1980) 的工作以来一直受到研究。虽然之前的研究已在平面图、$K_5$-极小图或特定度约束下确立了该猜想，但本证明直接处理了除最小度要求外不限制图类的所有偶度情况。

作者明确指出，该证明是对原猜想的强化，提供了具有特定结构属性的 4-着色，而不仅仅是分解。这项工作被呈现为对该猜想的决定性解决，依赖于循环词组合学与有限域上奇偶性引理的新颖结合。

关于作者身份的说明
文中明确指出，证明完全归功于 “GPT 5.6 Pro”，而撰写工作由 “GPT 5.6 Sol” 协助完成。人类作者 Nikolay Ulyanov 承认了 AI 在生成数学论证和阐述过程中的作用。