拉姆齐理论是以英国数学家和哲学家弗兰克·P·拉姆齐（Frank P. Ramsey）的名字命名的，是数学的一个分支，致力于研究必须出现阶数的条件。 拉姆齐理论中的问题通常会问一个形式的问题：“某种结构中必须有多少个元素才能保证特定的财产能够持有”。

1930年弗兰克·普伦普顿·拉姆齐在论文On a Problem in Formal Logic （《形式逻辑上的一个问题》）证明了R(3,3)=6。

拉姆齐定理

Ramsey

拉姆齐二染色定理

弗兰克·普伦普顿·拉姆齐 

数学、计算机 

   R(a,b)个顶点的完全图 

定理定义

在组合数学上，拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

拉姆齐理论的核心可以概括成：完全的无序是不可能的。更具体的，Ramsey 理论中 典型的问题是：为了保证在某个集合（或系统）中有某种性质（或结构）一定出现，这个 集合的元素个数应该达到多少？从最初的拉姆齐定理到后来发展出的众多拉姆齐型定理都表明：一个集合只要元素数量达到某个临界值后，一定会出现我们预先定义好的某种 性质或结构。纳什之所以自信可以画出任意的形状，是因为星星的数量非常巨大，因此可以保证一定会出现想要的形状。除此之外，我们熟悉的鸽笼原理也是拉姆齐理论的一个例子。

电影《美丽心灵》中有一段非常浪漫的场景：纳什和艾丽西亚站在喷泉边，仰望星空， 艾丽西亚说自己曾数星星数到了 4348 颗，纳什笑着回复，咱俩真是一对怪胎。接着，纳什 让艾丽西亚选一个形状，动物随便什么都可以。艾丽西亚想了想说，雨伞。纳什走到艾丽 西亚背后，拿起她的手，在星空中用星星连出一个雨伞的形状。艾丽西亚芳心瞬间被俘获， 于是央求：再来一次，再来一次嘛！来画个章鱼！

姑且不论纳什是否做过这么浪漫的事，也不论纳什是否有这样的本领；假如是真的， 我们想问的是，纳什为什么自信可以用星星连出任意的形状呢？答案或许藏在一个数学理论中，这就是组合数学中的拉姆齐理论(Ramsey Theory)。

拉姆齐理论的核心可以概括成：完全的无序是不可能的。更具体的，Ramsey 理论中 典型的问题是：为了保证在某个集合（或系统）中有某种性质（或结构）一定出现，这个 集合的元素个数应该达到多少？从最初的拉姆齐定理到后来发展出的众多拉姆齐型定理都表明：一个集合只要元素数量达到某个临界值后，一定会出现我们预先定义好的某种 性质或结构。纳什之所以自信可以画出任意的形状，是因为星星的数量非常巨大，因此可以保证一定会出现想要的形状。除此之外，我们熟悉的鸽笼原理也是拉姆齐理论的一个例子。

鸽笼原理传统的理解是，

只鸽子飞进 

个鸽笼，一定会有一个鸽笼里面至少有两只鸽子。如果遵循 Ramsey 理论的思想，我们可以把鸽笼原理换一种方式理解：给定 

个鸽笼，如果想要鸽子“同笼”一定发生，那我们至少需要多少只鸽子？答案是

。

再换一套语言来理解鸽笼原理。假设有 

 种颜色用来给鸽子上色，如果要保证一定出现“同色”鸽子，问至少需要多少只鸽子？答案还是

。

再换一套语言。假设有 

 两 个集合，其中集合

中有

个元素(即势为

)。现在从集合 

 向集合

作映射 

，如果要保证一定会出现

，问集合

的元素个数至少是多少个？答案还是 

。

从这个角度看，鸽笼原理，以至拉姆齐理论其实是在探讨这样的问题：如何从不确定性中抽取出确定性，或者说如何从混沌（Chaos）中找到秩序（Order）。不确定性是说鸽子飞进鸽笼鸽子的染色方案看成映射，因为不同的映射构成一个随机事件的空间，有些随机事件满足我们想要的性质，有些则不能；另一方面，如果我们扩张这个空间，则想要的确定性就一定会出现。这个转变一定会有一个临界状态和临界值，就像水结冰对应的临界状态是冰水混合，对应的临界值是 0°C 一样。在鸽笼原理中，因为我们想要的性质比较简单，这个临界状态正好是鸽子占满鸽笼且均匀分布在鸽笼中，因此对应的临界值是

（限制条件的线性函数），这也是为什么看起来鸽笼原理好像是带余除法的应用。

首先看一个代数的例子。我们从 1 依次开始往后写正整数，假设我们有红黑两种颜色的笔，在每个整数写好的整数上涂上红色或者黑色。如果想要一定会出现一个长度是3同色的等差数列，问至少要写到几？答案是 9。显然，这里的临 界值是 8。2

验证推导

我们用形式语言刻画图论，则图论的语言 

 ，这里的

表示“边” ,

 的理论即图论是以下两个句子的句子集： 

一个具体的图即是图论的一个模型。我们先考察四色定理。

定理 1（四色定理对任意无穷平面图可以用四种颜色对其结点进行着色，使得相邻结点都有不同的颜色。

证明对有穷平面图，已经有 APPellle 和 Haken 在 1976 年证明的有穷平面图四色定理：每个有穷平面图都可以用四种颜色着色。我们用预备知识中介绍的概念将这个结论推广到无穷平面图。

令 

 为无穷平面图，膨胀语言

为

 ，其中

 为引入的四个一元关系符号，分别表示红、绿、蓝、黄，令

是膨胀语言

中如下的公式

该公式表示可用 

四种颜色对平面图着色。令

则根据有穷平面图四色定理，

有穷可满足，从而得到又的任一有穷子集有模型，由模型论紧致性定理，有模型

从而 

由引理1，

可以同构嵌。

定理推广

对于任何一个正整数

,存在一个最小的正整数

,使得对任意一个至少有

个顶点的图

,它或者有

个顶点的完全子图

,或者有

个顶点是独立集.由此定理易得:设

是顶点数

的简单图,其边数

,且

的所有

阶导出子图的边数相等,那么

是完全图.并给出上述结论的推广:设

是

阶简单图,其边数

,对某个给定的自然数

,若

的所有

阶导出子图的边数相等,则

是完全图。

定理意义

Ramsey理论的结果通常具有两个主要特征。首先，它们是非建设性的：它们可能表明存在某种结构，但没有给出寻找此结构的过程（除了蛮力搜索）。例如，鸽洞原理就是这种形式。其次，尽管拉姆齐理论的结果确实表明足够大的物体必须一定包含给定的结构，但这些结果的证明通常要求这些物体非常大-呈指数增长或甚至与阿克曼函数一样快的界线并不罕见。在许多情况下，这些界限是证明的伪像，尚不清楚是否可以对其进行实质性的改进。在其他情况下，已知任何边界都必须非常大，有时甚至比任何原始递归函数还要大；有关示例，请参见Paris-Harrington定理。格雷厄姆数是认真的数学证明中使用的最大数，是与拉姆齐理论有关的问题的上限。

Ramsey理论中的定理通常是三种类型之一。许多定理以Ramsey定理本身为模型，它们断言在一个大型结构化对象的每个分区中，其中一个类必然包含一个大型结构化子对象，但没有提供有关这是哪个类的信息。有时，出现此类Ramsey类型结果的原因是最大的分区类始终包含所需的子结构。根据图兰定理，这种结果称为密度结果或图兰类型结果。著名的例子包括Szemerédi定理，它是对van der Waerden定理的强化，以及Hales-Jewett定理的密度形式。

拉姆齐二染色定理

拉姆齐二染色定理是由英国数理逻辑学家西塔潘（Seetapun）于20世纪90年代提出的一个猜想。十多年来，许多著名研究者一直努力都没有解决。今年5月，由北京大学等联合举办的逻辑学术会议上，还是大三的刘嘉忆报告了他对目前反推数学中的拉姆齐(Ramsly)二染色定理的证明论强度的研究。这是由英国数理逻辑学家Seetapun于上个世纪90年代提出的一个猜想，十多年来，许多著名研究者一直努力都没有解决。刘嘉忆的报告给这一悬而未决的公开问题一个否定式的回答，彻底解决了Seetapun的猜想。继今年上半年他攻克一个十多年悬而未决国际数学难题后，不久前在美国芝加哥大学结束的数理逻辑学术会议上，他作为亚洲高校唯一一位代表在会上做了40分钟报告，报告了他在数理逻辑方面的研究成果，语惊四座。1

声明：本文部分文字与图片资源来自于网络，转载此文是出于传递更多信息之目的,若有来源标注错误或侵犯了您的合法权益，请立即【留言反馈】通知我们，情况属实，我们会第一时间予以删除，并同时向您表示歉意