更新时间：2023-11-17 16:22
在组合数学上，诺曼·拉姆齐（Ramsey）定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。这个定理以弗兰克·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。
6个人中至少存在3人相互认识或者相互不认识。
该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。
证明如下：首先，把这6个人设为六个点。由A点可以引出五条线段。设：如果两个人认识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。
由抽屉原理可知：这五条线段中至少有三条是同色的。不妨设为红色。若或为红色，则结论显然成立。若和均为蓝色，则若为红色，则一定有三个人相互认识；若为蓝色，则一定有三个人互相不认识。
拉姆齐数，用图论的语言有两种描述：
对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作；
在着色理论中是这样描述的：对于完全图的任意一个2边着色，使得中含有一个k边形，含有一个l边形，则称满足这个条件的最小的n为一个拉姆齐数。（注意：Ki按照图论的记法表示i阶完全图）
诺曼·拉姆齐证明，对与给定的正整数数k及l，的答案是确定和有限的。
拉姆齐数亦可推广到多于两个数：
对于完全图的每条边都任意涂上r种颜色之一，分别记为，在Kn中，必定有个颜色为的边形，或有个颜色为的边形……或有个颜色为的边形。符合条件又最少的数n则记为。
拉姆齐数的数值或上下界
已知的拉姆齐数非常少，保罗·埃尔德什曾以一个故事来描述寻找拉姆齐数的难度：“想像有队ET军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”
已知的诺曼·拉姆齐数
关于拉姆齐数，有，当a,b大于等于2时。
显然易见的公式：
（将的顺序改变并不改变诺曼·拉姆齐的数值）
等于6的证明
证明：在一个的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。
• 任意选取一个端点P，它有5条边和其他端点相连。
• 根据鸽巢原理，5条边的颜色至少有3条相同，不失一般性设这种颜色是红 色。
• 在这3条边除了P以外的3个端点，它们互相连结的边有3条。
• 若这3条边中任何一条是红色，这条边的两个端点和P相连的2边便组成一个红色三角形。
• 若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了一个蓝色三角形。
• 而在内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。
拉姆齐理论的一个典型结果是从一些数学结构开始，然后将其切成碎片。为了确保至少其中一部分具有给定的有趣属性，原始结构必须达到多大，这个想法可以定义为分区规则。
例如，考虑一个n阶的完整图。也就是说，有n个顶点，并且每个顶点通过一条边连接到其他每个顶点。 3阶的完整图称为三角形。然后将每条边缘都涂成红色或蓝色。为了确保有蓝色三角形或红色三角形，事实证明n必须是6。
表达此结果的另一种方法如下：在至少有六个人的任何一方中，有三个人都是互相认识的（每个人都认识另外两个）或互相陌生的（每个人都不知道另两个人）。
这也是拉姆西定理的特例，该定理说，对于任何给定的整数c，任何给定的整数，都有一个数字 ，使得如果 阶的完整图的边用c种不同的颜色着色，那么对于介于1和c之间的某些i，它必须包含一个ni阶的完整子图，其边都是i。上面的特殊情况有和。
Van der Waerden定理：
对于任何给定的c和n，都有一个数字V，因此，如果V个连续数字用c种不同的颜色着色，则它必须包含长度为n的算术级数，其元素都是相同的颜色。
Hales–Jewett定理
对于任何给定的n和c，都有一个数字H，如果H维立方体的像元用c色着色，则必须有一行，列等长度为n的所有单元格都具有相同的颜色。那就是：多人n排字游戏不能以平局结束，无论n有多大，有多少人在玩，如果您在棋盘上有足够多的人玩尺寸。 Hales-Jewett定理隐含了Van der Waerden定理。
舒尔定理
对于任何给定的c，都有一个数字N，如果数字1，2，...，N用c种不同的颜色着色，那么必须有一对整数x，y，使得x，y和都是相同的颜色。存在该定理的许多概括，包括Rado定理，Rado-Folkman-Sanders定理，Hindman定理和Milliken-Taylor定理。格雷厄姆，罗斯柴尔德银行和斯宾塞是诺曼·拉姆齐理论中这些以及其他许多结果的经典参考。
Ramsey理论的结果通常具有两个主要特征。首先，它们是非建设性的：它们可能表明存在某种结构，但没有给出寻找此结构的过程（除了蛮力搜索）。例如，鸽洞原理就是这种形式。其次，尽管拉姆齐理论的结果确实表明足够大的物体必须一定包含给定的结构，但这些结果的证明通常要求这些物体非常大-呈指数增长或甚至与阿克曼函数一样快的界线并不罕见。在许多情况下，这些界限是证明的伪像，尚不清楚是否可以对其进行实质性的改进。在其他情况下，已知任何边界都必须非常大，有时甚至比任何原始递归函数还要大；有关示例，请参见Paris-Harrington定理。格雷厄姆数是认真的数学证明中使用的最大数，是与诺曼·拉姆齐理论有关的问题的上限。
Ramsey理论中的定理通常是三种类型之一。许多定理以Ramsey定理本身为模型，它们断言在一个大型结构化对象的每个分区中，其中一个类必然包含一个大型结构化子对象，但没有提供有关这是哪个类的信息。有时，出现此类Ramsey类型结果的原因是最大的分区类始终包含所需的子结构。根据图兰定理，这种结果称为密度结果或图兰类型结果。著名的例子包括Szemerédi定理，它是对Van der Waerden定理的强化，以及Hales-Jewett定理的密度形式。