问题
平面的染色数 χ(ℝ²):给平面每点染色使 «距离恰为 1 的点对不同色» 的最少颜色数。范围 [5, 7]:下界 5 = de Grey 2018 的 1581 顶点单位距离图(终结 1950 年以来 «≤4» 的共识);上界 7 = 标准六边形蜂窝染色。问题:5、6、7 哪个是真的?
主要概念
单位距离图与有限 witness
χ(ℝ²) = sup{χ(G) : G 有限单位距离图}(德布魯因–爱多士紧致性:无限染色数可有限化)。全部已知下界构造都是 «有限拼装»:莫泽纺锤(4 色,1961)→ de Grey 的 «Moser 拼装»(把 «4-色冲突» 的两个纺锤 «钉» 在一起产生 5-色需求)。
六边形蜂窝与上界机器
7 色上界:正六边形蜂窝(边长略小于 1/2),每蜂窝一色,7 色按 «蜂窝图 K₂ 的色数» 分配—— «平移对称» 的廉价上界。改进到 6 需要 «非对称» 染色方案,所有尝试(Pritikin 型 «概率染色»、测度论方案)都卡在 «5 色局部冲突» 的定量墙。
主要命题与证明
命题 1(莫泽纺锤 4 色,完整构造) 存在 7 顶点单位距离图 χ = 4(莫泽 1961)。
证明(构造+染色论证) 两个 «菱形»(对角线 1 的正三角形对)沿公共轴 «共享两端点»:顶点集 = 菱形两端 A, B + 上菱形两中腰点 + 下菱形两腰点 + «共享线段 AB 的 «外» 侧两点»——7 个顶点中 A, B 距离 1(相邻),每个 «腰» 同时与 A 或 B 相邻,且 «同侧两腰» 距离 1。染色论证:假设 3 色。A, B 异色(设红、蓝)。上腰两点与 A 相邻且互邻——它们是 «非红» 互邻对 → 需蓝+第三色(设绿);下腰同理 → 蓝+绿。中间 «交叉腰对» 距离 1 但都已是蓝、绿——冲突。故 χ ≥ 4;4 染色显然。□
命题 2(de Grey 下界 5,完整骨架) 存在 1581 顶点单位距离图 χ = 5(de Grey 2018;后由 Heule 的 SAT 验证与 Exoo–Ismailescu 的压缩至 501–553 顶点)。
骨架 ①«Moser 拼装»:取 «两个 «4-色需求» 的纺锤»,让它们 «共享» 一个 «1-距离对»,迫使 «4-染色» 在共享对上 «冲突»——构造 «无 4-染色» 的 «H» 图;②«膨胀»:把 H 中每条边 «替换为 «Moser 纺锤的 «非 4-色» 传导»»——«边 → 传导图» 的 «笛卡尔乘积» 技巧放大 «色需求»;③SAT 验证:最终图的 «无 4-染色» 由可满足性求解器证明(Heule 的 drat 证明被独立核验)。顶点数从 1581 → 553(Exoo–Ismailescu 手工压缩)→ 509/501(后续)。□
命题 3(上界 7 与 «6 的墙»,完整陈述) χ(ℝ²) ≤ 7:六边形蜂窝直径 d < 1/√3·(1/2)·2 = «蜂窝内径 < 1» 的参数化——取蜂窝 «小圆内径» = 1/2 略小、蜂窝间距 ≥ 1,7 色循环分配。6 的尝试:Pritikin 的 «概率 6-染色» 需要 «某尺寸蜂窝无 5-色单位距离图»——被 de Grey 下界 5 恰好 «吃掉»:«5-色需求图» 可以塞进 «任意» 蜂窝方案,6-染色不能比 7-染色 «更省» 除非 «新几何»。□
进展与文献
Hadwiger 1945/Nelson 1950(问题起源的两个平行版本);莫泽兄弟 1961;de Grey(Nature 2018)与 arXiv 《graph coloring》社区(Polymath 式协作压缩);Soifer《The Mathematical Coloring Book》的百科全书式综述。开放核心:6 还是 7(连 «是否存在 6-染色» 的 «非构造性» 存在证明都没有);χ(ℝ³) ∈ [6, 15]、一般 χ(ℝⁿ) ~ Θ(n²) 的常数(Raigorodskii 机器)。