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

康韦套扣猜想

《图论中的 50 个公开问题》 · 问题 29 专题综述

题面套扣图的边数不超过顶点数吗?

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

问题

康韦定义:图可画在平面上使每条边恰与其他每条边相交一次(端点相邻算相交,故共端点的边 «交于端点»)且端点处不穿过——这样的图叫套扣(thrackle)。猜想(Conway 1969 起):套扣的边数 ≤ 顶点数。悬赏一千美元征证明或反例。

主要概念

约束的代数化

«每对边恰交一次» 在 «交矩阵»(m×m,(i,j) 格 = 边 i,j 是否交)上是 «非对角全一 + 对角约定» 的结构——强约束。奇圈是套扣的最小例(一个奇圈的边两两相邻于端点)—— «两个共点奇圈» 是经典构造模板。

下界构造的极限

所有已知套扣都满足 m ≤ n(最长 «双奇圈» 型构造达到 m = n);无数值反例被找到(穷举到相当规模), «上界到底是否 n» 的高灵敏度体现在:已证上界 1.3984n(Fulek–Tóth 系的当前纪录)距 n 只有 40%,但每一步压缩都极难。

主要命题与证明

命题 1(Cairns–Nikolayevsky 交叉约定,完整证明) 套扣中任何两个偶圈不能 «共边相交»,且任何偶圈与奇圈 «交叉偶数次»。

证明 设 C 是套扣 T 中的圈,e 是 C 外的一条边。e 与 C 的每条边恰交一次;沿 C 行走, «进入/离开» C 的内部区域交替——故 e 与 C 的 «真交叉»(非端点)次数 = |C| − (与 e 共端点的 C 边数)。而 «真交叉» 次数必为偶数(闭合曲线穿越计数),给出 |C| − d(e,C) ≡ 0 (mod 2),其中 d(e,C) ∈ {0,1,2}(e 最多与 C 共两端)。对偶圈 |C| 偶、d ≤ 2:矛盾除非特定结构——推论:偶圈 «孤立»、套扣至多含一个偶圈且偶圈 «悬垂»。□

命题 2(上界纪录线) 套扣边数 ≤ 1.3984n(Fulek–Tóth 2023 前后)。路线: «圈交分析»(命题 1 的奇偶约束)给出 «至多一个偶圈» → 结构二分( «纯奇» 与 «偶悬垂»)→ 每类用 «度 ≤ 常数»(套扣中度 ≤ 3 的深度结果)+ 计数不等式压到常数因子。

进展与文献

Conway 的原始悬赏与其 «Musings on thrackles»;Woodall 1973 的早期上界;Cairns–Nikolayevsky 2000 的 «边界行走» 奇偶机器;Fulek–Tóth–Pach 系的逐次纪录(1.5n → 1.4n → 1.3984n)。开放核心:1n 的最后 40% 需 «全局计数» 突破—— «交矩阵的谱» 或 «拓扑交集定理»(如 Holmsen 型)被试过皆未达标;散在 «最大套扣 » 分类工作(双奇圈是否唯一的极值形)独立成趣。

← 返回问题 29