拉姆塞定理

最小正整数#

设 $r,s$ 是正整数。$R(r,s)$ 是满足下面条件的最小正整数：当 $n\ge R(r,s)$ 时，把 $K_n$ 的边任意染成红或蓝，都一定出现红色的 $K_r$，或蓝色的 $K_s$。红色的 $K_r$ 是 $r$ 个顶点，其中每条边都是红的。蓝色的 $K_s$ 同理，顶点数是 $s$，边全是蓝的。两种只要出现一种就成立。不要求两种同时出现，也不要求这种团只有一个。

够用的性质往上封闭，最小性才有着落。若某个 $n$ 已经使每种染色都出现所要的团，更大的完全图也一样：从中任取 $n$ 个顶点，它们之间的边已经染好，较小的完全图里就有那个团。所以够用的正整数一旦有了一个，所有更大的都够用。$R(r,s)$ 是其中最小的一个。只找到一个很大的够用的数，得到的是上界：最小正整数存在，并且不超过那个数。上界还不是最小正整数本身。

另一侧是反例。若 $K_m$ 有一种红蓝染色，既没有红色 $K_r$，也没有蓝色 $K_s$，则 $m$ 不够用，$R(r,s)>m$。最小性是两侧一起卡住。本页把两侧都写完的，只有 $r$ 与 $s$ 都取 $3$ 的那一对。其余参数只证明这个最小正整数存在，并给出一条不一定紧的上界。

完全图在定义里不是装饰。任意两顶点之间恰有一条边，不是红就是蓝。没有红边，就等于这条边是蓝的，不能理解成边不存在。若允许缺边，三个顶点可以两两都不连，两种三角形都谈不上。后面三个邻点之间要分情况，用的就是这个事实：那三条边都在，只是颜色还没看。

本页只染红与蓝两种颜色。把所有边染成红色，立刻得到红色团，蓝色团可以一个都没有。因此定义里的或，不是并且。六人聚会那句若被听成既有三人互识、又有三人互不相识，就多听了一句。全红的染色里人人相识，没有三人互不相识，定理仍然成立。它要至少一种单色团，并不要求两种颜色各自交出一个团。

递归只生产上界#

存在性用到的递归上界，只在两个参数都至少是 $3$ 时才往下调用。参数里已经出现 $2$ 的情形由边界负责。当 $r\ge 3$ 且 $s\ge 3$ 时，

$$R(r,s)\le R(r-1,s)+R(r,s-1).$$

对每个不小于 $2$ 的正整数 $k$，$R(2,k)=k$；把两种颜色对调，$R(k,2)=k$。边界不是从不等式推出来的。没有这个起点，递归只是把一个未知数写成另外两个未知数的和，并不说明它有限。

边界本身就是等式。红色的 $K_2$ 就是一条红边。在 $K_k$ 上，只要有一条红边，红色 $K_2$ 就有了。若一条红边都没有，每条边都是蓝的，整个图是蓝色 $K_k$。因此 $k$ 个顶点够用。再看 $k-1$ 个顶点，把每条边都染蓝：没有红边，顶点个数也到不了蓝色 $K_k$。所以 $R(2,k)=k$。这是边界自己的最小性，不是递归用了一次之后碰巧相等。$R(k,2)=k$ 只是红蓝对调。

不等式的一步是数一个顶点连出去的边。令 $a=R(r-1,s)$，$b=R(r,s-1)$，$n=a+b$。该顶点连出 $a+b-1$ 条边。若红边至多 $a-1$ 条且蓝边至多 $b-1$ 条，总数至多 $a+b-2$，与边数矛盾。所以红边至少 $a$ 条，或蓝边至少 $b$ 条。

红色邻点若至少有 $a$ 个，这些邻点之间的染色要么含红色 $K_{r-1}$，连上中心成为红色 $K_r$；要么含蓝色 $K_s$，那就是要找的蓝团。蓝色邻点若至少有 $b$ 个，同样二选一：蓝色 $K_{s-1}$ 连上中心成为蓝色 $K_s$，否则红色 $K_r$ 已经在邻点之中。因此 $n$ 个顶点够用，最小正整数不会超过 $a+b$。

归纳沿着参数之和往上走。和更小的那些值若已经有限，不等式就说明 $a+b$ 对当前这对参数够用。够用的正整数不是空集，故有最小元，它就是 $R(r,s)$。这个最小元不超过 $a+b$，但不一定等于 $a+b$。存在说的是最小元有，并且被一个有限数盖住。存在还不等于已经把最小元写成等式。

把边界代进 $r=s=3$。由 $R(2,k)=k$ 得到 $R(2,3)=3$，颜色对调得到 $R(3,2)=3$。于是 $R(3,3)\le R(2,3)+R(3,2)=6$。两个加数都是边界，没有借用别的精确拉姆塞数。六个顶点够用。五个顶点够不够，不等式没有说，此刻不能把小于等于写成等于。

同一条不等式用到更大的参数时，生产的仍是上界。即便右边两个数已经是各自的最小正整数，它们的和也不自动成为左边的最小正整数。最小性过不了加法。要把不等号收成等号，还得另外交出一个染色：顶点个数刚好比上界少一，两种团都不出现。本页只对三个顶点对三个顶点写出这个染色。没有反例的地方，递归停在上界。上界给出有限性，一般不是精确值。本页不再计算任何别的精确拉姆塞数。

五个顶点的五圈#

上界要收成 $R(3,3)=6$，缺的是下界。取五个顶点，当成凸五边形的五个角。红色只染五边形的五条边，五条对角线全部染蓝。$K_5$ 一共十条边，五红五蓝，没有漏边，也没有一条边染两次。

五条对角线自己构成另一条五圈。每个顶点有两个不相邻的顶点，蓝色边正好连向它们，所以蓝色图每个顶点的度都是 $2$。五个顶点、度全为 $2$ 的简单图只能是一条五圈：这样的图是若干个圈的不交并，五个点装不下两条长度至少为 $3$ 的圈。红色就是五边形自己的那条圈。两种颜色都是五圈。

一条五圈里没有三角形。任意三个顶点至少有一对在这条圈上不相邻，因而缺少一条这种颜色的边。红色没有红色三角形，蓝色没有蓝色三角形。五个顶点并不迫使单色三角形出现，所以 $R(3,3)>5$。

六个顶点够用，五个顶点有一个反例。若某个更小的正整数够用，五个顶点作为更大的完全图也必须够用，与反例矛盾。因此小于或等于 $5$ 的正整数都不够，最小的就是 $6$，即 $R(3,3)=6$。反例只要一个。定义要的是存在一种染色同时躲开两种三角形，不是大多数染色都躲开。

全红不是反例。若 $K_5$ 的每条边都是红色，红色三角形很多；全蓝也一样。五圈染色才同时躲开两种三角形：每个顶点恰好两条红边、两条蓝边，连不出三条同色边。六个顶点证明的第一步在这里没有落点。不是证明写漏了，是五个顶点还没被挤到那一步。

六个顶点上的三条边#

不背一般参数，六个顶点也可以直接证完。取 $K_6$ 的任意一个顶点，它连出五条边。若红边、蓝边都至多两条，总数至多四，与五条边矛盾。所以至少三条同色。这一步用到 鸽巢原理：五件东西放进两个盒子，必有一个盒子至少三件。结论只到同色的三星，即一个中心、三条同色边、三个邻点。

设这三条边是红色。三个邻点之间的三条边都在。若其中有一条是红的，它的两端再加上中心，就是红色三角形。若三条都不是红的，则三条全是蓝的，三个邻点自己构成蓝色三角形。三星若是蓝色，把两种颜色对调即可。因此 $K_6$ 的任何红蓝染色都有单色三角形，直接得到 $R(3,3)\le 6$。

第二支的三角形落在三个邻点上，不经过中心。不能把证明读成每个顶点都在某个单色三角形里。定理只要求整张图里至少有一个。中心可以只负责把五条边交给鸽巢，三角形出现在旁边。

这段和递归在 $r=s=3$ 时是同一次计数，不是第二条定理。递归里的 $R(2,3)=3$，就是这里的至少三条。写成直接证明，是为了六个顶点不必先记住一般参数。它不把上界从 $6$ 再往下压。等式仍要靠五圈：上界是 $6$，下界大于 $5$，最小正整数才是 $6$。

证明也不把染色列成表。固定六个顶点后有十五条边，每条两种染法。步骤不逐一查看这些染色。给定一种染色，只看一个顶点的五条边，取出三条同色的，再看邻点之间的三条边。单色三角形在这两次查看里出现。步骤短，是因为五被两种颜色一挤至少是三，不是因为有人巡视了全部染色。

鸽巢停在三星#

把这两步并成一句，就会说拉姆塞定理就是鸽巢原理。并不成。鸽巢原理比较物件和盒子。五条边、两种颜色、至少三条同色，是它在本页的全部用场。它不谈论团，也不知道三个邻点之间还有没有边。

停在这一步，手里只有同色三星。三个外端之间可以还没有与三星同色的边。没有下一步的分情况，三角形没有出现。因此鸽巢原理不保证单色三角形。分情况用的是完全图：那三条边必须都在，并且不是红的就是蓝的。缺一条边，两支都会落空。缺边不能被说成另一种颜色。

这条定理也不是把鸽巢换了名字。鸽巢可以用于同一个月里的生日，那些场合没有边，更没有单色的 $K_3$。本页从三星走到三角形，靠的是边已经染好。五个顶点的五圈把分界画出来：每个顶点只有两条红边和两条蓝边时，三条同色边还没被挤出来，单色三角形也确实可以不出现。

题目是逻辑里的判定#

弗兰克·拉姆塞（Frank Ramsey）1930 年的论文，题目是 On a Problem of Formal Logic，刊于 Proceedings of the London Mathematical Society，系列 2，第 30 卷，第 264–286 页，DOI 为 10.1112/plms/s2-30.1.264。题目里的问题是逻辑里的判定程序：有没有一种机械的办法，判定某一类句子是否成立。组合定理写在文章内部，是用来完成这件事的工具，不是论文的标题。

六人聚会必有三人或互识或互不相识，是后来的通俗说法。把红边读成相识，把蓝边读成不相识，$R(3,3)=6$ 就变成这句故事。故事只覆盖三个顶点对三个顶点这一个数。1930 年的题目里没有聚会，也没有把定理叫做派对问题。把故事的标题安回论文，是把讲法和篇名对调了。组合总览和图论页用相识关系帮助读者记住 $6$。本页沿用这个等式，只把篇名还回论文。

课堂上的完全图、红边与蓝边，是后来整理出来的讲法。整理可以使六个顶点的证明变短，但不能改 1930 年印出来的那行题目。本页的中文名用拉姆塞，与组合总览一致。这里不设人物字段，也不设年份字段。1930 是论文的年份，留在正文和参考文献里。站上没有拉姆塞的人物页，本页不新造这样的链接。

无限子集不是一个整数#

无限形式是另一个句子。取一个无限集合，把它的二元子集任意染成两种颜色，则必有一个无限子集，其二元子集全是同一种颜色。用图来说：无限个顶点两两有边，边任意红蓝染色之后，必有无限个顶点，它们之间的边全红，或全蓝。单色在这里指那个无限子集内部的所有边，不是仅仅出现一个有限三角形。

一个有限的 $R$ 代替不了这句话。$R(3,3)=6$ 只保证足够大的有限完全图里出现三个顶点的单色团。无限集合上的染色即使已有红色三角形，离边全红的那个无限子集仍差得远。把阈值换成更大的有限上界也一样：更大的有限数只保证更大的有限团，有限团仍然有限。量词的次序不同。有限定理先固定团有多大，再要一个顶点个数的阈值。无限形式里，染色已经做在无限集合上，要找的子集本身必须无限。

本页不证明无限形式。有限情形的存在性已经由边界和递归给出，不必先证明无限情形再推回来。即便有人从无限形式走到有限形式，走通了也只说明蕴含可以朝这个方向，并不把那个无限单色子集换成一个整数。读到拉姆塞定理，先看句子要的是有限团，还是无限子集。本页的等式只回答前一件。

跨域连接#

• 组合数学：组合总览把这条定理列为核心定理，写下 $R(3,3)=6$，并用六个人中必有三人互相认识或互不认识来记住它。那一句是总览里的口号，不是 1930 年的篇名。人是顶点，认识与否是边的两种颜色，三人两两关系相同是单色三角形。总览还把拉姆塞理论与极值组合分开：一边问足够大之后有序子结构是否必然出现，一边问在它出现之前结构最多还能有多大。五个顶点的五圈是后一个问题的很小样本，单色三角形到第六个顶点就躲不开。递归证明每个 $R(r,s)$ 有限，精确等式只写成了三个对三个这一对。总览的定理名单不是一张已经填满的精确值表。
• 图论：图论页用 $R(3,3)=6$ 说明完全无序不可能，并把六个人的相识关系当作日常说法。同页的经典问题里保存着更大参数的上下界。那些数字属于那一页，本页不重算，也不把那组夹逼抄回来。两边共用完全图、边染色和团这些词，共用词不等于共用计算。本页在 $R(3,3)=6$ 处停住，边界 $R(2,k)=k$ 只作为递归的起点。读到具体的夹逼区间时离开本页。留在这里，只核对三条同色边怎样逼出三角形，以及五圈怎样说明五个顶点不够。
• 鸽巢原理：六个顶点的证明里，五条边、两种颜色、至少三条同色，这一步才是鸽巢原理。它给出同色三星，不给出三角形。三角形来自下一步：邻点之间若有一条边与三星同色，就和中心构成三角形。若那三条边全是另一种颜色，三个邻点自己构成三角形。因此本定理不是鸽巢原理的别名，鸽巢也不保证单色三角形。没有完全图，邻点之间可能缺边，缺边不是另一种颜色，两支都会落空。五个顶点的五圈让鸽巢先挤不出三条同色边，单色三角形也确实可以没有。两页是证明里的先后，不是同一句话的两个标题。
• 拉姆齐数与组合学的新工具：对角情形的指数上界后来被改进，这件事写在这一页，不写在这里。本页的上界是递归不等式，它与五圈反例一起只把 $R(3,3)$ 收成 $6$。那是一对固定参数的最小正整数。前沿页讨论参数变大以后上界怎样跟着变。本页不重写那里的常数，也不把那些改进说成新的精确值。边界 $R(2,k)=k$ 是递归的起点，不是要在这里展开的另一串答案。要看上界后来怎样被压低，按那一页自己的标题去读。定理在这里叫拉姆塞，那一页沿用它已有的标题。本页不改那一页。

参考文献#

• Ramsey, F. P. On a Problem of Formal Logic. Proceedings of the London Mathematical Society, series 2, vol. 30 (1930), 264–286. DOI: 10.1112/plms/s2-30.1.264. 论文的问题是逻辑里的判定程序，组合定理在文章内部。聚会说法不是这篇的题目。
• Béla Bollobás. Modern Graph Theory. 1998. 组合总览已列此书。本页用它作有限图上这个陈述的课程来源，不编定理号。