结果族 189：Cycle–clique Ramsey numbers · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
派对上任意两人，要么是朋友（系红绳），要么是陌生人（系蓝绳）。问：至少要请多少人，才能保证出现”m 个朋友首尾相连围成一圈”或”n 个人两两互为陌生人”？所需的最少人数就是拉姆齐数。本文完全确定了”圈对团”的公式 @@M@@(m-1)(n-1)+1@@，了结 1978 年悬置至今的猜想。
关键词卡片
@@M@@R(H,J)@@：任何红蓝染色都必现红色 @@M@@H@@ 或蓝色 @@M@@J@@ 的最小顶点数。@@M@@C_m@@（cycle）：@@M@@m@@ 个点首尾相连的环，长度必须恰好是 @@M@@m@@，多一步少一步都不算。@@M@@K_n@@（clique）：两两之间都有边的 @@M@@n@@ 个点，这里指”两两陌生”的蓝团。看个具体例子
对照公式：@@M@@R(C_4,K_3)=(4-1)(3-1)+1=7@@。下图把 6 人分成两个红三角、组间全蓝，既无红四圈也无蓝三角，说明人数不能再少；这种”分成同色小块、块间换色”的分组构造，正是拉姆齐下界的经典手法。定理则保证第 7 个人一来，怎么染色都逃不掉。
为什么值得关心
一个悬置近五十年的精确组合公式被关闭；证明是”结构推理 + 程序核查 3099 个有限情形”的混合打法，展示了人机协作攻克精确组合问题的新范式。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的派对比喻说：任意两人要么是朋友、要么是陌生人，问至少请多少人，才能保证出现”m 个朋友首尾相连围成一圈”或”n 个人两两陌生”。换成半数学的说法：对象是一群人及他们之间被染成两种颜色的两两关系；我们要称量的，是”无论怎样染色都必然出现某种指定关系图案”所需的最少人数。
第二级台阶
用本科图论精确化：给 N 个顶点的完全图的每条边染红或蓝，拉姆齐数 R(H,J) 就是保证出现红色 H 或蓝色 J 的最小 N。这里 H 取圈 C_m——m 个点首尾相连、长度恰好为 m 的环；J 取团 K_n——两两相邻的 n 个点。圈长必须分毫不差，正是这一点让渐近工具无从下手。
第三级台阶
定理断言：当 m ≥ n ≥ 3 且 (m,n) ≠ (3,3) 时，R(C_m,K_n) = (m−1)(n−1)+1。假设中 m ≥ n 界定了猜想的有效区域，例外对 (3,3) 是因为 C₃ 与 K₃ 重合、经典值 R(3,3)=6 使公式失灵。下界来自显式构造：n−1 个互不相交的红 K_{m−1}、块间全蓝，既无红 C_m 也无蓝 K_n。论文证明的是上界——多加一个顶点就必然迫出二者之一。这正是 Erdős–Faudree–Rousseau–Schelp 1978 年的猜想（依 Keevash–Long–Skokan 的表述），至此完全关闭。
第一级台阶
导读的派对比喻说：任意两人要么是朋友、要么是陌生人，问至少请多少人，才能保证出现”m 个朋友首尾相连围成一圈”或”n 个人两两陌生”。换成半数学的说法：对象是一群人及他们之间被染成两种颜色的两两关系；我们要称量的，是”无论怎样染色都必然出现某种指定关系图案”所需的最少人数。
第二级台阶
用本科图论精确化：给 N 个顶点的完全图的每条边染红或蓝，拉姆齐数 R(H,J) 就是保证出现红色 H 或蓝色 J 的最小 N。这里 H 取圈 C_m——m 个点首尾相连、长度恰好为 m 的环；J 取团 K_n——两两相邻的 n 个点。圈长必须分毫不差，正是这一点让渐近工具无从下手。
第三级台阶
定理断言：当 m ≥ n ≥ 3 且 (m,n) ≠ (3,3) 时，R(C_m,K_n) = (m−1)(n−1)+1。假设中 m ≥ n 界定了猜想的有效区域，例外对 (3,3) 是因为 C₃ 与 K₃ 重合、经典值 R(3,3)=6 使公式失灵。下界来自显式构造：n−1 个互不相交的红 K_{m−1}、块间全蓝，既无红 C_m 也无蓝 K_n。论文证明的是上界——多加一个顶点就必然迫出二者之一。这正是 Erdős–Faudree–Rousseau–Schelp 1978 年的猜想（依 Keevash–Long–Skokan 的表述），至此完全关闭。
证明了 Erdős–Faudree–Rousseau–Schelp 1978 年提出的循环–团拉姆齐数（cycle–clique Ramsey number）猜想：@@M@@m\ge n\ge3@@ 且 @@M@@(m,n)\ne(3,3)@@ 时 @@M@@R(C_m,K_n)=(m-1)(n-1)+1@@，给出了完全图红蓝染色中迫出红 @@M@@m@@ 圈或蓝 @@M@@n@@ 团的精确阈值，悬置近半世纪的猜想就此完结。
拉姆齐数 @@M@@R(H,J)@@ 是最小的整数 @@M@@N@@，使得 @@M@@K_N@@ 的任何红蓝边染色都含红色 @@M@@H@@ 或蓝色 @@M@@J@@。Erdős、Faudree、Rousseau、Schelp 于 1978 年猜想：当 @@M@@m\ge n\ge3@@ 时 @@M@@R(C_m,K_n)=(m-1)(n-1)+1@@，其中 @@M@@C_m@@ 是恰有 @@M@@m@@ 个顶点的圈、@@M@@K_n@@ 是 @@M@@n@@ 点完全图，唯一例外是 @@M@@R(C_3,K_3)=6@@。难点在于圈长必须不多不少恰为 @@M@@m@@，渐近工具无从下手。半个世纪里只有零星进展：@@M@@n=3@@ 由 Chartrand–Schuster 解决，Bondy–Erdős 处理 @@M@@m\ge n^2-2@@，固定 @@M@@n\le7@@ 与 @@M@@n=8@@ 的部分情形逐篇推进，Nikiforov 覆盖 @@M@@m\ge4n+2@@。2021 年 Keevash–Long–Skokan 证明 @@M@@m\ge C\log_2 n/\log_2\log_2 n@@ 时公式成立，把未决情形压缩为有限多对 @@M@@(m,n)@@；本文补齐全部剩余情形，且不依赖常数 @@M@@C@@ 的数值。
主定理：对一切整数 @@M@@m\ge n\ge3@@ 且 @@M@@(m,n)\ne(3,3)@@，有 @@M@@R(C_m,K_n)=(m-1)(n-1)+1@@；例外对满足 @@M@@R(C_3,K_3)=6@@。
下界是显式构造：取 @@M@@n-1@@ 个两两不相交的红 @@M@@K_{m-1}@@，团间全染蓝，共 @@M@@(m-1)(n-1)@@ 个顶点，既无红 @@M@@C_m@@ 也无蓝 @@M@@K_n@@。论文证明上界，它等价于：凡 @@M@@(m-1)(n-1)+1@@ 个顶点的图必含 @@M@@m@@ 圈或 @@M@@n@@ 点独立集（independent set）——把红边视作该图即完成转化。记 @@M@@k=m-1@@、@@M@@a=n-1@@，需排除的即是满足 @@M@@|V(G)|=ka+1@@、@@M@@\alpha(G)\le a@@、无 @@M@@C_{k+1}@@ 的反例图 @@M@@G@@。
全证明先化归、再找结构、后取极值、终致矛盾，分四步递进。
第一步：极小反例与邻域扩张（expansion）。 固定 @@M@@k@@，取使上界失败的最小 @@M@@a@@ 及反例 @@M@@G@@。对非空独立集 @@M@@I@@，残余图 @@M@@G-N_G[I]@@ 仍无 @@M@@C_{k+1}@@ 且独立数至多 @@M@@a-|I|@@，由 @@M@@a@@ 的极小性它至多 @@M@@k(a-|I|)@@ 个点，从而 @@M@@|N_G[I]|\ge k|I|+1@@；特别地最小度 @@M@@\delta(G)\ge k@@。这个”删独立集、数闭邻域”的手法承自 1978 年原始论文，是全文的发动机。
第二步：找大团。 最大团规模 @@M@@t@@ 满足 @@M@@\max\{3,\lfloor k/2\rfloor\}\le t\le k@@。三角形由 @@M@@R(K_3,K_{a+1})\le\frac{(a+1)(a+2)}2\le ka+1@@ 直接得到；@@M@@k\ge8@@ 时反设无 @@M@@K_s@@（@@M@@s=\lfloor k/2\rfloor@@），在根点的广度优先搜索树中分层，同奇偶各层的最大独立集可以合并，代入扩张不等式逐层累加，迫使某层 @@M@@D_i@@ 满足 @@M@@|D_i|\ge s\alpha(D_i)@@；再取满足该式的极小诱导子图 @@M@@H@@，它连通、非二部、至少 @@M@@k@@ 个点、最小度至少 @@M@@s@@ 且自带同类扩张性质。最后用旋转论证（rotation）在 @@M@@H@@ 内造长路，借树中通向上层的路径缝合为恰 @@M@@k+1@@ 个顶点的圈，与反设矛盾。@@M@@k=3,4@@ 另行直接处理。
第三步：最优路径系统。 设 @@M@@k\ge5@@，固定最大团 @@M@@Q@@，令 @@M@@h=k+1-t@@。路径系统（path system）是若干条端点落在 @@M@@Q@@、内部互不相交且全在 @@M@@Q@@ 外的路，其表示边须构成线性森林（linear forest），各分量称链；系统总量（amount）为各路内部点数之和。关键引理：任何满足 @@M@@h\le q\le k+1-v@@ 的系统都能用团边把各链首尾相连，闭成恰 @@M@@k+1@@ 个顶点的圈，因而被绝对禁止。于是取总量 @@M@@L<h@@ 最大、路径数最少的系统 @@M@@\mathcal P@@，它的一切改良都被此”禁区”挡住；反过来，禁区迫使相关的团外路不存在，而路不存在又使球 @@M@@B_r(x;S)@@ 两两分离且无边相连（anticomplete），球内独立集便可合并。扩张保证 @@M@@B_1(x;S)@@ 至少 @@M@@t+1@@ 个点、含独立对，一个大小引理在球足够大时把独立数从 2 提升到 3。
第四步：收官矛盾。 当 @@M@@t\ge9@@，先证某对代表点间必有参数介于 @@M@@1@@ 与 @@M@@6@@ 的团外路，由此把 @@M@@\mathcal P@@ 逼入三种刚性构型之一（@@M@@d=2@@ 且几乎所有团点被关联；@@M@@d=3@@、@@M@@t\in\{9,11\}@@ 且表示边构成匹配；@@M@@d=5@@、@@M@@t=9@@、@@M@@k=19@@）；每种构型都能选出大批两两分离的球，各含独立对或独立三元组，合并后超过 @@M@@k@@ 个独立点，与 @@M@@\alpha(G)\le k@@ 矛盾。剩下 @@M@@3\le t\le8@@，此时 @@M@@5\le k\le17@@：把系统编码为模式（pattern，即各链内部点数序列，模反转与重排），共 42 个参数对、3,099 个实例；论文先证明五条推理规则（路径替换、精确闭圈、邻域增长、独立集装填、加边或添一个内部点致矛盾），再由两套独立实现的精确程序逐一排除——枚举的是加权森林而非图或染色本身。
本篇手稿的 formalized 标记为否：主结果暂无 Lean 形式化证明，按 OpenAI 官方声明，未经形式化的结果可能有问题，请以社区核验为准。论文的全部结构引理与五条推理规则均在正文给出证明，有限部分由两套独立实现的程序交叉验证并附完整推演轨迹（deduction traces）。结果族 189 仅含本篇，无姊妹篇互证；外部支撑主要来自与 Keevash–Long–Skokan 定理的衔接：该定理覆盖大 @@M@@m@@ 的渐近区域，本文以显式结构归约补齐其余全部情形。
问 1：证明的发动机是哪一步？
| 答：极小反例的扩张性质。固定 k=m−1，取使上界失败的最小 a=n−1 与反例图 G，则任何非空独立集 I 满足 | N[I] | ≥ k | I | +1，特别地最小度至少为 k。这个”删独立集、数闭邻域”的手法承自 1978 年原始论文，后续找大团、路径系统优化与有限排除全靠它供血。 |
问 2：最脆弱的环节在哪里？
答：有限部分的计算机排除。3,099 个参数-模式实例由两套独立实现的精确程序排除，枚举对象是加权森林（模式）而非图或染色本身。其正确性依赖两条腿：实现无误，且五条推理规则（路径替换、精确闭圈、邻域增长、独立集装填、加边或添一个内部点致矛盾）的数学证明无缺口——任何一条规则覆盖不全，枚举就可能漏排实例。推演轨迹可部分缓解。
问 3：与 Keevash–Long–Skokan 相比真正的新意是什么？
答：他们证明 m ≥ C·log₂n/log₂log₂n 时公式成立，把未决对压缩为有限多个，但常数 C 无数值、剩余对列不出来。本文给出显式结构归约，不依赖 C 的取值：大团引理（最大团规模 t ≥ max{3,⌊k/2⌋}）加上路径系统的极值优化，把剩余情形压到 42 对 (k,t)、3,099 个可枚举的模式。
问 4：为什么 (3,3) 必须除外、m ≥ n 不能去掉？
答：(3,3) 时 C₃=K₃，两种颜色索要同一个三角形，经典值 R(3,3)=6 ≠ 5，公式本身失灵；且 k=2 时最小度保证太弱，找团与路径论证无从启动。m<n 的区域不在猜想范围内，此时下界构造与上界论证的参数关系都会改变，论文未讨论。
问 5：AI 生成证明最可能出错的模式？
答：典型风险有二。一是结构引理的边界情形漏证——旋转论证要闭出恰好 k+1 个顶点的圈，长度差一就前功尽弃；二是”规则证明”与”程序判定”的接口错位：正文证明的图论陈述若与程序实际检查的条件不完全等价，排除即不充分。双实现与推演轨迹是合理防御，但论文未形式化，仍是最大不确定源。
问 6：这个结果谁会用到？
答：精确拉姆齐数与极图工作者——圈对团一族数字从此定案，可直接写入参考工具；”结构归约 + 模式枚举 + 双实现核验”的混合范式，对其它小参数 Ramsey 问题亦有示范意义。论文未讨论对圈长为区间（非精确）等变体的外推。
总评
关闭近五十年悬案并覆盖全部参数范围，是扎实的大工程；最大风险集中在 3,099 个实例的程序排除与推理规则的完备性衔接处，好在附有可复核的推演轨迹。
问 1：证明的发动机是哪一步？
| 答：极小反例的扩张性质。固定 k=m−1，取使上界失败的最小 a=n−1 与反例图 G，则任何非空独立集 I 满足 | N[I] | ≥ k | I | +1，特别地最小度至少为 k。这个”删独立集、数闭邻域”的手法承自 1978 年原始论文，后续找大团、路径系统优化与有限排除全靠它供血。 |
问 2：最脆弱的环节在哪里？
答：有限部分的计算机排除。3,099 个参数-模式实例由两套独立实现的精确程序排除，枚举对象是加权森林（模式）而非图或染色本身。其正确性依赖两条腿：实现无误，且五条推理规则（路径替换、精确闭圈、邻域增长、独立集装填、加边或添一个内部点致矛盾）的数学证明无缺口——任何一条规则覆盖不全，枚举就可能漏排实例。推演轨迹可部分缓解。
问 3：与 Keevash–Long–Skokan 相比真正的新意是什么？
答：他们证明 m ≥ C·log₂n/log₂log₂n 时公式成立，把未决对压缩为有限多个，但常数 C 无数值、剩余对列不出来。本文给出显式结构归约，不依赖 C 的取值：大团引理（最大团规模 t ≥ max{3,⌊k/2⌋}）加上路径系统的极值优化，把剩余情形压到 42 对 (k,t)、3,099 个可枚举的模式。
问 4：为什么 (3,3) 必须除外、m ≥ n 不能去掉？
答：(3,3) 时 C₃=K₃，两种颜色索要同一个三角形，经典值 R(3,3)=6 ≠ 5，公式本身失灵；且 k=2 时最小度保证太弱，找团与路径论证无从启动。m<n 的区域不在猜想范围内，此时下界构造与上界论证的参数关系都会改变，论文未讨论。
问 5：AI 生成证明最可能出错的模式？
答：典型风险有二。一是结构引理的边界情形漏证——旋转论证要闭出恰好 k+1 个顶点的圈，长度差一就前功尽弃；二是”规则证明”与”程序判定”的接口错位：正文证明的图论陈述若与程序实际检查的条件不完全等价，排除即不充分。双实现与推演轨迹是合理防御，但论文未形式化，仍是最大不确定源。
问 6：这个结果谁会用到？
答：精确拉姆齐数与极图工作者——圈对团一族数字从此定案，可直接写入参考工具；”结构归约 + 模式枚举 + 双实现核验”的混合范式，对其它小参数 Ramsey 问题亦有示范意义。论文未讨论对圈长为区间（非精确）等变体的外推。
总评
关闭近五十年悬案并覆盖全部参数范围，是扎实的大工程；最大风险集中在 3,099 个实例的程序排除与推理规则的完备性衔接处，好在附有可复核的推演轨迹。