2025-11-17T09:40:14.052128

Four plane unit vectors generate a $3$-colorable graph

Eng, Harris, Krebs et al.

We show that given an arbitrary set of four plane unit vectors $v_1, v_2, v_3, v_4$, the Cayley graph generated by $\{\pm v_1, \pm v_2, \pm v_3, \pm v_4\}$ is always $3$-colorable. Indeed, we show that this is a specific case of a much more general result wherein we determine the chromatic number of an arbitrary abelian Cayley graph generated by a set of four elements and their negatives, subject to the constraint that the group of relations between those elements has rank no more than $2$.

academic

Four plane unit vectors generate a 3-colorable graph

基本信息

论文ID: 2511.10813
标题: Four plane unit vectors generate a 3-colorable graph
作者: Katherine Eng, Timothy Harris, Mike Krebs, Mason Meeks, Claudia Maria Schmidt
分类: math.CO (组合数学)
发表时间: 2025年11月13日提交至arXiv
论文链接: https://arxiv.org/abs/2511.10813

摘要

本文证明了对于任意四个平面单位向量 $v_1, v_2, v_3, v_4$ ，由 $\{\pm v_1, \pm v_2, \pm v_3, \pm v_4\}$ 生成的Cayley图总是3-可着色的。进一步地，作者证明这是一个更一般性结果的特例：确定了由四个元素及其负元生成的任意阿贝尔Cayley图的色数，前提是这些元素之间的关系群的秩不超过2。

研究背景与动机

1. 核心问题

本文研究的是经典的平面色数问题（Hadwiger-Nelson问题）的一个变体。原问题询问：需要多少种颜色才能给平面 $\mathbb{R}^2$ 中的每个点着色，使得距离为1的任意两点颜色不同？目前已知 $\chi(\mathbb{R}^2) \in \{5, 6, 7\}$ 。

2. 问题的重要性

理论意义：平面色数问题是组合几何中的经典难题，与图论、几何和拓扑学密切相关
实际应用：单位距离图在无线网络频率分配、晶体结构分析等领域有应用
数学深度：问题涉及Cayley图理论、代数群论和图着色理论的交叉

3. 现有方法的局限性

完整平面色数问题极其困难，至今未能确定精确值
有限单位距离图的色数研究缺乏系统性方法
对于特定生成元个数的Cayley图色数缺乏一般性理论

4. 研究动机

作者提出了新的研究角度：定义 $\chi_{\max}(n)$ 为所有由 $n$ 个平面单位向量 $\{\pm v_1, \ldots, \pm v_n\}$ 生成的Cayley图的最大色数。这个问题更具结构性，便于系统研究。

核心贡献

主要结果（Corollary 1.1）：证明了 $\chi_{\max}(1) = \chi_{\max}(2) = 2$ 且 $\chi_{\max}(3) = \chi_{\max}(4) = 3$
一般性定理（Theorem 1.2）：完全确定了具有 $4 \times 2$ Heuberger矩阵的标准化阿贝尔Cayley图（SACG）的色数，给出了色数为4的充要条件
理论框架：建立了从平面单位向量问题到阿贝尔Cayley图色数的系统联系
方法论贡献：扩展了之前关于小尺寸Heuberger矩阵的结果（ $1 \times r$ , $m \times 1$ , $2 \times 2$ , $3 \times 2$ ）到 $4 \times 2$ 情形
技术工具：开发了modified Hermite Normal Form、pre-modified Hermite Normal Form等矩阵标准形式及相关分析工具

方法详解

任务定义

输入：

四个平面单位向量 $v_1, v_2, v_3, v_4 \in \mathbb{R}^2$ ， $\|v_i\| = 1$
或更一般地：一个 $4 \times 2$ 整数矩阵 $M$ （Heuberger矩阵）

输出：

Cayley图 $\text{Cay}(G, S)$ 的色数 $\chi(X)$ ，其中 $S = \{\pm v_1, \pm v_2, \pm v_3, \pm v_4\}$ ， $G$ 是由 $S$ 生成的 $\mathbb{R}^2$ 的子群

约束：

图无环（no loops）
图非二部图（nonbipartite）
矩阵无零行

核心理论框架

1. Cayley图与Heuberger矩阵

对于阿贝尔群 $G$ 和对称生成集 $S = \{\pm x_1, \ldots, \pm x_m\}$ ：

关系：满足 $a_1x_1 + \cdots + a_mx_m = 0$ 的整数向量 $(a_1, \ldots, a_m)^t$
关系群： $H \subseteq \mathbb{Z}^m$ 是所有关系构成的子群
Heuberger矩阵： $m \times r$ 整数矩阵 $M$ ，其列生成 $H$

2. 标准化阿贝尔Cayley图（SACG）

给定 $m \times r$ 整数矩阵 $M$ ：

令 $H$ 为 $M$ 的列生成的 $\mathbb{Z}^m$ 的子群
令 $G = \mathbb{Z}^m / H$ ， $S = \{H \pm e_1, \ldots, H \pm e_m\}$
记 $M^{\text{SACG}} = \text{Cay}(G, S)$

关键性质：每个连通有限度数阿贝尔Cayley图都同构于某个SACG

主要定理（Theorem 1.2）

设 $M$ 是 $4 \times 2$ 整数矩阵， $X = M^{\text{SACG}}$ 。若 $X$ 非二部图、无环、 $M$ 无零行，则：

$\chi(X) = 4 \Leftrightarrow \exists \text{ 符号置换矩阵 } P \text{ 和幺模矩阵 } U \text{ 使得 } PMU = \begin{pmatrix} 1 & a \\ 1 & b \\ 1 & c \\ 0 & 1 \end{pmatrix}$

其中 $a, b, c \in \mathbb{Z}$ 且 $3 \mid a + b + c$ 。否则 $\chi(X) = 3$ 。

证明策略

阶段1：从单位向量到矩阵（Section 3）

对于四个平面单位向量，构造Heuberger矩阵 $M$ ，按列数 $r$ 分情况：

Case $r = 1$ ：由Tomato Cage Theorem， $\chi(X) \leq 3$

Case $r = 2$ ：这是核心情形

若有零行：可约化为3个向量的情形，利用 $\chi_{\max}(2) = 2$
若无零行且非二部图：应用Theorem 1.2
若Theorem 1.2的特殊形式成立，证明必有 $v_1 + v_2 + v_3 = 0$ （等边三角形配置）
此时 $v_4$ 必是格点中的单位向量，即 $v_4 \in \{\pm v_1, \pm v_2, \pm v_3\}$
用三角格着色公式： $\alpha v_1 + \beta v_2 + \gamma v_3 \mapsto \alpha + \beta + \gamma \pmod{3}$

Case $r = 3, 4$ ：图有限或可约化

阶段2：证明Theorem 1.2（Sections 4-6）

工具1：Modified Hermite Normal Form 对于 $3 \times 2$ 矩阵，定义标准形式满足：

$y_{11} > 0$ ， $y_{12} = 0$
$y_{11} \equiv 0 \pmod{3}$ 或 $y_{22} \equiv y_{32} \pmod{3}$
其他技术条件

Theorem 4.6给出了此标准形式下色数的完整分类（6种例外情形色数为4）

工具2：Pre-modified Hermite Normal Form 对于 $4 \times 2$ 矩阵，定义三种"桶"（buckets）：

Case 1：合并第1、2行得到modified Hermite Normal Form
Case 2：合并第2、3行得到modified Hermite Normal Form
Case 3：合并第3、4行得到modified Hermite Normal Form

工具3：关键引理

4×2 three-divisible row lemma（Lemma 5.1）：若某行被3整除，则 $\chi(Y) \leq 3$
Tri-Triangle Lemma（Lemma 4.9）：特定形式矩阵的色数判定
图同态：行合并操作产生同态 $M^{\text{SACG}} \xrightarrow{\circledcirc} M'^{\text{SACG}}$

证明流程：

将 $4 \times 2$ 矩阵归约到三种Case之一
对每个Case，合并两行得到 $3 \times 2$ 矩阵 $M_Z$
若 $\chi(Y) \geq 4$ ，则由同态性质 $\chi(Z) \geq 4$
应用Theorem 4.6， $M_Z$ 必属于6种例外情形之一
通过案例分析，证明只有Theorem 1.2中的特殊形式才能使 $\chi(Y) = 4$

技术创新点

矩阵标准形式理论：创造性地将图着色问题转化为矩阵标准形式问题
分层归约策略： $4 \times 2 \to 3 \times 2 \to$ 已知结果，利用图同态保持色数上界
模运算约束：巧妙利用模3同余关系排除大量情形
二次型理论：在复杂子情形中使用二次型约化理论求解Diophantine方程
几何直观：将代数条件翻译为几何配置（如等边三角形格点）

实验设置

注：本文是纯理论数学论文，不包含传统意义上的实验。所有结果均为数学证明。

验证方法

理论证明：通过严格的数学推理
案例验证：对特定矩阵形式进行详尽的案例分析
引用先前工作：依赖三篇硕士论文4,6,7完成部分子情形的证明

证明覆盖范围

Case 1（合并行1、2）：完全由4证明
Case 2（合并行2、3）：部分由7证明，本文补充剩余情形
Case 3（合并行3、4）：部分由6证明，本文补充剩余情形

详细分析的案例（Section 6）

作者展示了**Case 3 + 例外情形(v)**的完整证明过程：

矩阵形式： $M_Y = \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ y_{31} & y_{32} \\ y_{41} & 2-y_{32} \end{pmatrix} \xrightarrow{\circledcirc} M_Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \pm 3k & 2 \end{pmatrix}$

证明步骤包括：

模3分析确定变量同余类
构造新同态到矩阵 $M_U$
将 $M_U$ 归约到modified Hermite Normal Form
识别色数为4的子情形
构造第二个同态 $M_V$ 进行交叉验证
求解产生的Diophantine方程组

实验结果

主要结果

定理验证：Corollary 1.1完全确立：

$\chi_{\max}(1) = 2$ ：双向无限路径图
$\chi_{\max}(2) = 2$ ：无限网格图或路径图
$\chi_{\max}(3) = 3$ ：三角格（下界）+ Theorem 1.2推导（上界）
$\chi_{\max}(4) = 3$ ：同上

关键观察：

$n \geq 5$ 时 $\chi_{\max}(n)$ 未知
$\chi_{\max}(7) \geq 4$ ：Moser's spindle提供4-色图的例子
由de Bruijn-Erdős定理（假设选择公理），对充分大的 $n$ ， $\chi(\mathbb{R}^2) = \chi_{\max}(n)$

理论发现

临界维度现象：从3个向量到4个向量，色数没有增加，显示某种饱和效应
代数-几何对应：色数为4的充要条件对应于特定的代数形式（ $3 \mid a+b+c$ ），在几何上对应于三角格配置
秩的作用：关系群秩 $\leq 2$ 的约束是关键，更高秩情形复杂度显著增加
对称性保持：符号置换和幺模变换保持图的色数（同构类）

案例分析

例：等边三角形配置 当 $v_1 = (1, 0)$ ， $v_2 = (-1/2, \sqrt{3}/2)$ ， $v_3 = (-1/2, -\sqrt{3}/2)$ 时：

满足 $v_1 + v_2 + v_3 = 0$
生成三角格 $G$
着色方案： $\alpha v_1 + \beta v_2 + \gamma v_3 \mapsto \alpha + \beta + \gamma \pmod{3}$
这给出了 $\chi_{\max}(3) = 3$ 的紧下界

例：Moser's spindle

7个单位向量定义的图
已知是4-色的
证明 $\chi_{\max}(7) \geq 4$

结论与讨论

主要结论

核心定理：任意四个平面单位向量生成的Cayley图是3-可着色的
精确刻画：完全确定了 $4 \times 2$ Heuberger矩阵对应SACG的色数，给出色数为4的充要条件
计算结果： $\chi_{\max}(n) = 2$ 当 $n \in \{1, 2\}$ ； $\chi_{\max}(n) = 3$ 当 $n \in \{3, 4\}$
方法贡献：矩阵标准形式方法为研究更高维情形提供了工具

局限性

未解决情形： $n \geq 5$ 时 $\chi_{\max}(n)$ 仍然未知
技术复杂度：证明涉及大量案例分析，部分依赖于三篇硕士论文的详细工作
计算困难：从单位向量到Heuberger矩阵的构造可能不唯一，需要选择合适的表示
选择公理依赖：与平面色数的联系需要假设选择公理（AC）
直接证明缺失：作者承认可能存在更直接的证明Corollary 1.1的方法

未来方向

扩展到更多向量：
- 确定 $\chi_{\max}(5)$ , $\chi_{\max}(6)$ , $\chi_{\max}(7)$ 等
- 开发处理更大 $m \times r$ 矩阵的技术
简化证明：
- 寻找更直接的几何证明
- 减少案例分析的数量
算法实现：
- 开发自动判定给定矩阵色数的算法
- 计算机辅助验证
推广到更高维：
- $\mathbb{R}^d$ 中的单位距离图问题
- 非阿贝尔Cayley图
应用探索：
- 无线网络中的频率分配
- 晶体学中的对称性问题