组合学和图论之间的桥梁——拉姆齐理论，有着难以想象的复杂度

luyuanhong

组合学和图论之间的桥梁——拉姆齐理论，有着难以想象的复杂度

原创 我才是老胡 老胡说科学 2024-01-19 23:09 上海



我们如何研究结构与随机性之间的边界？数学中充满了这种现象，比如在非线性动力学和涌现过程的领域中。还有一些科学领域涉及混沌理论（Chaos Theory），比如气候系统。在我看来，这就是数学和科学变得最有趣的地方！这个迷人的边界可能出现在最意想不到的地方，比如被称为图论（graph theory）的高度结构化的数学领域。

如果你对图论有所了解，这可能会让你感到惊讶。这个数学的子领域充满了严格的布局和高度有序的网络。通过稍微改变规则，我们可以得到一个丰富而美丽的数学领域，它处理秩序与混沌的边界。这就是所谓的拉姆齐理论（Ramsey Theory），以英国杰出的数学家弗兰克·拉姆齐的名字命名。拉姆齐不幸在 26 岁时就去世了，但他的工作永远改变了数学。


● 弗兰克·拉姆齐，拉姆齐理论的创始人

维基百科对拉姆齐理论有一个有趣的定义。它被定义为一个数学领域专注于秩序的出现。

全文有更长的描述，但我喜欢这个摘录。它几乎是诗意的。这个定义简洁地总结了它，但它并没有告诉我们拉姆齐理论真正的含义。这就是这篇文章要做的。我首先要讲解图论的基础知识。然后我会讲述拉姆齐的变化（它涉及到着色！）。

图论

要理解拉姆齐理论，我们首先需要了解图论。这是一个处理网络的数学领域，在计算机科学中常用。实际上，它始于欧拉著名的“哥尼斯堡七桥问题”。



哥尼斯堡城（现在位于俄罗斯，当时属于普鲁士）被普雷格尔河分为四个部分，这四部分通过七座桥连接。问题是：是否有可能从城市的一个区域出发，穿越每一座桥恰好一次，然后回到起点或者结束于另一个地点。换句话说，就是寻找一条路径，它恰好经过每一座桥一次。


● K_3 示例图

上图有三个节点和三条边。节点标记为 A 、B 和 C ，边将它们相互连接。事实上，这是一种特殊类型的图，所有节点都相互连接，称为 K_3 。你可以想象一个修改过的版本的 K_3 图，其中至少有一对节点之间没有边相连。这样的图在图论中仍然是一个有效的图形，但它就不再是一个完全图（即不是 K_3 图）了。


● K_4 示例图

实际上，可能有无限多的图。图中的每个节点不需要通过边与另一个节点相连。图论有许多有趣的应用！我们说这个图不是完全图，因为不是每个节点都相互连接，



图论的价值在于它作为分析和理解各种网络和连接的强大工具。这个数学分支通过节点（代表点或顶点）和边（连接线）来模拟和简化现实世界中的复杂系统。这种简化手段使得我们能够清晰地识别和理解系统的核心结构及其组成部分之间的相互作用。

图论允许我们将复杂的系统看作是由多个相互连接的对象组成的网络。在这个框架下，对象可以是网络中的任何实体（如个人、计算机或城市），而它们之间的关系则通过边来表示。这种方法有效地将现实生活中的复杂关系转化为更容易分析和理解的数学模型。

此外，图论中的“有向边”概念为表示方向性提供了可能，使其成为描述具有明确方向流动（如单向道路或数据流）的理想工具。有向图（其边具有确定方向的图）可以更精确地描绘出信息或对象在系统内的流动方向。

下面，我们将深入研究拉姆齐理论。

拉姆齐理论

为了阐述拉姆齐理论的结构，我们需要在上述图形中添加一些新元素。我们将创建多种不同类型的边，每种边用不同的颜色表示。现在，我仅使用红色和蓝色的边。拉姆齐理论有多种颜色的版本，但为了本文的目的，我将保持简单。


● 带有彩色边的 K_4

现在，图形有了更多元素。我们可以根据边的颜色来构造子图。具体来说，如果我们有一个由不同颜色的边组成的图，我们可以选择这些边中的一种颜色，并利用这些特定颜色的边及其连接的节点来创建一个新的、更小的图，即子图。

子图是从原始图中选取一部分节点和边构成的。例如，假设原图中有红色和蓝色的边，我们可以选择所有红色的边及其连接的节点来形成一个子图；同理，选择所有蓝色的边及其连接的节点也可以形成另一个子图。这样，我们就根据边的颜色，从原图中分离出了两个不同的子图。

在创建这些子图的过程中，我们保留并重用了原图中的节点。这意味着，尽管子图只包含原图的一部分元素（即特定颜色的边和相连的节点），但这些节点在原图中仍然存在，维持了子图与原图之间的关联性。


将上面的图形分割成两个子图

这两个子图被称为“包含在”上面的原始彩色图中。它们保持相同的结构，只是其中的一部分。这两个图都不是完全图，因为一些节点没有连接。这与它们所包含的主图形成对比。

我们现在准备好了用一个具体的例子来展示拉姆齐理论的应用。想象一下，有六个朋友被邀请参加同一个派对。在这群朋友中，有的相互认识，有的则不认识。为了描绘这种社交关系，我们可以使用图论的方法。在这个图中，每个人都由一个节点表示，而他们之间的相识或不相识的关系则通过连接这些节点的边来表示。



为了区分朋友之间的不同关系，我们可以使用两种颜色的边：蓝色边表示两个人相互认识，红色边则表示他们彼此不认识。通过这种方式，这个图就变成了一个展示朋友间关系网络的视觉模型。在这个模型中，每个节点（代表一个朋友）都通过蓝色或红色的边与其他节点（其他朋友）相连，形成了一个揭示了他们之间已知和未知联系的复杂网络。这个网络为我们提供了一个实际的场景来应用拉姆齐理论，从而发现其中的一些数学性质和模式。

这就是拉姆齐理论的用武之地。弗兰克·拉姆齐证明了一个定理，无论如何，总会有三个人彼此认识或彼此不认识。这有点奇怪，边的排列方式有这么多种可能！这怎么可能被证明呢？所有边都相连的子图被称为“团（clique）”。

由于每个人要么相互认识，要么不认识，所以每对节点之间都有一条边。你能在那里找到一个由相同颜色边连接的三人小组吗？

这个图中实际上有多个三人小组。其中一个是在节点 A 、B 和 E 之间。它们都通过红色边连接，所以这是一个由三个陌生人组成的小组。在这个图中，实际上还有另一个三人小组：D 、E 和 F 。这个小组由蓝色边连接，所以他们都互相认识。无论我们如何设置颜色，总会有这样的子图存在。

这些子图总是存在似乎非常奇怪。用不同颜色设置这个图形有 2^15 种不同的方式，这是一个超过 3 万的数字！然而，拉姆齐理论证明，在每一个构型中，总有一个由三个全红或全蓝的组成的小组。

当我第一次听说这个时，我真的不相信。我花了一段时间试图找到一个反例。最终，我放弃了并接受了这个事实。


● 拉姆齐理论在更大的图中变得更加复杂

提高复杂度

我刚才展示的是一个相对较小的图。该图包含 6 个节点和两种颜色的边。在这种情况下，我们关注的是所谓的拉姆齐数（Ramsey Number），使用符号表示为 R(3,3) 。这个表达式中的两个数字 3 表示我们在图中寻找的是一个包含三个节点的子图，这些节点全部通过同色（红色或蓝色）的边相连。因此，这个拉姆齐数 R(3,3)=6 的含义是，在一个有 6 个节点的图中（完全图），无论如何着色边，总能找到一个全由同色边连接的三个节点的子图。实际应用到社交场景中，这意味着如果 有六个人参加派对，总会存在一个三人小组，他们之间要么全部相识（红色连接），要么完全不相识（蓝色连接）。

数学家已经计算出 R(4,4)=18 。所以如果我们邀请 18 人参加派对，那里会有一个大小为 4 的小组，他们要么都是朋友，要么都是陌生人。让人惊讶的是，R(4,4) 是目前已知的最高值。R(5,5) 是未知的。我们只知道 R(5,5) 在 43 到 48 位客人之间。

这为什么这么难以计算？假设有一个包含 43 个节点的图。这意味着有 2^903 种不同可能的红色和蓝色边的排列！这个数字是巨大的！即使使用最强大的超级计算机计算所有可能的排列也需要超过宇宙的年龄。

当然，数学家已经想出了各种巧妙的技巧来试图找到这个数字。这就是为什么我们有一系列的猜测。这些论证背后的证明超出了本文的范围，但我在最后提供的一些链接可以帮助你开始。


● 即使在纯粹的混沌中，总会出现某种形式的秩序

拉姆齐理论表明，无论系统多么混乱，总会在其中存在有序的部分。这是一个非常强大的声明，可以扩展到各种应用中。