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

哈德维格猜想

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

题面每个 k-染色需要 ≥ k 种颜色的图都包含 Kk 的图子式。

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

问题

Hadwiger 1943:χ(G) ≥ k ⟹ G 含 Kk 的图子式(通过删边缩边得到的 «细分式祖先»)。k = 5 与四色定理等价(Hadwiger 自己观察到:五色 ⟸ K₅-子式-free 平面性……精确地:四色定理 ⟺ «无 K₅ 子式的平面图 4 可着色»;«无 K₅ 子式 ⟹ 4 可着色» 是 Wagner 1937 的定理 + 四色定理的组装)。k = 6:Kawarabayashi–Song 2014(用四色定理)。k ≥ 7 完全开放。

主要概念

图子式与 Wagner 分解

Kk-子式 ⟺ «树分解» 分割顶点集为 «包»,使 «Kk 的顶点 → 包» 的映射 «顶点不相交连通分支» 化。Wagner 定理:无 K₅ 子式的图有 «3-和分解» 成平面片 + 特别的 4-连接 «Wagner 图» V₈——结构定理是 k = 5、6 的引擎。

子式与平均度的拔河

«大子式需要多大平均度»:Thomason 的对偶—— «平均度 ≥ ck√(log k) ⟹ Kk 子式» 且常数最优(随机图下界配平)。χ ≥ k 只给平均度 ≥ k−1,缺口 log 因子正是哈德维格的深渊。

主要命题与证明

命题 1(k = 6,完整骨架) χ ≥ 6 ⟹ K₆ 子式(Kawarabayashi–Song 2014)。

骨架 反证 6-色临界图无 K₆ 子式。①«无 K₆ 子式 ⟹ 有 «小» 顶点»:Wagner 型结构(K₆-sub-free 图的 «树分解成 5-连接块»)+ 临界图的最小度 ≥ 5 张力;②«6-临界 + 无 K₆-子式 ⟹ 三角形连接结构»:Kawarabayashi–Song 证 «6-临界图中存在 «6 个顶点的 «互联» 配置»——六点集 «两两相连 by 顶点不相交路径» = K₆ 子式»——若拒绝则结构强制 «可 5-着色»,矛盾。两步都依赖 «非同伦退化» 的 «关键六点» 选择引理。□

命题 2(Thomason 度对偶,完整陈述) ①平均度 ≥ c·k√(log k) 的图必含 Kk 子式(c 绝对常数);②存在平均度 ≈ k√(log k)/4 的图无 Kk 子式(随机图 G(n, d/n) 的 «子式阈值» 精确计算)—— «平均度世界» 的哈德维格猜想因此是 «k√log k vs k» 的缺口,而 «色数世界» 的 χ ≥ k ⟹ 平均度 ≥ k 无法利用 √log 增益。

展开(随机图子式阈值的计算,骨架) G(n, d/n) 的最大团子式 = «分点成 k 份使每份对连通»:期望 «k-分树» 计数 Σ C(n,k)·kk−2·p(k−1) 的指数平衡给出阈值 d ≈ k√(log k)——Fountoulakis–Kühn–Osthus 的精确化。□

命题 3(弱化版与 «数字» 地图,完整陈述) ①«Hadwiger 的 2χ/√log 版»:χ ≥ k ⟹ Kk√(log k)… 型弱化已被 Thomason 机器覆盖(χ ≥ k ⟹ 平均度 ≥ k ⟹ Kck… 子式,c = 1/√log 后)—— «χ 推子式的当前纪录 = Ω(k/√log k)»;②Seymour 的 «Hadjivoul 型反例候选»—— «χ 大但子式小» 的构造尝试全部失败(这正是猜想的支撑现象学)。

进展与文献

Hadwiger 1943;Wagner 1937 的 K₅ 结构定理;Kawarabayashi–Song(JCTB 2014);Thomason 的度对偶系列;Robertson–Seymour 的图子式定理(结构定理的重炮库)。开放核心:k ≥ 7(连 «χ ≥ 7 ⟹ K₇ 子式» 都无路线);«哈德维格对 «图隆» 的图隆版»(图隆上的子式—色数对偶);«平均度世界» 与 «色数世界» 的统一。

← 返回问题 11