问题
R(4,4,4):最小 N 使 N 顶点完全图的 3-边染色必含单色 K4。已知在 51 与 62 之间:下界 51(1974 年的构造染色)、上界 62(Radziszowski–Xu)——四十余年未动。它与图论分册 04 号的 R₄(3)(同为 51–62 区间)数值对望——纯巧合的 «区间共振»,但两者都卡在同一堵墙前。多色拉姆齐谱系(R(3,3,4)、R(3,4,4) 等部分确定)中 R(4,4,4) 是下一位主角,也是 «拉姆齐理论可计算性极限» 的标本。
主要概念
下界的构造侧
51-顶点的 3-染色无单色 K₄:1974 年的构造(循环群 𝔽₅₁? 的 «差集染色»——以 ℤ51 的循环差集给三种边的 «颜色类»)。构造的 «代数骨架»(循环差集、强正则图拼合)是拉姆齐下界的标准配方;改进到 52 需要 «更好的差集»——候选已被大规模搜索扫过多数类型。
上界的机器侧
62 的上界是 «经典递归+手工剪枝»:R(4,4,4) ≤ R(3,4,4)+R(4,3,4)+R(4,4,3)−2 型递归给 «百级»,Radziszowski–Xu 的改进走 «逐点邻域的色结构分析»。当代可能的新机器:SAT 的 cube-and-conquer(S(5)=160 的配方)——但 62→61 的每一步都是 «百万核·年» 级工程,理论侧 «新不变量» 的希望与计算侧的算力竞速。
主要命题与证明
命题 1(经典递归上界,完整证明) R(k₁,…,kr) ≤ Σj=1r R(k₁,…,kj−1,…,kr) − r + 2。
证明 设 N = 1 + Σj (R(…,kj−1,…)−1)。取 N 顶点 r-染色完全图与顶点 v:v 的 N−1 条边按色分组,由 N−1 = Σ(R(…,kj−1,…)−1) 与鸽笼,某色 j 的 «v-邻集» 至少 R(…,kj−1,…) 个顶点。该邻集内:若含色 j 的 Kkj−1,则连同 v 得单色 Kkj;若含其他色 i 的 Kki,直接命中。故 N 顶点必含单色目标。□
命题 2(R(4,4,4) ≤ 62 的机制;陈述) Radziszowski–Xu 的上界:在经典递归之上加入 «邻域色结构» 的精细分析——固定顶点 v 的三色邻集 A,B,C,«A 内的边色分布» 受 «无色-1 K₃» 约束(否则 +v 成 K₄),迭代 «每点的 K₃-自由子结构» 的强制约束直至矛盾。手工+程序辅助的树搜索。
说明 这类 «约束传播» 的手工版本正是 SAT 求解器内部机制的人肉形态——62 的证明本质上是 «早期的 cube-and-conquer»。□
命题 3(51 下界的差集构造;陈述) ℤ51 上的循环 3-染色(三组 «颜色差集» 的并覆盖所有非零差且各自 «无 K₄-型差»)给出无单色 K₄ 的 51 顶点染色。大规模搜索已扫过 «循环型» 候选,52 的循环下界不存在——52 若成立必用非循环构造。
说明 «循环构造的天花板已探明» 是当代拉姆齐下界的典型处境:构造空间的下一个增量需要 «非平移对称» 的新对象。□
进展与文献
Radziszowski 的 «Small Ramsey Numbers» 动态综述(持续更新的权威表);Radziszowski–Xu 的 R(4,4,4) 上界;Grinstead–Roberts 与 Exoo 的下界构造谱系;与 27 号 SAT 引擎的共用基建。开放核心:R(4,4,4) 的真值(51/52 与 61/62 两端的独立攻坚);R(3,3,4)、R(3,4,4) 等近邻值的关闭;«拉姆齐数与 SAT 引擎» 的方法论文。