Planar-Toroidal Decomposition of $K_{12}$

该论文通过理论论证与计算机搜索，证明了完全图$K_{12}$无法分解为一个平面图和一个环面图，并进一步确定了所有使平面图与其补图中的环面子图边数差达到最小的 123 对唯一图结构。

要点

这篇论文讲述了一个关于**“拆积木”**的数学故事，主角是一个由 12 个点组成的超级复杂的网络（在数学上称为 $K_{12}$ 完全图）。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成一场**“拼图挑战”**。

1. 背景：一个巨大的拼图难题

想象一下，你有一个由 12 个朋友组成的聚会，每个人都要和其他 11 个人握手。这总共会产生 66 次握手（边）。
数学家们想把这些握手分成两组：

• 第一组（平面组）： 这些握手必须画在一张普通的纸上，线条不能交叉。这就像在平地上修路，不能有任何立交桥。
• 第二组（环面组）： 剩下的握手必须画在一个甜甜圈（数学上叫“环面”或“环”）上，线条也不能交叉。在甜甜圈上，你可以绕过那个洞，所以有些在纸上会交叉的路，在甜甜圈上可以互不干扰。

问题的核心是： 能不能把这 66 次握手完美地切分成两份，一份能画在纸上，另一份能画在甜甜圈上？

2. 过去的猜想与作者的发现

在 1978 年，两位学者（Anderson 和 White）提出了一个猜想：对于 12 个人的情况，这种完美的“纸 + 甜甜圈”拆分是可能存在的。这就像有人预言：“肯定有一块拼图能刚好填进这个空缺。”

但是，这篇论文的作者（Allan Bickle 和 Russell Campbell）通过严密的逻辑推理加上超级计算机的暴力搜索，得出了一个令人惊讶的结论：
“不，这种完美的拆分不存在。”

这就好比有人告诉你：“肯定有一把钥匙能同时打开这两把锁。”但作者们检查了所有可能的钥匙形状，最后发现：根本不存在这样一把钥匙。

3. 他们是怎么做到的？（两大武器）

作者用了两把“武器”来破解这个难题：

武器一：逻辑推理（像侦探一样排除嫌疑人）

作者首先用数学规则缩小了搜索范围。

• 规则： 一张纸上能画的最多连线数有限（就像一张纸能容纳的马路数量有限），甜甜圈上能画的也有限。
• 推论： 如果要把 12 个人的所有连线分完，那么“纸上的图”必须画得满满当当（达到极限），而“甜甜圈上的图”也必须画得满满当当。
• 排除法： 作者发现，如果某个人的“握手次数”（度数）太高或太低，或者某些特定的连接模式出现，就会导致矛盾。比如，如果某个人在纸上握了 8 次手，那么他在甜甜圈上就只能握 3 次手，这会导致剩下的图形结构变得不可能。通过这些逻辑，他们排除了成千上万种不可能的情况。

武器二：计算机暴力搜索（像大海捞针）

虽然逻辑推理排除了一大半，但剩下的可能性依然很多。于是，作者让计算机上阵了。

• 任务： 计算机列出了所有 7595 种可能的“纸上满铺图”（也就是在 12 个点上，线条不交叉且画得最满的所有画法）。
• 过程： 对于每一种画法，计算机把剩下的连线（补图）拿出来，尝试看看能不能画在甜甜圈上。
  • 如果直接画不行，计算机尝试删掉 1 条线再试。
  • 如果还不行，就删掉 2 条线再试。
• 结果：
  • 删 0 条线（完美拆分）：0 次成功。
  • 删 1 条线：0 次成功。
  • 删 2 条线：成功了 123 次。

4. 最终结论与意义

这篇论文告诉我们：

1. 猜想破灭： 对于 12 个点的完全图，你无法把它完美地拆成“一张纸”和“一个甜甜圈”。
2. 代价： 如果你想让剩下的部分能画在甜甜圈上，你至少得扔掉 2 条线（也就是有 2 次握手无法被归类）。
3. 意外收获： 作者找到了所有 123 种“扔掉 2 条线”后能成功的特殊情况。这就像是在说：“虽然完美的钥匙没有，但我们找到了 123 把‘稍微磨一下’就能用的备用钥匙。”

5. 为什么这很重要？

这就好比在研究网络拓扑或芯片设计。

• 如果我们要设计一个芯片，有些线路必须铺在平面层（平面图），有些可以绕到背面或特殊层（环面图）。
• 这篇论文告诉我们，当节点数量达到 12 个且要求极其紧密连接时，单纯靠“平面 + 环面”是不够的，必须允许有“断点”（删掉几条线）或者增加更多的层。

总结一句话：
作者们用逻辑和计算机证明了，把 12 个人的复杂关系网完美地拆成“平面”和“甜甜圈”两部分是不可能的，必须至少牺牲掉两条连线才能勉强实现。这推翻了 40 多年前的一个猜想，并找到了所有最接近成功的方案。

技术摘要

这是一份关于论文《K12 的平面 - 环面分解》（Planar-Toroidal Decomposition of K12）的详细技术总结，该论文由 Allan Bickle 和 Russell Campbell 撰写，发表于《离散数学与理论计算机科学》（2026 年）。

1. 研究问题 (Problem)

本文的核心问题是解决图论中关于完全图分解的一个长期未决猜想，具体涉及**平面图（Planar Graph）与环面图（Toroidal Graph）**的分解问题。

• 背景定义：
  • 分解（Decomposition）：将图 $G$ 的边集划分为若干非空子图（因子）。
  • 厚度（Thickness）：$\theta(G)$ 是将 $G$ 分解为平面图所需的最少平面图数量。
  • 环面厚度：$\theta_1(G)$ 是将 $G$ 分解为可嵌入环面（Torus）图所需的最少数量。
  • $N(\gamma, \gamma')$：定义为无法将其边集划分为两个分别可嵌入亏格为 $\gamma$ 和 $\gamma'$ 的曲面的完全图的最小阶数。
• 具体目标：
  • 确定 $N(0, 1)$ 的值，即是否存在一个阶数为 12 的完全图 $K_{12}$，可以分解为一个平面图 $G$ 和一个环面图 $\bar{G}$（$G$ 的补图）。
  • 验证 Bickle 和 White (2013) 提出的猜想：对于 $n \ge 11$，$\gamma(G) + \gamma(\bar{G})$ 的下界 $\lfloor \frac{1}{12}(n^2 - 13n + 24) \rfloor$ 是否总是可达。
  • 当 $n=12$ 时，该下界为 1。这意味着如果猜想成立，则 $K_{12}$ 应能分解为一个平面图（亏格 0）和一个环面图（亏格 1）。

2. 方法论 (Methodology)

作者结合了理论推导与大规模计算机搜索两种方法来解决问题。

2.1 理论方法 (Theoretical Approaches)

作者提出了三种理论筛选机制，用于排除不可能存在分解的极大平面图（Maximal Planar Graphs）：

1. 顶点度数分析 (Vertex Degrees)：
   • 利用平面图和环面图的边数限制（$m \le 3n-6$ 和 $m \le 3n$），推导出若 $K_{12}$ 存在分解，则两个因子必须取最大边数。
   • 证明了在 $PT_{12}$（即满足条件的分解对）中，平面图 $G$ 的最小度 $\delta(G)$ 和最大度 $\Delta(G)$ 必须满足特定范围（$3 \le \delta \le 5 \le \Delta \le 8$）。
   • 利用度数序列排除了多种不可能的情况（如 $5^{12}$ 等序列）。
2. 三角形计数 (Counting Triangles)：
   • 利用 Goodman 公式计算 $G$ 和 $\bar{G}$ 中的三角形总数。
   • 由于 $G$ 是极大平面图，其三角形区域数为 $2n-4=20$；若$\bar{G}$是环面三角剖分，其区域数为$2n=24$。
   • 通过计算度数序列对应的三角形总数，排除了那些无法同时满足 $G$ 和 $\bar{G}$ 三角形数量要求的度数序列。
3. 分离集分析 (Separating Sets)：
   • 分析 $G$ 中的分离三角形（Separating Triangle）和分离 4-圈。
   • 证明了如果 $G$ 存在特定的分离结构（如删除后产生特定阶数的子图），则其补图 $\bar{G}$ 将包含不可嵌入环面的子图（如 $K_{3,6}$ 或 $K_{4,4}$ 的特定嵌入导致交叉），从而排除这些情况。

2.2 计算机搜索 (Computer Search)

由于理论方法无法排除所有情况，作者进行了穷举搜索：

• 数据源：使用了 Combinatorial Object Server 中列出的所有 7595 个 12 阶极大平面图（平面三角剖分）。
• 预处理过滤：
  • 首先排除了最大度 $\Delta > 8$ 的图（3476 个）。
  • 排除了存在度数为 8 的顶点且其非邻接点构成独立集等违反引理条件的图。
• 核心搜索策略：
  • 对于剩余的候选平面图 $G$，检查其补图 $\bar{G}$ 是否可嵌入环面。
  • 由于直接嵌入算法复杂且存在错误风险，搜索策略调整为：尝试从 $\bar{G}$ 中移除少量边，看剩余图是否可嵌入环面。
  • 移除 1 条边：耗时约 4 天 8 小时，未发现任何可嵌入环面的情况。
  • 移除 2 条边：耗时约 59 天。发现了一些可嵌入环面的情况，但均需要移除至少 2 条边。
• 工具与实现：
  • 使用了 Campbell 编写的 C/C++ 代码进行嵌入搜索。
  • 利用 Gunnar Brinkmann 的 planedraw 可视化结果。
  • 使用了 Sulanke 的 Surftri 程序生成平面三角剖分作为验证。
  • 所有数据、代码和生成的图像（7595 个平面图及其补图）均开源在 GitHub 仓库中。

3. 关键贡献与结果 (Key Contributions & Results)

1. 否定 $K_{12}$ 的平面 - 环面分解：

   • 通过穷举所有 7595 个 12 阶极大平面图，证明了不存在一个平面图 $G$，使得其补图 $\bar{G}$ 是环面图。
   • 结论：$K_{12}$ 不能分解为一个平面图和一个环面图。

2. 确定 $N(0, 1)$ 的值：

   • 结合已知结果（$K_{11}$ 可以分解为 $C_9 + 2K_1$ 和 $C_9 \cup K_2$），证明了 $N(0, 1) = 12$。即 12 是第一个无法分解为平面和环面图的完全图阶数。

3. 证伪 Bickle/White 猜想：

   • 直接推翻了 Bickle 和 White (2013) 关于 $n \ge 11$ 时 $\gamma(G) + \gamma(\bar{G})$ 下界总是可达的猜想。
   • 对于 $n=12$，下界计算为 1，但实际最小和为 2（因为无法分解为 0+1，只能是 1+1 或更高），因此猜想不成立。

4. 量化边数差距：

   • 证明了如果 $G$ 是 12 阶平面图且 $H \subseteq G$ 是环面图，则 $H$ 的边数至少比 $G$ 少 2 条。
   • 计算机搜索找到了所有 123 对唯一的 $(G, H)$，使得 $H$ 恰好比 $G$ 少 2 条边（即从 $K_{12}$ 的补图中移除 2 条边后可嵌入环面）。

5. 资源开源：

   • 提供了 7595 个 12 阶平面三角剖分的程序化生成图像集合。
   • 公开了搜索算法代码和 123 个满足“移除 2 条边后可嵌入环面”的补图嵌入示例。

4. 意义 (Significance)

• 理论突破：解决了 Anderson 和 White 在 1978 年提出的关于 $N(0, 1)$ 的开放问题，填补了图嵌入理论中的一个重要空白。
• 猜想修正：修正了关于图及其补图亏格和的下界猜想，表明该下界在 $n=12$ 时不可达，为后续研究 $n$ 较大时的行为提供了新的方向。
• 算法与数据贡献：
  • 展示了处理复杂图嵌入问题（特别是环面嵌入，其禁止极小图数量巨大）时，理论筛选与暴力搜索结合的有效性。
  • 生成的 7595 个平面图数据集和 123 个特殊嵌入案例，为未来研究图分解、嵌入算法及拓扑图论提供了宝贵的基准测试数据（Benchmark）。
• 方法论示范：论文展示了如何利用理论引理（如度数限制、分离集性质）大幅缩小搜索空间，从而使得在普通计算资源上完成大规模穷举成为可能。

总结：该论文通过严密的理论推导和详尽的计算机验证，彻底解决了 $K_{12}$ 的平面 - 环面分解问题，证明了其不存在性，并由此修正了相关的图论猜想，同时为社区提供了丰富的计算资源。