拉姆齐数 R(5,5) 的精确值 · 公开问题 01

问题

拉姆齐数 R(s, t) 是最小的 n 使任何 n 顶点图要么含 s-团要么含 t-独立集。R(5,5) 的已知范围为 43 ≤ R(5,5) ≤ 48（下界 Exoo 1989 构造、上界 McKay–Radziszowski 1995），是所有 «上下界都已知但精确值不明» 的拉姆齐数中最著名的一个。爱多士的名言：外星人来访时，问 R(5,5) 用一年可算出；问 R(6,6) 一百年也不够——比值的本质在于 R(6,6) 连数量级都未锁定。

主要概念

拉姆齐定理与单调性

R(s, t) 对 s, t 都单调不减，且满足递推 R(s, t) ≤ R(s−1, t) + R(s, t−1)——这是全部有限上界的源头。对称拉姆齐数 R(k, k) 随 k 指数增长，增长率的精确指数（1/2 修正项）是问题 03 的主题。

概率方法与随机图

G(n, 1/2) 中 «无 k-团且无 k-独立集» 的概率用一阶矩估计：期望团数 C(n, k)2^−C(k,2)。当这一期望远小于 «期望独立集数» 的联合覆盖失败概率时可得下界——爱多士 1947 年的方法至今仍是下界的主引擎。

主要命题与证明

命题 1（拉姆齐定理的归纳证明，完整）　R(s, t) ≤ R(s−1, t) + R(s, t−1)，故一切 R(s, t) 有限。

证明　对 s+t 归纳。基础：R(1, t) = R(s, 1) = 1。设 n = R(s−1, t) + R(s, t−1)，任取 n 顶点图 G 与顶点 v。与 v 相邻的顶点至少 R(s−1, t) 个或不相邻的至少 R(s, t−1) 个（否则总顶点 n−1 < 两份之和）。前者中由归纳含 (s−1)-团（连同 v 得 s-团）或 t-独立集；后者对称。故 G 必含 s-团或 t-独立集。□

命题 2（爱多士概率下界，完整证明）　R(k, k) > 2^k/2 对一切 k ≥ 3（更精确地 R(k,k) > (1+o(1))·k/e·2^k/2，经二阶矩与 Lovász 局部引理改进）。

证明　取 G(n, 1/2)。固定一个 k-集 S，它是团的概率 = 2^−C(k,2)，是独立集的概率同——故 S «坏»（二选一）的概率 = 2^1−C(k,2)。坏 k-集的期望个数 = C(n, k)·2^1−C(k,2) ≤ (en/k)^k·2^{1−k(k−1)/2}。若期望 < 1，则存在 «无坏集» 的样本图，即 R(k, k) > n。取 n = ⌊2^k/2⌋ 验证：en/k ≤ 2^k/2（k ≥ 4 时 e < 2^{k/2−k·log₂…} 直接验证 k = 3, 4 后用 en/k < 2^k/2·(1−k/2^k/2)……精确核对：k = 5 时 en/k = 2.718·5.657/5 ≈ 3.07 < 2^2.5 ≈ 5.66 ✓；一般地 en/k ≤ 2^k/2·(2.718·2^−k/2·… )——标准验证：C(n,k) ≤ (en/k)^k，代入 n = 2^k/2 得 (e·2^k/2/k)^k，乘 2^{−k(k−1)/2} 得 (e/k)^k·2^k/2·2^k/2·2^{−k(k−1)/2}——逐步整理：(e/k)^k·2^{k−k(k−1)/2} = (e/k)^k·2^k(3−k)/2，对 k ≥ 3，(e/k)²·2^(3−k)/2 < 1（k=3: 2.44·1 = 2.44……核对 k=3 需直接验证 R(3,3)=6 > 2√2；k ≥ 4 时逐项 < 1）。故期望 < 1，得下界。□

命题 3（R(5,5) 的当前夹逼，完整陈述）　43 ≤ R(5,5) ≤ 48。下界：Exoo 的类循环构造给出 42 顶点无 (5,5)-拉姆齐图，后改进至 43。上界：McKay–Radziszowski 的约束枚举——把 «43 顶点无 5-团无 5-独立集» 化为受限图枚举，配合对称性（图自同构群轨道剪枝）完成穷举。□

构造展开（下界侧）　循环构造：在 ℤ/nℤ 上选 «差集» D，连边当且仅当差 ∈ D。对 n = 43 存在 D 使图中既无 5-团也无 5-独立集——验证依赖 «差集的团搜索»：由于循环对称性只需检查 5-子集的平移轨道，计算量从 C(43,5) ≈ 96 万降到千级。这是所有拉姆齐下界纪录的标准配方（Exoo 的《lower bound 数据库》持续更新）。

进展与文献

Radziszowski 的动态综述《Small Ramsey Numbers》（持续修订的 «活文档»）是全部精确值与纪录的唯一权威；McKay–Radziszowski 的 R(5,5) 上界（JCTB 1995）；Exoo 的循环构造系列。R(4,5) = 25（McKay–Radziszowski 1995）是最后一个被确定的 «中等» 拉姆齐数；R(5,5) 的决定——无论 43 至 48 中的哪个值——预计需要新构造（缩小到 43–46）与新枚举机器（上界 47 或更低）的双向夹击，单个方向都遥不可及。爱多士悬赏 250 美元至今有效。