People And Ramsey

官官方信息技术老师·26 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ People And Ramsey信息技术People And RamseyPeople
组合数学Ramsey理论图论鸽巢原理

People And Ramsey

看清 R(3,3)=6 的证明思路，触及 Ramsey 理论的边界与开放问题

按 空格/→ 演示下一步

1 / 26 页

全部页面点击任意一页，跳回舞台从这页播放

组合数学Ramsey理论图论鸽巢原理

People And Ramsey

看清 R(3,3)=6 的证明思路，触及 Ramsey 理论的边界与开放问题

1第 1 页 · People And Ramsey

一个有趣的派对游戏

想象一个六人聚会，有人相识，有人陌生。数学家说：不管关系多复杂，里面必然藏着「三人互相认识」或「三人互不相识」的小团体。

六人聚会
任意6个人，关系任意，没有其他前提
二色染色
认识涂红、不认识涂蓝，把关系压成边的颜色
鸽巢推理
任取1人，其5条边至少3条同色，必出同色三角形
R(3,3)=6
Ramsey数的最小保证，5人构不成反例
朋友圈红蓝标记对应 →图边二色染色

把每对关系当成一条边，红=认识、蓝=陌生，问题变成找同色三角形

$$R(3,3) = 6$$
2第 2 页 · 一个有趣的派对游戏

为什么答案是6

上一页我们见证了6人派对的神奇规律：必有3人彼此都认识或都不认识。但这是巧合还是数学必然？让我们戴上图论眼镜，重新审视这个派对。

完全图 K₆
6个人 = 6个顶点，每两人之间都有边，共 15 条
红蓝着色
认识→红色边，不认识→蓝色边，把关系编码到边上
单色三角形
问题化为：在 K₆ 的任何红蓝着色中，必有同色 K₃
鸽巢原理
n 件物品放 k 个抽屉，必有一个抽屉 ≥ ⌈n/k⌉ 件
边的封闭
从一人出发的 5 条边中，必有 3 条同色，与他人构成三角形
5 个球塞 2 个抽屉对应 →5 条边染 2 种颜色

鸽巢保证至少一个抽屉装 ≥ 3 个球；这里保证至少一个颜色被用到 ≥ 3 次

⌈5/2⌉=3\lceil 5/2 \rceil = 3
3第 3 页 · 为什么答案是6

派对问题的图示

用点和连线表示人际关系，红蓝边表示认识/不认识

派对问题的图示
用点和连线表示人际关系，红蓝边表示认识/不认识
4第 4 页 · 派对问题的图示

二染色完全图

上一页我们画出了 6 人之间的全连接网络，但边还彼此相同。要回答「是否有 3 人两两相识」，必须给每条边贴上二选一的标签——这正是「二染色完全图」。

完全图 K₆
6 个点两两相连，共 15 条边，没有遗漏
二染色
每条边恰好染成红或蓝中的一种，不存在第三色
两色即两态
红蓝对应派对上两种互斥关系：相识 vs 不相识
组合爆炸
15 条边各有 2 种选择，共 2¹⁵ = 32768 种染色方案
给每对人贴二元标签对应 →给完全图的边染色

标签只分「是/否」，颜色只分「红/蓝」，结构完全对应

E(K6)=(62)=15E(K_6) = \binom{6}{2} = 15
5第 5 页 · 二染色完全图

什么是「单色三角形」

上一页我们把完全图的每条边都染成了红色或蓝色——现在问题来了：在这张涂满颜色的图里，我们到底在找什么样的「特殊图形」？

单色三角形
三个顶点组成的三角形，三条边的颜色完全相同
两种颜色都算
全红三角形、全蓝三角形都是「单色」，颜色不挑
派对问题的靶心
R(3,3)=6 要找的就是它——出现任意一个就证明存在
班里3人互为好友 / 互不相识对应 →全红三角形 / 全蓝三角形

关系对应边的颜色，3对关系全同色即构成单色三角形

6第 6 页 · 什么是「单色三角形」

着色与单色三角形的对应

顺着流程读: 从任一2-着色出发, 看推理如何必然落到一个单色三角形。

图解渲染中…
a4：鸽巢原理: 5条边中必有3条同色a5：红蓝对称, 只展开红色分支a8：看3个邻居之间的3条内部边的颜色a10：若候选三角不全红, 可构造蓝色三角
7第 7 页 · 着色与单色三角形的对应

Ramsey Number 的定义

前页我们建立了『着色↔单色子图』的对应。现在把故事里的具体数字——6 个人、3 个点的子图——都换成参数，这就引出 Ramsey 数 R(m,n) 的形式化定义。

参数化定义
R(m,n) 是最小整数 N，使 K_N 的任意红蓝着色必含红 K_m 或蓝 K_n
对称性
交换红蓝色只调换 m、n 位置：R(m,n)=R(n,m)
已严格确定
R(1,n)=1, R(2,n)=n；非平凡有 R(3,3)=6, R(3,4)=9, R(4,4)=18
开放问题
R(5,5) 至今未定；m、n 越大未确定越多，只能给上下界
水沸腾的临界温度对应 →Ramsey 数的阈值

N 小于 R 时存在『不沸腾』的反例着色；达到 R 后任何着色都『沸腾』出单色子图

R(m,n):=min⁡{N∈N∣KN→(Km,Kn)}R(m,n) := \min\{N \in \mathbb{N} \mid K_N \to (K_m, K_n)\}
8第 8 页 · Ramsey Number 的定义

定义的核心要素

上一页我们写出了 Ramsey 数的正式定义。但这个看似简洁的写法里，其实悄悄藏了三个关键要素——每一个都不可或缺，缺了它整个定义就站不住。

存在性
这样的 n 一定存在，不会出现「找不到」的情况
任意性
对所有红蓝着色都成立，不是「碰巧某一次」
最小性
所有满足条件的 n 中最小的那一个，是「临界值」
水的沸点对应 →Ramsey 数的「最小性」

低于它水未必沸腾，高于它必然沸腾——Ramsey 数正是这个临界点

R(s,t)=min⁡{n: Kn 的任意 2-着色都含单色 Ks 或 Kt}R(s,t)=\min\{n:\,K_n\text{ 的任意 2-着色都含单色 }K_s\text{ 或 }K_t\}
9第 9 页 · 定义的核心要素

派对问题与 R(3,3)

直觉描述与数学定义说的是同一件事——但两套语言如何精确对应？

派对问题
  • 6人派对，两两构成一对
  • 每对人只分认识或不认识
  • 必有3人全认识或全不认识
R(3,3)
  • K₆，6顶点两两连边
  • 每条边着红色或蓝色
  • 必有红色三角形或蓝色三角形
本质等价：人是顶点，认识映射为红边，三角形即三人组。
10第 10 页 · 派对问题与 R(3,3)

经典结果一览

上一页我们证明了 R(3,3)=6。更大的数字呢？精确算出的只有几例，更多还卡在上下界之间——这是 Ramsey 数研究的常态：知道它存在，却算不出精确值。

斜线小值已定
R(3,4)=9、R(3,5)=14、R(3,6)=18、R(3,7)=23 等都已精确证明
R(4,4) = 18
目前最大的精确对角值，1955 年 Greenwood 和 Gleason 给出
R(5,5) 至今未解
仅知 43 ≤ R(5,5) ≤ 48，组合数学最著名的开放问题之一
对角线指数级增长
Erdős 下界 R(n,n) ≥ 2^(n/2)，n 每加 1 难度数倍提升
登山测高对应 →精确求 R(n,n)

小山能精确测高度，主峰只能给出「高于 X、低于 Y」的区间

R(n,n)≥2n/2R(n,n) \geq 2^{n/2}
11第 11 页 · 经典结果一览

R(3,3)=6 的证明：下界

把 K5 拆成红蓝两张子图，各为 5-圈，故任一颜色无三角形 ⇒ R(3,3)≥6

图解渲染中…
A：5 个点、10 条边，待着色B：外圈五边形 5 条边染红C：内部五角星 5 条边染蓝F：下界 R(3,3)≥6 证毕
12第 12 页 · R(3,3)=6 的证明：下界

R(3,3)=6 的证明：上界

鸽巢原理的论证流程：从任一顶点出发，二分支必得单色三角形。

图解渲染中…
v：K6 中任意选定的顶点, 与其余 5 点相连鸽巢原理：5 条边分 2 色, 至少 3 条同色a,b,c：与 v 同色相连的三个顶点
13第 13 页 · R(3,3)=6 的证明：上界

更大的 Ramsey Numbers

R(3,3)=6 已经完全证下。但把单色团人数门槛抬到 4、5，情况就全变样了——更大的 Ramsey 数，许多至今没有精确值。

递推上界
R(s,t) ≤ R(s-1,t) + R(s,t-1)，从已知小参数一层层推上来
R(4,4)=18
下界靠构造 17 顶点合法着色，上界靠递推收口
概率方法
Erdős 1947：随机两色着色中能避开单色 K_s∪K_t 的概率 > 0
R(5,5) 未解
只能把范围夹到 [43, 48]：下界靠计算机搜索构造
数独从 9×9 扩到 25×25对应 →Ramsey 数从 R(3,3) 到 R(5,5)

参数只多一格，可行解空间却指数级膨胀，人工枚举已不可能

R(s,t)≤R(s−1,t)+R(s,t−1)或R(s,t)≤(s+t−2s−1)R(s,t) \leq R(s-1,t) + R(s,t-1)\quad\text{或}\quad R(s,t) \leq \binom{s+t-2}{s-1}
14第 14 页 · 更大的 Ramsey Numbers

多颜色推广

上一节我们用两种颜色证明了 R(3,3)=6。但现实分类常常不止两个——会议有支持、反对、弃权，地图也要区分多个国家。多色推广 R(a,b,c,…) 自然登场。

多色 Ramsey 数的定义
R(a₁,…,a_k) 是使任意 k-着色 K_n 必含某色单色 K_{a_i} 的最小 n
存在性由定理保证
对任意正整数 a₁,…,a_k，R(a₁,…,a_k) 必存在（多色 Ramsey 定理）
三色起几乎算不出
k≥3 时除 R(3,3,3) 等极少数情况外，绝大多数多色 R 值只有上下界
R(3,3,3) 的悬案
三色版 R(3,3)=6 的自然推广，已知 17 ≤ R(3,3,3) ≤ 307
公司会议的二色表决对应 →多色 Ramsey 数

两色（支持/反对）6 人必出 3 人一致；三色（加弃权）门槛骤升，至今无人算出确切人数

R(a,b,c)≤R(a−1,b,c)+R(a,b−1,c)+R(a,b,c−1)R(a,b,c) \leq R(a-1,b,c) + R(a,b-1,c) + R(a,b,c-1)
15第 15 页 · 多颜色推广

图拉姆齐数

上一页我们把焦点放在「单色三角形」上，得到了 R(3,3)=6。但三角形只是最经典的一例——Ramsey 真正在问的是：给定任意一对图 G 与 H，是否存在一个让单色嵌入「逃不掉」的临界顶点数？

对象是任意图对
不再是只问三角形，可以是 K₄、C₅ 或任意 G 与 H 的组合
找的是同构嵌入
K_n 中要找到子图，与 G 或 H 严格同构，且所有边同色
临界值
使命题恒成立的最小 n；少一个点，就能既避开 G 又避开 H
三角形仅为例
R(3,3)=6 只是 R(K₃, K₃) 的特例写法
大画里找一只完整的红猫或蓝狗对应 →K_n 红蓝着色中找全红的 G 或全蓝的 H

形状须严格对应（同构），颜色须统一（单色）——缺一不可

R(G,H)=min⁡{n:对 Kn 任意红蓝二着色，都存在红色 G 或蓝色 H}R(G,H) = \min\{n : \text{对 } K_n \text{ 任意红蓝二着色，都存在红色 } G \text{ 或蓝色 } H\}
16第 16 页 · 图拉姆齐数

非对称拉姆齐数

前面看到的 R(3,3)、R(4,4) 都让两个参数相等。这次 m≠n，进入「非对称」领域——会撞上一个让数学家困惑多年的巧合。

定义扩展
m≠n 时仍称 R(m,n)；颜色互换不改变问题，故 R(m,n)=R(n,m)
已知名单
R(3,4)=9, R(3,5)=14, R(3,6)=18, R(4,5)=25
惊人巧合
R(3,6)=18 恰好等于 R(4,4)=18
为何意外
非对称值不能由 R(m,m) 与 R(n,n) 简单外推，必须逐一独立证明
两道考试分数线对应 →两类单色团的临界人数

同样划 18 分及格，「找红三角或蓝 K₆」与「找单色 K₄」难度竟然一样

R(3,6)=R(4,4)=18R(3,6) = R(4,4) = 18
17第 17 页 · 非对称拉姆齐数

已知上界与下界

上一页 R(3,3)=6 是精确值。但绝大多数 R(m,n) 我们算不出精确答案，只知道它被夹在两个数之间。

下界
构造 N 顶点的反例 2-着色，证明 R(m,n) ≥ N+1
上界
证明 K_R 任何 2-着色必含单色 K_m 或 K_n
经典递推公式
R(s,t) ≤ R(s-1,t) + R(s,t-1)，由此得 C(s+t-2,s-1)
R(3,k) 渐进
下界 Ω(k²/log²k)，上界 O(k²/log k)，渐近阶于 Kim 1995 确定
测量光速的历史对应 →Ramsey 数的渐进估计

下界逐步抬高，上界逐步压低，但仍未相遇

18第 18 页 · 已知上界与下界

R(5,5) 的故事

上一页我们知道，Ramsey 数的精确值多数时候只能靠上下界夹逼。R(5,5) 是这条路上最有名的「钉子户」——精确值至今未定，目前确定在 43 到 48 之间。

下界 ≥ 43
Exoo 1989 用计算机构造出 K₄₂ 的合法 2-着色，无单色 K₅
上界 ≤ 48
递推式 R(5,5)≤R(4,5)+R(5,4)=50，再精细分析压到 48
缺口仍 6
5 已超出人手推理能力，计算机也难以再前进一步
棋局里穷举每一步走法对应 →在 K₄₂ 的 2-着色空间里搜合法的那一个

解空间都指数级爆炸，必须靠算法剪枝，不是肉眼

19第 19 页 · R(5,5) 的故事

开放问题

R(5,5) 的故事里我们看到：敲定一个拉姆齐数往往要耗费数年甚至数十年。这背后到底卡在哪里？

组合爆炸
n 个点的候选着色数为 2^(n(n-1)/2)，增长远超指数
精确值稀少
对角线 R(n,n) 仅 R(1,1) 到 R(4,4) 共 4 个已知
上下界鸿沟
R(5,5) 已知 43 ≤ R ≤ 48，差距仍然明显
对称性帮助有限
等价着色归类只能消去固定倍数，无法突破指数壁垒
缺乏通用工具
没有像筛法那样可复用的方法，问题疑似计算困难
草垛找针对应 →穷举 R(n,n) 的精确值

针一定在草垛里，但草垛按指数级膨胀，逐根翻找永远完不成

20第 20 页 · 开放问题

组合学中的应用

开放问题告诉我们精确 Ramsey 数极难求。但「足够大则结构必现」这一思想本身是通用的证明工具，它能直接证明一大类极值组合定理。

极值断言
「足够大则必现特定子结构」是一类经典组合命题
Schur 定理
r-着色 {1,...,N} 中，N 充分大时必有同色 x+y=z
超图归约
把 x+y=z 编码为超边，问题化为超图 Ramsey 问题
概率下界
Erdős 用概率方法证 S(r) 至少随 r 指数增长
给 1~N 的卡片涂色对应 →Schur 定理

卡片对应数字，颜色对应着色，「必有同色 x+y=z」即 Schur 结论

S(r)=min⁡{N:任意 r-着色 [N] 含同色 x+y=z}S(r) = \min\{N : \text{任意 } r\text{-着色 } [N] \text{ 含同色 } x+y=z\}
21第 21 页 · 组合学中的应用

计算机科学中的应用

前几页我们看到 Ramsey 数像是组合学的'存在性宝石'。但真正让计算机科学家兴奋的，是它能直接拿来证明算法到底需要多少时间——这就是下界证明。

最长单调子序列
Erdős-Szekeres 定理可由 Ramsey 直接证明，长度 (n-1)²+1 的序列必含长 n 的单调子列
决策树下界
某些布尔函数的查询次数下界，证明里用到 sunflower 或 Ramsey 型引理
通信复杂度
多方通信中 Ramsey 型论证证明某些问题必须交换 Ω(n) 比特
物理守恒定律对应 →复杂度下界证明

守恒律说'这件事物理上做不到'，Ramsey 型下界说'这个算法不可能比这更快'

长度 (n−1)2+1 的序列必含长 n 的单调子列\text{长度 }(n-1)^2+1\text{ 的序列必含长 }n\text{ 的单调子列}
22第 22 页 · 计算机科学中的应用

日常决策中的拉姆齐思维

在不确定中寻找必然结构

日常决策中的拉姆齐思维
在不确定中寻找必然结构
23第 23 页 · 日常决策中的拉姆齐思维

知识要点回顾

  • ✓足够大的结构里，任意着色都藏不住单色子图
  • ✓R(3,3)=6 示范了「显式构造下界 + 鸽巢论证上界」模板
  • ✓R(s,t) 增长极快，精确值仅 R(3,3)、R(4,4) 等几例
  • ✓颜色数、对称性、图结构，是推广拉姆齐问题的三轴
  • ✓R(5,5) 仍未精确——组合数学的当代开放前线
延伸主题：Hales-Jewett 与其他拉姆齐型定理Erdős 的概率方法图拉姆齐数的渐近理论
24第 24 页 · 知识要点回顾

自我检测

3道题目验证对 Ramsey Number 的理解

自我检测
3道题目验证对 Ramsey Number 的理解
25第 25 页 · 自我检测

延伸思考

先自己琢磨一阵，再翻参考答案。三个问题层层递进。

1为什么 R(3,3)=6 不是 5 也不是 7？证明中最关键的一步是什么？

参考答案5 人时存在无单色三角形的反例；上界靠鸽巢：任取一点 5 条边中必有 3 条同色，强制出三角形。

2把派对人数从 6 改成 100，'必有 3 人构成单色三角形'还成立吗？

参考答案依然成立。R(3,3)=6 是最小门槛，意味着任何 ≥6 人的派对都满足，结论与人数无关。

3R(5,5) 为什么这么难？上界证明的瓶颈究竟在哪里？

参考答案上界靠穷举所有着色构型，但顶点数增多时构型数指数爆炸。目前仅知 R(5,5) 介于 43 与 48 之间。

26第 26 页 · 延伸思考
People And Ramsey · 知识图解