Prime Certificates for Exact Vertex-Coprime Ramsey Numbers

技术摘要：精确顶点互素拉姆齐数的素数证书

问题陈述
本文研究了混合顶点互素拉姆齐数，记为 $R_{cop}(k_1, \dots, k_c)$，该数定义在互素图 $G_n$ 上。$G_n$ 的顶点集为 $\{1, \dots, n\}$，其中两个不同顶点 $a$ 和 $b$ 之间存在边，当且仅当 $\gcd(a, b) = 1$。该问题旨在寻找最小的整数 $n$，使得 $G_n$ 顶点的任意 $c$-着色都包含某种颜色 $i \in \{1, \dots, c\}$ 的单色团，其大小为 $k_i$。等价地，该问题寻求这样一个阈值：将 $\{1, \dots, n\}$ 划分为 $c$ 个集合时，至少有一个部分包含 $k_i$ 个两两互素的整数。

方法论与核心机制
作者通过识别一种能够压缩搜索空间的结构性“证书”解决了该问题，这与直接 SAT 编码的指数级复杂性形成对比。该方法依赖于基于素数除数的两种互补构造：

1. 上界（素数团）： 集合 $\{1\} \cup \{p \le n : p \text{ 是素数}\}$ 在 $G_n$ 中构成一个大小为 $\pi(n) + 1$ 的团，其中 $\pi(n)$ 是素数计数函数。根据鸽巢原理，如果颜色类的总容量（即 $k_i - 1$ 之和）小于该团的大小，则必然强制存在所需大小的单色团。
2. 下界（素数箱划分）： 对于低于阈值的 $n$，作者构造了一种有效的着色方案以避免单色团。这是通过将可用素数划分为容量对应于 $k_i - 1$ 的“箱子”（并对通用顶点 1 进行调整）来实现的。每个合数根据其落入某个箱子中的选定素数除数进行着色。由于两两互素的整数不能共享素数除数，任何单色团的大小受限于包含其见证素数的箱子的容量。

该方法被推广到支撑不相交图，其中顶点携带支撑（原子的子集），邻接关系由支撑不相交定义。互素图是原子为素数的特定实例。

主要贡献与结果

• 精确混合公式： 本文证明了混合顶点互素拉姆齐数的精确公式：
  $$R_{cop}(k_1, \dots, k_c) = p_M$$
  其中 $M = \sum_{i=1}^c (k_i - 1)$，$p_M$ 是第 $M$ 个素数。该结果对所有 $c \ge 1$ 和 $k_i \ge 2$ 成立。
• 边着色归约： 本文区分了同一宿主图上的顶点着色与边着色。它建立了边互素拉姆齐数 $R_{cop}^{edge}$ 到经典完全图拉姆齐数 $R_{cl}$ 的精确归约：
  $$R_{cop}^{edge}(k_1, \dots, k_c) = p_{R_{cl}(k_1, \dots, k_c) - 1}$$
  这表明边互素值并非新的算术常数，而是通过素数索引映射观察到的经典拉姆齐数。
• 平衡双色阈值： 作者解决了下界构造可能依赖于高度不平衡颜色类的担忧。他们证明，对于双色对角情形，平衡阈值（颜色类大小差异不超过 1）与无限制阈值相同：$L_{bal}(k; 2) = p_{2k-2} - 1$。这是通过确定性素数箱划分以及弱素数索引间隙不等式（$2p_m < p_{2m} < 3p_m$）实现的。
• 多色平衡与边界情形：
  • 对于 $c \ge 3$，平衡阈值对于小的 $k$ 并不精确，但对于所有足够大的 $k$ 变得精确（渐近精确性），这是通过霍尔型论证和 Selberg–Delange 估计证明的。
  • 本文分析了移位区间 $\{m+1, \dots, m+n\}$。在没有通用顶点 1 和初始素数团的情况下，精确公式失效，阈值取决于局部素数因子结构。
• 算法原语： 提出了一种多项式时间的证书提取原语，用于验证给定图是否允许支撑不相交证书。如果验证通过，则无需搜索即可确定拉姆齐阈值和极值着色。

意义与范围
本文声称完全解决了整数互素图上的顶点着色问题，用小型、显式的素数索引证书取代了大规模计算搜索（例如包含数百万个子句的 SAT 编码）。

• 结构洞察： 这项工作强调，互素图的算术刚性（由素数除数控制）使得拉姆齐问题能够坍缩为素数上的简单装箱问题，这与完全图上渐近困难的经典边拉姆齐问题不同。
• 对先前工作的澄清： 作者澄清，先前关于“互素拉姆齐数”的计算结果（特别是 Towell 的结果）指的是边着色变体，本文表明其等价于经典拉姆齐数。此处提出的顶点着色公式在已检查的公开来源中并不存在。
• 局限性： 本文明确指出，它并未改进经典边拉姆齐界限，也未提出通用的 AI 辅助求解器。结果特定于互素图及其支撑不相交变体。本文指出了关于非完全边目标（路径、环）、小 $k$ 的密度约束多色平衡以及其他算术图（其支撑不相交性质不能完全解释邻接关系）的拉姆齐阈值等未解决问题。

总之，本文为一类特定的算术拉姆齐数提供了决定性的、初等的证明，表明对于该宿主图，“障碍”是一个显式的素数团，而非隐藏的类随机构型。