组合数学中最神秘的常数，拉姆齐数：看似幼稚的问题居然如此艰深

摘要：弗兰克·拉姆齐是二十世纪早期最非凡的人物之一。他在多个领域作出了重要贡献，从概率论到经济学，而他在数学上的贡献更是如此重要，以至于如今有一个完整的分支以他的名字命名。除此之外，作为一名哲学家，他还指导过路德维希·维特根斯坦的博士论文——而这一切都发生在他于19

弗兰克·拉姆齐是二十世纪早期最非凡的人物之一。他在多个领域作出了重要贡献，从概率论到经济学，而他在数学上的贡献更是如此重要，以至于如今有一个完整的分支以他的名字命名。除此之外，作为一名哲学家，他还指导过路德维希·维特根斯坦的博士论文——而这一切都发生在他于1930年不幸去世之前，那年他年仅26岁。

他显然也是一个极尽享受生活的人，通常只在上午工作，下午则去打网球。他想必还是个不折不扣的老饕，因为他体重高达108公斤，酗酒且举办盛大的派对。因此，用组织一次晚宴来引入如今以他命名的组合数学分支，实在再贴切不过。

五个人的晚宴

设想你正在筹办一场晚宴。现实生活中，人们之间可能存在很多种关系，从毕生挚友到誓不两立的仇敌，更不用说工作同事、泛泛之交、远房表亲，乃至同卵双胞胎。

但为了简化问题，我们假设你的客人之间只有两种关系：朋友或陌生人。那么，是否可能安排这样一场五人晚宴：其中既没有三位互为朋友的客人，也没有三位互为陌生人的客人？

答案显然是肯定的：想象把五位客人围坐在一张圆桌旁，假定每个人与左右相邻的两位是朋友，而与另外两个非相邻的则是陌生人。某一位客人只会与桌子另一侧的两个人互为陌生人，但由于这两人彼此相邻，所以他们是朋友，因此没有任何一位客人会处于“三个互为陌生人”的组合里。同样，也不会出现三个客人互为朋友的情形。

那么，如果我们邀请6个人来参加晚宴，情况是否依旧如此呢？令人惊讶的是，答案是否定的！要理解其中缘由，我们稍作抽象。回忆一下：图（graph）基本上就是一堆点（称为顶点，vertices），用一些线（称为边，edges）把它们连接起来。这里并不是讲授图论的地方——已经有很多更好的入门资料了。

我们关于“五人晚宴”的问题，可以转化为一个关于五个顶点的图的问题：在这个图里，不能存在三个顶点两两相连的情况（即它们构成一个三角形，或称为3-团，3-clique；一般来说，n-团就是由n个顶点构成的、两两之间都有边相连的子图）；同时也不能存在三个顶点彼此完全不相连（即它们构成一个3-反团，3-co-clique；n-反团的定义，想必你已经猜到了）。

我们将晚宴表示为一个图：客人作为顶点，只有当两位客人为朋友时，才在他们之间连一条边。于是，上述五人晚宴对应的图，就是所谓的5-环。

很容易看出，5-环是唯一一个在5个顶点上满足我们所需性质的图：如果一个顶点连接了三条或更多的边，那么要么这些相连的顶点中有两点之间再连接一条边，从而形成一个三角形；要么这些顶点之间完全没有边相连，此时任取其中三点就构成一个3-反团。

因此，每个顶点最多只能连接到2个顶点。再看：若某个顶点只连接到0个或1个顶点，那么它要么直接处在一个3-反团中，要么迫使其余的三个顶点构成一个三角形。所以我们必须要求每个顶点都恰好连接到另外两个顶点，而唯一符合条件的图就是5-环。

回到6人晚宴，换句话说，从我们的新视角来看，就是一个6个顶点的图。如果其中一个顶点记作 vvv，那么其余5个顶点所对应的子图必须是一个5-环；否则，根据上一段的论证，这5个顶点中就会出现一个三角形或一个3-反团。

6人晚宴 —— 在上图中，顶点 v 与其他5个顶点都是陌生人，这样它与5-环中任意两点就构成一个2-反团。

那么，v 与这5个顶点中的哪些相连呢？如果它与其中0个或1个相连，那么 v 将与它未相连的两点一起构成一个反团。如果它与其中3个或更多相连，那么它必然参与一个三角形。不管怎么安排，我们都无法避免得到一个三角形或一个3-反团。

这个热身问题把我们引向了……

拉姆齐数

设 m 与 n 是大于等于3的整数（在某些约定下，它们也可以取1或2，但为了简单起见，我们暂且忽略这些情况）。我们称拉姆齐数 R(m,n)的值为 r，如果以下命题成立：任意一个包含 r 个顶点的图，一定包含一个大小为 m的团，或者一个大小为 n 的反团。上一节的讨论，其实就是在证明一个事实：

R(3,3)=6

给定拉姆齐数 R(m,n)，若一个图含有 R(m,n)−1个顶点，并且它既不包含大小为 m 的团，也不包含大小为 n 的反团，那么这个图就称为一个 R(m,n)拉姆齐临界图。这种图的存在，为 R(m,n)的取值提供了一个下界。而上界的建立则更加困难。虽然对于较小的 R(m,n)存在一些通用结果，但在总体上，求解通常需要大量的高强度计算，往往还需要对较小的 m 和 n 值所对应的所有拉姆齐临界图进行完全枚举。

这就提出了一个问题：我们怎样才能简化寻找既不包含大小为 m 的团，也不包含大小为 n 的反团的图呢？这正是一个图的对称性能够让我们生活大大简化的完美例子。

我们称一个 t 个顶点的图为循环图（circulant），如果可以把顶点均匀地排在一个圆的周边，使得将圆旋转一个角度 2π/t后，整个图保持不变。换句话说，这个旋转会把每一条边映射到另一条已有的边上。前文提到的5-环就是这样一个例子。再来一个稍微有趣点的例子：考虑由8-环出发，并在每个顶点与其正对顶点之间连一条边所定义的图，如下所示。

一个循环图

如果想要一个更复杂的循环图例子，可以看看本文开头绘制的那个图（稍后我们会再讲到它）。

稍大一些的拉姆齐数

到目前为止，我们只讨论了拉姆齐数 R(3,3)，但其他一些小的拉姆齐数的取值也是已知的。之所以选择上一节末尾提到的循环图作为进一步的例子，是因为它恰好是一个 R(3,4)的拉姆齐临界图。这正是对称性大显身手的地方：由于每个顶点在结构上都是“相同的”，要验证没有顶点处在一个三角形中，我们只需检查任意一个顶点即可。

如果两顶点之间有一条边相连，我们称它们是邻居。但在上面的图里，每个顶点只有三个邻居，并且这三个邻居之间没有任何两点再相连，因此不存在三角形。同样地，检查任意一个顶点的非邻居，也可以看到不存在大小为4的反团。因此，这个图为 R(3,4) 提供了一个下界，即：

R(3,4)≥8

再结合上一节提到的上界推理，可以得出结论：

R(3,4) = 9

需要注意的是，在这个例子里，实际上有三个不同的 (R(3,4)拉姆齐临界图；其余两个可以通过对上面那个图删去一条边得到。要证明除了这三个之外没有其他的情况，则相当困难。

尽管对小拉姆齐数取值的探索，从技术上讲始于拉姆齐本人20世纪20年代的工作，并且在20世纪50年代的发表之后才真正提速，但直到今天，已知取值的仍然寥寥无几。值得注意的是，其中有相当多的例子都是循环拉姆齐临界图。这很可能只是一个“偶然产物”：因为目前的研究前沿仍然只处理小规模的情形——更大的数值通常并没有这样的性质。但在此期间，它们提供了很多方便的例子。

Greenwood 和 Gleason 证明了 R(3,5) = 14，其下界来自一个具有 13 个顶点的循环图，这个图由 [1,5] 定义，如下所示。