Featured image of post 拉姆齐理论：完全无序中必有规则——通过6人社交关系着色证明
数学

拉姆齐理论：完全无序中必有规则——通过6人社交关系着色证明

只要聚集6个人，就必定存在互为熟人的3人，或者互不相识的3人。本文通过着色图证明拉姆齐数 R(3,3)=6，并深入解析5人时的反例、全部32768种涂色情况的程序验证，以及在数列和网络中的实际应用。

1. 6人聚会，必定能找到的“3人组”

假设有6个人参加聚会。他们之中可能有人是老相识，也有人是初次见面。不论谁和谁认识的关系有多么错综复杂，以下两种情况必定至少有一种会发生：

  • 任选其中2人，彼此都互相认识的3人组。
  • 任选其中2人，彼此都互不相识的3人组。

这并不是“大概率能找到”，而是无论人际关系如何组合，都 毫无例外 一定能找到。不仅如此，“6人”这个数字还是最小的临界值。如果只有5个人，就完全可以构造出避开这两种3人组的社交网络配置。

这个小小的惊奇，正是通往 拉姆齐理论（Ramsey Theory） 的大门。无论把一个庞大的结构划分得多么复杂，只要其规模足够大，就绝对无法完全避开具备某种特定性质的同质微观结构。拉姆齐理论研究的正是这种“无法回避的秩序与规律”。

不过，这并不意味着在混乱无序中会凭空出现任何你想要的规律。只有明确了研究对象、划分成多少类，以及寻找怎样的结构，它才能成为一个严谨的数学命题。首先，让我们从在纸上画6个点这个贴近生活的例子开始吧。

2. 将社交关系抽象为红线与蓝线

模型的约定

在本文中，我们假设“认识”是一种对称的关系：如果A认识B，那么B也认识A。而且任意两个人之间，必定明确属于“互相认识”或“互不认识”这两者之一。

单方面听说过对方名字，或者不确定是否认识的情况，都不在我们的讨论模型中。此外，“互不认识”也并不意味着“讨厌”或“敌对”。

我们将每个人表示为一个“点（顶点）”，将两人之间的关系表示为连接他们的“线（边）”。

图中元素含义
点（顶点）1位参与者
红色实线两人彼此认识
蓝色虚线两人互不相识
由同色3条边组成的三角形我们要寻找的3人组

因为所有参与者两两之间都连有线，所以在图论中这被称为 完全图 。包含 $n$ 个顶点的完全图记作 $K_n$，其边数为：

$$ \binom{n}{2}=\frac{n(n-1)}{2} $$

6个人对应的边数共有15条。仅仅满足“A认识B且A认识C”，并不能说明这3个人互为熟人；B和C之间也必须由红线连接。请务必记住，我们的条件是三角形的 全部3条边 必须同色。

在后文中，我们将全为红色或全为蓝色的三角形统称为 单色三角形 。为了在不易分辨颜色时也能清晰阅读，在插图中红色用实线表示，蓝色用虚线表示。

3. 证明：6人之中必定存在单色三角形

这个证明所需要的工具，仅仅是 鸽巢原理 。它基于一个极其朴素的事实：“将5个物品分配到2个类别中，至少有一个类别包含3个或更多的物品”。

步骤1：聚焦于任意一人

在6个人中，任选其中一人记为A。从A出发，连接向其余5个人的边共有5条。由于每条边非红即蓝，因此由鸽巢原理可知，至少有3条边具有相同的颜色。

$$ \left\lceil\frac{5}{2}\right\rceil=3 $$

这里的 $\lceil x\rceil$ 表示不小于 $x$ 的最小整数（向上取整）。也可以从反面来理解：如果红线和蓝线各自都不超过2条，那么总共最多只有4条线，无法填满5条边。

我们先考虑红线至少有3条的情况，并将这3条线连接的另外3个人记为B、C、D。此时，A–B、A–C、A–D全部为红线。若最初是蓝线有3条以上，只需在下文的讨论中将红蓝颜色互换，推理完全相同。

步骤2：观察B、C、D三者之间的关系

对于B–C、B–D、C–D这3条边，只可能出现以下两种情况：

情况①：至少存在1条红线。 例如，若B–C是红线，由于A–B和A–C也都是红线，那么A、B、C三人就构成了全红的单色三角形。此时其余两条边是什么颜色都无关紧要。

情况②：一条红线都没有。 那么B–C、B–D、C–D就必须全为蓝线。这时，B、C、D三人便直接构成了全蓝的单色三角形。

从A出发选出3条同色边，若其端点之间有红线则形成红色三角形，否则形成蓝色三角形的证明图

图中灰色显示的边以及被省略的边，是证明过程中无需确定颜色的部分。在实际的完全图中，它们同样会被涂上红色或蓝色。

至此我们证明了：无论怎样着色，图中都必定存在单色三角形。我们根本无需穷举全部15条边， 仅凭从1人出发的5条边以及相连3人之间的关系，就涵盖了所有可能的情况 。大学教材相关讲解

4. 为什么5个人还不够？

“6个人足够”与“6个人是最小值”是两个不同的命题。为了证明6是最小值，我们必须给出一个在5个人时不满足条件的具体反例。

我们将5个人放置在正五边形的5个顶点上。让相邻的两个人之间（即正五边形的外周5条边）涂成红色，而内部剩下的5条对角线全部涂成蓝色。

将五边形外周涂为红色、对角线涂为蓝色的5人反例。两种颜色均不包含三角形

单独观察红色部分，它是一个环绕五边形一周的五边形回路。任选3个人，都无法仅用红边闭合成一个三角形。单独看蓝色部分，虽然呈现为一个五角星形，但如果重新调整遍历顶点的顺序，它同样也是一个遍历5个顶点的五边形回路。因此蓝色部分中同样不存在任何三角形。

请注意，五角星内部的交叉点并不是新的顶点；与人对应的只有A到E这5个点。即使线段交叉在视觉上形成了小三角形，那也绝非本问题所考察的图论三角形。

由于全红和全蓝的3人组都可以被巧妙避开，所以在5个人的情况下无法保证必然存在。结合“6人必定存在”，我们便确定了最小人数恰好为6。

5. 这一“临界规模”被称为拉姆齐数

当对完全图的每条边任意涂上红色或蓝色时，必定会出现红色 $K_s$ 或蓝色 $K_t$ 的最小顶点数，记为 拉姆齐数 $R(s,t)$。

这里的红色 $K_s$ 指的是选出的 $s$ 个顶点之间，所有的边全部是红色的（即红色完全子图），仅仅由红色路径连通是不够的。由于 $K_3$ 就是三角形，因此我们前面得出的结论可以用简洁的一行公式表示：

$$ R(3,3)=6 $$

拉姆齐定理表明：对于任意给定的有限正整数 $s, t$，这样有限的拉姆齐数必定存在。然而，“存在”并不等同于“能够轻松求出其具体数值”。尽管对三角形（$s=t=3$）的证明非常简短，但只要把寻找的单色子图规模稍加放大，计算难度就会呈爆炸式上升。

对于拉姆齐数的基本数学上界，有如下著名的递推关系：

$$ R(s,t)\leq R(s-1,t)+R(s,t-1) \qquad(s,t\geq3) $$

记不等式右边的值为 $N$。我们在包含 $N$ 个顶点的完全图中任选一个顶点。若与该顶点由红边相连的顶点数不少于 $R(s-1,t)$，那么在这些邻接顶点中，必定包含一个红色 $K_{s-1}$ 或蓝色 $K_t$。若存在红色 $K_{s-1}$，将其与最初选定的顶点合并即可构成红色 $K_s$；若存在蓝色 $K_t$，则已直接满足条件。

如果红边邻接的顶点没有达到这个数量，那么根据鸽巢原理，由蓝边相连的顶点数就必定不少于 $R(s,t-1)$。对蓝色运用完全对称的推理即可。这一思路同样是“聚焦于单点并收集同色邻居”证明方法的推广。

从边界基准值 $R(2,t)=t$ 与 $R(s,2)=s$ 出发，利用上述递推关系便可依次构造出有限的上界。然而因为是不等式，计算出的数值并不一定是最小值。分清“能够予以保证的理论规模”与“实际所需的真正最小值”至关重要。

6. “几乎必然”与“绝无例外”的本质区别

现在我们来做一项思维实验：假设完全图的每条边相互独立地以 $1/2$ 的概率被涂为红色或蓝色。这个概率模型虽然对数学证明并非必需，但有助于我们直观领悟规律的特性。

将各个顶点分别标上A、B、C……的名字进行统计，着色方式的总数如下所示。即使某些着色在旋转或重命名顶点后在几何上全等，也视为不同的着色方式：

$$ 2^{\binom{n}{2}} $$

对于6个人，总共有 $2^{15}=32768$ 种着色可能。穷举验证3到6个人时的所有情况，可以得到如下结果：

人数着色总数不含单色三角形的着色数包含单色三角形的比例
3人8625.00%
4人641871.88%
5人10241298.83%
6人327680100.00%

对比3至6人中存在单色三角形的比例。5人时虽达到98.83%但仍有12种反例，而6人时则达到100%

即使是5个人，随机着色时出现单色三角形的概率也高达约98.83%。如果只随手做几次实验，人们很可能会误以为“5个人也必然会有”。然而，在全部1024种情况中，偏偏留存着12种反例。概率极高与 绝无反例 之间，存在着本质的鸿沟。

需要说明的是，此表呈现的是在独立且等概率涂色假设下的占比，并不代表现实中的社交关系真的是独立且各占50%。而拉姆齐定理的强大之处在于它完全不依赖于概率——无论现实中的人际关系多么极端倾斜，定理都绝对成立。

平均而言，能找到多少个单色三角形？

任意固定3个顶点，其间有3条边，共计 $2^3 = 8$ 种着色方式。其中全红和全蓝这2种属于单色，因此概率为 $2/8 = 1/4$。设单色三角形的个数为 $T$，由期望值的线性性质可得：

$$ E[T]=\binom{n}{3}\frac14 $$

对于6个人（$n=6$），期望值平均为 $\binom{6}{3}\times \frac{1}{4} = 20 \times \frac{1}{4} = 5$ 个。不同三角形之间因共享边而并不相互独立，但在计算期望值的和时，并不需要各个随机变量相互独立。

然而，数学期望大于0绝不意味着在所有着色中都必然存在。5人时的期望值也是2.5个，但依然存在个数为0的反例。不将“平均情况”与“最坏情况”混为一谈，同样是拉姆齐理论带给我们的深刻启示。

7. 用Python验证全部32768种情况

以下代码仅使用Python标准库即可运行。我们将红色编码为0，蓝色编码为1，用二进制数的各个位对应每条边的颜色。程序遍历所有选出3个顶点的组合，检查其间的3条边是否同色。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from itertools import combinations

def check_all(n):
    edges = list(combinations(range(n), 2))
    edge_index = {edge: i for i, edge in enumerate(edges)}
    triples = [
        [edge_index[e] for e in combinations(vertices, 2)]
        for vertices in combinations(range(n), 3)
    ]
    total = 1 << len(edges)
    without_triangle = 0
    minimum = len(triples)

    for coloring in range(total):
        count = 0
        for i, j, k in triples:
            if ((coloring >> i) & 1) == ((coloring >> j) & 1) == ((coloring >> k) & 1):
                count += 1
        without_triangle += (count == 0)
        minimum = min(minimum, count)

    return total, without_triangle, minimum

for n in range(3, 7):
    total, missing, minimum = check_all(n)
    print(f"{n}人: 共{total}种、无三角形{missing}种、最少{minimum}个")

1
2
3
4

3人: 共8种、无三角形6种、最少0个
4人: 共64种、无三角形18种、最少0个
5人: 共1024种、无三角形12种、最少0个
6人: 共32768种、无三角形0种、最少2个

6人时的“最少2个”，比我们最初证明的存在性更进了一步。事实上，若将连接到各个顶点的红边数量记为 $r_v$，蓝边数量记为 $b_v$，则有 $r_v+b_v=5$ 且整数乘积满足 $r_vb_v\leq6$。

对于非单色三角形，恰好有两个顶点的两条邻边是一红一蓝。因此，如果我们统计各个顶点处“一条红边与一条蓝边”的组合总数，就会将每个非单色三角形恰好重复计数2次。由于三角形总数为 $\binom{6}{3}=20$ 个，因此：

$$ T=\binom63-\frac12\sum_{v=1}^{6}r_vb_v \geq20-\frac12\cdot6\cdot6=2 $$

由此可严密证明单色三角形数量至少为2。此外，若将6个顶点划分为各含3个顶点的两个子集，子集内部全涂红边，跨子集的边全涂蓝边，就会得到两个红色三角形和零个蓝色三角形。这说明极小值2也是极其精确的紧界。

这种全排列穷举对于规模较小的人数非常有效，但着色总数以 $2^{n(n-1)/2}$ 的双重指数级飞速增长。增加人数会让该代码的耗时骤增，因此这里仅局限于3到6人。图表与详细分布可参见 复现脚本 与 计算结果JSON。

8. 应用①：网络中的“全连接”与“全断开”

不妨将“互相认识”置换为设备之间的直接物理连接。假设有6台网络设备，任意两台设备之间要么“存在直接连接”，要么“不存在直接连接”。只要连接是无向的，上述定理就可以原封不动地直接套用。

由此可知，必定存在3台设备两两之间均有直接连接的子集，或者3台设备之间两两均无直接连接的子集。在图论术语中，前者称为3个顶点的 团（Clique） ，后者称为3个顶点的 独立集（Independent Set） 。需要注意，这里的“无直接连接”并不意味着它们无法通过其他中继设备进行通信。

这种视角同样可用于评估成对任务的兼容/冲突关系，或是检查小型网络互联设计的约束条件。例如，即便你提出需求：“希望既不出现任意两两兼容易发生冲突的3个任务，也不出现任意两两均冲突的3个任务”，只要涉及的任务达到6个，在开始搜索之前就能断定这是绝不可能实现的。

然而，定理本身并不能帮我们选择哪一种情况出现。有时你迫切需要两两兼容的3个任务，找到的却可能恰恰是两两冲突的3个任务。此外，即使两两成对兼容，3个任务同时运行时资源是否充足仍需额外验证。定理能够保证的，仅仅是预先定义好的二元关系本身。

9. 应用②：从杂乱无章的数列中提取单调递增或递减子序列

考虑将6个互不相同的数字排成一个数列。当位置 $i$ 处于位置 $j$ 之前（即 $i < j$）时，若 $a_i < a_j$，我们就在位置 $i$ 和 $j$ 之间连一条红线；若 $a_i > a_j$，则连一条蓝线。

这同样构成了6个顶点的完全图双色着色。根据拉姆齐定理，图中必定存在单色三角形。若将构成单色三角形的3个位置按先后顺序记为 $i < j < k$，那么当它为红色三角形时：

$$ a_i\lt a_j\lt a_k $$

当它为蓝色三角形时：

$$ a_i\gt a_j\gt a_k $$

这说明： 在保持原有先后顺序不变的前提下，我们必定能从中提取出单调递增的3项，或单调递减的3项 。这些项在原数列中并不需要相邻。在数学上，这种不改变相对顺序而抽取部分元素构成的序列称为“子序列”。

从数列4, 1, 5, 2, 6, 3中选择原位置2, 4, 6提取出递增子序列1, 2, 3的图解

在图中的数列 $4, 1, 5, 2, 6, 3$ 中，选出第2、4、6项便得到了递增子序列 $1, 2, 3$。这并不是将数值从小到大重新排序，而是在保持它们原本出现顺序的前提下选出的。

这为从看似杂乱的数据流中挖掘规律性局部结构提供了思路。然而必须警惕的是，挑选出的3个点呈现递增，并不能作为该数据序列整体处于上升趋势的证据。因为如果某种形态在任何序列中都必然会出现，那么它的存在本身就不能算作什么特异现象。

顺便一提，对于数列问题，6项其实并不是最小门槛，实际上只需5个互不相同的数字就能保证存在长度为3的单调递增或递减子序列。这是著名的埃尔德什–塞凯赖什单调子序列定理（Erdős–Szekeres theorem）的一个特例。因为由数列大小关系构造出的着色具有传递性约束，所以能够得出比任意双色着色更强的结论。单调子序列相关讲义资料

10. 总结：杂乱之中，亦有无法回避的秩序

将6人之间的社交关系抽象为红线与蓝线，仅通过聚焦于由1人出发的5条边，我们便简洁地证明了单色三角形的必然存在。而5人时的正五边形着色给出了反例，由此确定拉姆齐数 $R(3,3)=6$。

本文中值得牢记的三个核心要点如下：

  • “必然存在”绝非随机实验中的“极高概率”。 5人时即便是约98.83%的高概率也仍有反例存在，而6人时则绝对不留任何反例。
  • 规律的存在并不等同于该规律具有特殊因果意义。 仅仅因为局部存在单色三角形或递增子序列，并不能断定整体群体的全局性质或趋势因果。
  • 理论保证具有严格的对象与前提条件。 必须先厘清关系是否对称、全部二元配对能否明确划分为两类，以及所要寻找的目标局部结构究竟是什么。

拉姆齐理论的迷人之处，并不在于它能把复杂的整体变简单，而在于它揭示了：即使系统整体保持着极度复杂混乱的状态，其中的微观局部规则也绝不可能被彻底消除。从纸上画出的区区几条线条中，我们就能真真切切地领会到这一深刻的数学思想。

参考资料

本文中的示意图、穷举表格、概率与数量分布数据，均由文章附带的Python脚本计算生成。

comments powered by Disqus
© 2020 - 2026 kenjinote
使用 Hugo 构建
主题 Stack 由 Jimmy 设计