Ramsey 定理

$Ramsey$ 定理

​ 这一节是关于鸽巢原理的部分拓展，其实用处并不太大吧

​ 令 $K_n$ 表示为有 $n$ 个点且两两相连的图，或者说 $K_n$ 是一个 $n$ 阶完全图。

​ 而 $K_p \rightarrow K_n,K_m$ 表示对于 $K_n$ 的 $\frac{n(n-1)}{2}$ 条边进行染色（只有两种颜色：红色或蓝色）后，使得无论如何染色都能在 $K_p$ 中找到一个连边全为红色的 $K_n$ 或者连边全为蓝色的 $K_m$。

​ 令 $r(n,m)$ 表示使得 $K_p \rightarrow K_n,K_m$ 成立的最小的 $p$，而这样的数亦被称为 $Ramsey$ 数。

​ 对于 $Ramsey$ 数的存在性予以证明。

​ 我们先对于一些平凡的 $Ramsey$ 数进行证明。

​ 考虑到 $r(n,m)$ 和 $r(m,n)$ 之间是互为相同的。

​ 那么求 $r(2,n)$ 的数值时，发现 $K_2$ 是一条边，所以我们不能使用红色进行染色，则此时的所有边均为蓝色。而当且仅当已染色 $n-1$ 条边时，对于下一条边进行染色时，无论如何都会使得 $K_n \rightarrow K_2,K_n$，所以 $r(2,n)=r(n,2)=n$，即是平凡的 $Ramsey$ 数。

​ 现在，我们考虑对于 $n\geq3$ 且 $m \geq 3$ 的情况时，$r(n,m)$ 的取值。令 $p=r(n-1,m)+r(n,m-1)$，那么令 $R_x$ 表示为 $r(n,m)$ 中与一点 $x$ 相连的红色边的集合，$B_x$ 为 $r(n,m)$ 中与其同一点 $x$ 相连的蓝色边的集合。那么，易知：

$|R_x|+|B_x| = p - 1 = r(n-1,m) + r(n,m-1) -1 \tag{n,m$\geq$3}$

​ 由鸽巢原理易知，总有 $|R_x|\geq r(n-1,m)$ 或者 $|B_x| \geq r(n,m-1)$。

​ 故假设对于 $|R_x| \geq r(n-1,m)$ 成立的情况予以考虑，则令 $q=|R_x|$，所以有 $K_q$ 中包含一个红色的 $K_{n-1}$ 或者是一个蓝色的 $K_m$。继续考虑这两种情况，若存在一个蓝色的 $K_m$，那么 $r(n,m) \leq r(n-1,m)+r(n,m-1)$ 直接成立。否则存在一个红色的 $K_{n-1}$，再将 $x$ 点本身加入其中以形成一个 $K_n$，因为 $x$ 点与 $R_x$ 中的任意一点连边均为红色。同理可证的 $r(n,m-1)$ 如此。

​ 总而言之，$r(n,m) \leq r(n-1,m) + r(n,m-1)$ 成立。所以 $Ramsey$ 数必然存在。

​ 关于如何将两种染色的限制继续拓展到多种染色，这个我还不会，也求教于诸位大佬。