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

平面奇距离图的染色数

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

题面把平面点对按「距离为奇数」连边(奇距离图)需要多少种颜色?

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

问题

奇距离图:平面的点为顶点,«欧氏距离为奇整数» 的点对连边。染色数 χ_odd:奇圈图(正奇边形,边长 1)给出 ≥ 3;问题问 χ_odd 是否无界(无界性已有证明)以及 «多快» 增长—— «显式下界序列» 的缺失使 «增长速率» 完全未知。

主要概念

度量染色与 «距离族» 图

一般框架:ℝⁿ 的 «距离集 D» 图(D-距离连边)。单位距离(D = {1})是问题 13;奇距离(D = 奇整数)的 «非齐次» 性使 «代数构造»(格点、有限域嵌入)失效—— «无界性» 本身都曾是难题(Arman–Tsaturian 2015 解决)。

无界性的 «谐振» 论证

核心思想:奇距离图的 «大团» 由 «谐振点集»(Furstenberg–Weiss 型 «等距嵌套» 结构)构造—— «二进制分形» 点集使 «距离奇性» 在 «多重尺度» 上强制连边,团指数增长。

主要命题与证明

命题 1(奇圈下界,完整证明) χ_odd ≥ 3,且 3 色精确于 «奇圈»。

证明 正 (2k+1)-边形(外接圆半径 1,边长 2 sin(π/(2k+1)),调整半径使边长为奇数)是奇距离图;奇圈 χ = 3(经典)。□

命题 2(无界性,完整骨架) χ_odd 无界(Arman–Tsaturian 2015;Pach 等独立路线)。

骨架 构造 «团尺寸递增» 的奇距离图:①«格点塔»:取 ℤ² 的 «子格» 使 «奇距离» 对应 «格向量的 «奇» 范数»—— «范数奇 ⟺ 向量 «和的奇偶» 结构» 使 «子格的 «对角» 点集» 成团(团尺寸 ~ 格尺寸);②«嵌入»:任何有限格构型可 «实嵌入» 平面(相似变换保奇偶性:«奇距离» 对 «缩放» 敏感,缩放因子必须 «奇»…… Arman–Tsaturian 的 «嵌入引理»:任何 «整数距离图» 可 «刚性嵌入» ℝ² 使 «距离奇偶» 保持——依赖 «格的 «分解»»);③«团 → 染色数»:团尺寸无界 ⟹ χ 无界。□

命题 3(上界侧与 «增长率» 真空,完整陈述) χ_odd ≤ χ(ℝ²) ≤ 7(奇距离图不是单位距离子图,7 的上界不传导)。实际已知上界:χ_odd ≤ χ(「所有整数距离图」) ≤ ℵ₀ 级—— «可数上界» 是仅有的:平面的 «整数距离图» 染色数 ≤ ℵ₀(每点由 «奇偶格» 染色……精确:把平面按 «二进制 «尾部»» 染—— «无显式有限上界» 是当前格局)。□

进展与文献

Arman–Tsaturian(2015,无界性);Pach–de Zeeuw 等的 «距离图» 综述;Furstenberg–Weiss 的 «谐振» 预备。开放核心:χ_odd 的显式下界序列(连 «χ_odd ≥ 4» 的具体图都没有公开共识—— «4 色奇距离图» 的构造本身是文献缺口);χ_odd 是否有限( «无界但有界于某 f» 的中间地带);一般 «距离集» 图的 «染色 vs 代数维度» 框架(Solymosi 的纲领)。

← 返回问题 14