Ramsey 定理

Ramsey 定理说规模足够大后，任意染色都无法维持完全无序：某个颜色中必出现指定的完全子结构。它不是声称随机染色“通常”有规则，而是对最恶意的染色也成立。Ramsey 数的困难在于同时给出上界的必然性证明和下界的规避染色，两边往往相距很大。

经典结论是 $R(3,3)=6$。定理主要保证存在性，通常不给紧确阈值；多色、超图与无限版本需要另行表述。

$R(3,3)=6$：六人中把认识关系染红、不认识染蓝，任取一人，其余五条关联至少三条同色；在这三人间若有相同颜色边便成同色三角形，否则它们彼此全为另一色。五边形的边染红、对角线染蓝没有单色三角形，说明五人不够。定理要求宿主是完全图，因为每一对都必须被赋一种颜色。

完全图公理库完全图Complete graph每一对不同顶点都恰有一条边相连的有限简单无向图。的边染色公理库图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。产生不可避免的单色团公理库团与独立集Clique · Independent set · 团 · 独立集顶点集内部的边关系分别达到两两全有与两两全无时形成的两类结构。；把一种颜色视为边、另一种视为补图中的边，也可将结论读成大团与大独立集必居其一。有限性依赖鸽巢式公理库鸽巢原理Pigeonhole principle · Dirichlet's box principle把多于 n 个对象放入 n 个容器时，至少一个容器包含两个对象。递归，概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。则常给 Ramsey 数下界。逻辑、数论与计算机科学中的 Ramsey 型定理都在寻找“足够大有限结构中的有序子结构”。