罗盘 / 哈德维格-纳尔逊问题
暗星档案 · 未点亮的星

哈德维格-纳尔逊问题

本条为初评草案(AI 辅助编目):T 阶为三问初评(撬动面 × 停滞度 × 临界性),双评过 σ 门并红蓝复核后才升"已建档"。查不到的字段留空不编。点亮者会进入亮星候选流程,其贡献与星阶按 HCF 独立重评,不从暗星自动继承。

哈德维格-纳尔逊问题 量级 · 潜能待评
给平面染色让任意两个相距恰好1的点颜色不同,最少需要几种颜色
暗星编号DS-0445
R · 风险与文明安全
领域fundamental-science
状态初评草案 · 待双评与红蓝复核
这是什么 · 为什么难

求平面的色数:给平面上每个点染色,使得任意两点若距离恰好为1则颜色不同,最少需要多少种颜色。1950年代已知答案在4到7之间,2018年业余数学家Aubrey de Grey构造出一个色数为5的图,将下界提升到5,但确切答案(5、6还是7)至今未知。攻克将解决一个跨越70年、连接图论与几何组合的经典难题。

卡在哪 · 机制级卡点

上界7和下界5之间的缝隙需要构造出极其复杂的单位距离图(de Grey的图已有上千个顶点,且只能靠计算机验证色数而非人工可读证明),构造更大色数的图或证明7不可再降都极其困难。

谁在攻

独立数学家Aubrey de Grey(现有最佳下界构造者);Polymath16协作项目(在线众包持续优化de Grey图的顶点数与验证)

怎么参与

学习图论中的图染色理论,从Polymath16项目页面读起,了解如何用计算机辅助验证参与这类协作证明