拉姆齐理论

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

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

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

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

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

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

与范德瓦尔登定理类似的还有舒尔定理（英语：Schur's theorem）：给定任意${\displaystyle c}$ ，总有某个${\displaystyle N}$ ，使得：若将${\displaystyle 1,2,\ldots ,N}$ 染成${\displaystyle c}$ 种色，则其中必有两个数${\displaystyle x,y}$  ，使得${\displaystyle x,y,x+y}$ 三个数同色。此定理有许多推广，如：雷多定理（英语：Rado's theorem (Ramsey theory)）、雷多－福克曼－桑德斯定理（英语：Rado–Folkman–Sanders theorem）、海恩德曼定理（英语：Hindman's theorem）、米利肯－泰勒定理（英语：Milliken–Taylor theorem）。关于上述结果（及许多其他结果）的参考书有葛立恒、布鲁斯·罗斯柴尔德（英语：Bruce Lee Rothschild）、乔尔·斯宾塞（英语：Joel Spencer）、绍利莫希·约瑟夫（英语：József Solymosi）合著的《拉姆齐理论》（Ramsey Theory），该书于2015年曾更新扩展^[2]

特点

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

非构造性

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

界极大

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

定理分类

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

拉姆齐类

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

图兰类

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

• 遍历拉姆齐理论（英语：Ergodic Ramsey theory）
• 极值图论（英语：Extremal graph theory）
• 古德斯坦定理
• 巴尔特·伦德特·范德瓦尔登（英语：Bartel Leendert van der Waerden）
• 差异理论（英语：Discrepancy theory）