拉姆齐理论

关于无穷集上的拉姆齐理论，请见无穷元组合学。

拉姆齐理论得名自英国数学家兼哲学家弗兰克·普伦普顿·拉姆齐，是数学的一支，在大而无迭序的结构中寻找必然出现的有迭序的子结构。拉姆齐理论研究的典型问题形如：“某某结构要何等大，才能保证具有某某性质？”更具体而言，葛立恒称拉姆齐理论为“组合数学的分支”。

例子

拉姆齐理论的典型例子中，先有某个数学结构，然后该数学结构会切成若干小份，问题是原结构要多大，才能保证不论切法为何，仍有某一份具有指定的性质。此想法带出分划正则性的严格定义。

例如，考虑$n$阶完全图，即有$n$个顶点，每个顶点皆与其余$n-1$个顶点各以一条边相连。$3$阶完全图称为三角形。现将逐条边染红或蓝。$n$至少为何，才能保证总有一个同色（全红或全蓝的）三角形？答案为$6$。拉姆齐定理的条目有此结论的严格证明。

换言之：若任一个宴会上有至少六人，则必有三人，该三人或两两互为朋友，或两两互为陌生人。此版本又称朋友与陌路人定理。

上述结论为拉姆齐定理的特殊情况。该定理断言，给定正整数$c$，及正整数$n_{1},n_{2},\ldots ,n_{c}$，则必存在某个正整数$R(n_{1},\ldots ,n_{c})$，使得不论$R(n_{1},\ldots ,n_{c})$阶完全图$G$的边如何染成$c$种颜色，仍有某个$i\ (1\leq i\leq c)$，令$G$包含某个所有边皆为颜色$i$的$n_{i}$阶同色完全子图。取$c=2$和$n_{1}=n_{2}=3$即得上段的特殊情况。

成果

拉姆齐理论的著名定理有：

• 范德瓦尔登定理：对任意$c,n$，必有某个$V$，使得：若将$V$个连续正整数染成$c$种颜色，则必有长度为$n$的同色等差数列。
• 黑尔斯－朱威特定理 ：对任意$n$和$c$，必有某个$H$使得：若将$H$维的$n\times n\times \cdots \times n$立方体中，每个单位立方体染$c$色之一，则必有某个方向（允许某些特定的斜向）的连线上，全部$n$个小立方体皆同色。换言之：在多人版过$n$关（井字过三关的推广）中，不论玩家人数为何，也不论$n$为何，只要维数足够高，则必有一人先获胜，而不可能出现平局。该定理可推出范德瓦尔登定理。

与范德瓦尔登定理类似的还有舒尔定理：给定任意$c$，总有某个$N$，使得：若将$1,2,\ldots ,N$染成$c$种色，则其中必有两个数$x,y$ ，使得$x,y,x+y$三个数同色。此定理有许多推广，如：雷多定理、雷多－福克曼－桑德斯定理、海恩德曼定理、米利肯－泰勒定理。关于上述结果（及许多其他结果）的参考书有葛立恒、布鲁斯·罗斯柴尔德、乔尔·斯宾塞、绍利莫希·约瑟夫合著的《拉姆齐理论》（Ramsey Theory），该书于2015年曾更新扩展

特点

拉姆齐理论的结果通常有以下两个特点：

非构造性

可能证明了某个结构存在，但却并无给出构造该个结构的方法（除暴力搜索外）。例如，过程中可能采用鸽巢原理，便是非构造性的。

界极大

虽然拉姆齐理论的结果断言充份大的物件必定包含某个指定的结构，但证明经常要求该物件极巨大：常见指数增长甚至阿克曼函数增长的界。对某些小情况，已找到更好的上下界，但一般而言该些界未能改进。一些情况下，该些巨大的界是证明方法所遗留的，而无人知道能否实质改进。另一些情况下，已知任何界都必须异常大，甚至大于任何原始递归函数，例见帕里斯－哈灵顿定理。著名大数葛立恒数也是与拉姆齐理论有关的问题的上界。也有另一意义下巨大的例子：二染色毕氏三元组问题的证明有200 TB长。

定理分类

拉姆齐理论的成果可粗略分为两类：

拉姆齐类

若干定理与拉姆齐定理类似，断言某个大结构中，不论如何分划，都必有一块包含大的子结构，但不能得知该子结构位处何块。

图兰类

有时，某条拉姆齐类定理背后的原因很简单：最大的分块必然包含所求的子结构。此类结果称为密度结果或图兰类结果，得名自图兰定理。著名例子有塞迈雷迪定理（范德瓦尔登定理的图兰类加强）以及黑尔斯－朱威特定理的密度版本。

参见

• 遍历拉姆齐理论
• 极值图论
• 古德斯坦定理
• 巴尔特·伦德特·范德瓦尔登
• 差异理论