##### 拉姆齐定理 - 拉姆齐定理 - **拉姆齐定理**表示任何大的结构中都必然包含一个子结构. 最基本的内容是, 给定一个足够大的[[图]], 无论如何对图的边进行着色, 必定存在一个单色的完全子图. 对于任意[[整数]] $r,s\geq 1$, 存在一个最小的正整数 $R(r,s)$ 称为**拉姆齐数**, 使得对任何 $R(r,s)$ 个顶点的[[完全图]] $K_n$​ 的边进行红蓝两色染色, 必然存在一个红色的 $r$ 顶点完全子图 $K_r$, 或一个蓝色的 $s$ 顶点完全子图 $K_s$. 拉姆齐定理还可延伸到无穷图和超图 - 对称性, $R(m, n) = R(n, m)$ - 递推不等式, $R(m, n) \leq R(m-1, n) + R(m, n-1)$, $m,n \ge 2$ >[!example]- 拉姆齐定理 > - $R(3,3)=6$ > - 在一个 $6$ 个顶点的完全图中, 无论如何将边着色成两种颜色, 总是能够找到一个大小为 $3$ 的单色完全子图