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

拓扑哈德维格猜想

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

题面χ-染色需要 ≥ k 色的图包含 Kk 的拓扑子式(细分拷贝)吗?

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

问题

哈德维格猜想( «χ ≥ k ⟹ Kk 子式 »,本册设计/群卷的 « 邻居 »)的细分版:χ ≥ k ⟹ 图含 Kk 的拓扑子式( «细分拷贝 »: «边可拉长为路 »)。已知 k ≤ 5 已证( «k = 6 » 的 « 部分 »—— «平均度 » 型下界的 « 拓扑 » 版有进展); «k ≥ 6 » 一般开放。

主要概念

子式 vs 拓扑子式

«子式 »(minor): «删边缩边 » 得到—— «强 »; «拓扑子式 »(topological minor): «细分 » 得到—— «弱 »( «子式 » 未必 « 拓扑 »)。 «Mader 定理 »: «平均度 ≥ 2t ⟹ « Kt» 拓扑 »—— «平均度 » 侧 « 已证 »; «染色 ⟹ 平均度 »( «χ ≥ k ⟹ « 平均度 ≥ k−1 »)给 « 平凡 » 的 « 桥 »—— «k−1 vs 2k» 的 «指数 » 缺口。

真嵌图理论

«真嵌 »(properly embedded): «面 » 的 «复杂度 » 受控的 «嵌入图 »—— «拓扑子式 » 的 «曲面 » 侧: «真嵌 » 的 «染色 » 与 «拓扑子式 » 的 «曲面 » 版( «Kk 嵌入曲面 » 的 « Euler » 约束)。

主要命题与证明

命题 1(Dirac–Jung 的 k ≤ 5 证域) χ ≥ 5 ⟹ 拓扑 K₅( «Wagner 等价 » 的 « 拓扑 » 版);χ ≥ 4 ⟹ 拓扑 K₄( «初等 »)。

梗概 χ ≥ 5 的 «极小 » 图( «5-临界 »)的 «结构 »: «Dirac » 的 «5-临界 » 分析给 « « K₅ » 或 « 高度 » » 的 «二分 »; «高度 » 侧 « Mader » 机器给 « 拓扑 K₅ »。□

命题 2(平均度型拓扑子式定理,Mader–Bollobás–Thomason) 平均度 ≥ c·k²/log k ⟹ 拓扑 Kk( «c» 的 « 优化 »: «Kühn–Osthus » 型); «染色的桥 »:χ ≥ k ⟹ 平均度 ≥ k−1—— «k²/log » 与 «k» 的 «缺口 »。

进展与文献

Hajós 1961( «原始 » 猜想的 « 细分 » 版曾有反例史: «Hajós 猜想 » 方面: «k ≥ 7 » 有 « 稠密反例 »( «Catlin » 等),故 «拓扑版 » 的 «现状 » 是 «Hajós 的 « 弱化 »»);Mader 1967( «平均度 » 机器);Bollobás–Thomason 1998;Kühn–Osthus 的 «常数 » 优化; «真嵌 » 侧:Dvořák–...。开放核心: «χ ≥ k ⟹ 拓扑 Kk» 对 «k ≥ 6 » 的 «一致 » 真( «Hajós 反例 » 只否 «平均度» 弱版的 «某 » 形式—— «染色 » 版 «未被 » 反例否, «共识 » 微妙); «弱哈德维格 »( « Hadwiger 的 « 弱化 » »)与 «细分侧 » 的 «联合 » 版图。

← 返回问题 49