1. Ramsey 理论

这一讲回顾图论中的 Ramsey 定理, 并介绍一些相关结果. 首先陈述这个定理.

定理 1.1 (Ramsey). 对任意正整数 $s$, $t$, 存在正整数 $N$, 使得完全图 $K_N$ 的任意二染色 (下文中均指红蓝二染色) 必包含红色 $K_s$ 或蓝色 $K_t$. 这样的最小的正整数 $N$ 记为 $R(s,t)$.

约定 1.2. 对 $G\supseteq H$, 在 $G$ 的一种边染色中, 称图 $H$ 为某种颜色的, 指 $H$ 的边均为这种颜色.

证明. 我们对 $s+t=n$ 归纳. $n=2$ 时结论显然. 假设命题对 $n-1$ 成立, 我们来看 $n$ 的情况. 设 $n=R(s-1,t)+R(s,t-1)$. 任取 $K_n$ 中的一个点 $A$, 并以 $R$ 记与 $A$ 以红边相连的点组成的集合, $B$ 记与 $A$ 以蓝边相连的点组成的集合. 那么, 若 $|R|\ge R(s-1,t)$, 由归纳假设, 这 $n$ 个点诱导的子图包含红色 $K_{s-1}$ 或蓝色 $K_t$. 若为后者, 则命题已经得证, 若为前者, 则这个 $K_{s-1}$ 加上点 $A$ 构成一个红色 $K_s$, 此时命题依然得证. $|B|\ge R(s,t-1)$ 的情况同理. 而 $|R|+|B|+1=n=R(s-1,t)+R(s,t-1)$, 故上述两种情况至少有一种发生, 结论得证.

$\square$

由上述证明易得

推论 1.3.

•	对任意正整数 $s,t\ge 2$, $R(s,t)\le R(s,t-1)+R(s-1,t)$.
•	$R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$. 特别地, 有 $R(k,k)\le \left(\genfrac{}{}{0ex}{}{2k-1}{k-1}\right)\le 4^k$.

将多种颜色合并成一种颜色, 反复运用 Ramsey 定理, 容易得出下面的结论:

推论 1.4 (一般形式的 Ramsey 定理). 对任意正整数 $s_1,s_2,\dots ,s_r$, 存在正整数 $N$, 使得 $n\ge N$ 时, 对于完全图 $K_N$ 的任意 $r$ 染色, 我们总能找到某个 $i$ 和第 $i$ 色的 $K_{s_i}$. 这样的最小的正整数 $N$ 记为 $R(s_1,s_2,\dots ,s_r)$.

接下来介绍 Ramsey 定理的一个应用.

定理 1.5 (Schur). 对任意正整数 $k$, 存在正整数 $N$, 使得对 $1,2,\dots ,N$ 的任意 $k$ 染色, 总存在同色的三个数 $x,y,z$, 满足 $x+y=z$.

证明. 我们证明 $N=R(3,3,\dots ,3)$ ( $k$ 个 $3$) 符合条件. 对 $1,2,\cdots ,N$ 的一个 $k$ 染色, 我们对 $K_N$ 按如下方式染色: 连接顶点 $i$, $j$ 的边, 染 $|i-j|$ 所对应的颜色.

由 Ramsey 定理, $K_N$ 中必然存在同色三角形. 设存在正整数 $i<j<k$ 使得 $|i-j|$, $|j-k|$, $|k-i|$ 同色, 此时 $|j-k|+|i-j|=|k-i|$, 故 $(x,y,z)=(k-j,j-i,k-i)$ 满足条件.

$\square$

由 Schur 定理, 我们可以得到

推论 1.6. 对于任意正整数 $n$, 总存在正整数 $N$, 使得对于任意素数 $p\ge N$, 我们总能找到 $x,y,z\in (\mathbb{Z}/p{)}^{\times }$, 使得$$x^n+y^n=z^n.$$

证明. 记 $G=\{x^n:x\in (\mathbb{Z}/p{)}^{\times }\}$, 则 $G$ 是 $(\mathbb{Z}/p{)}^{\times }$ 的子群. 设 $(\mathbb{Z}/p{)}^{\times }/G$ 的代表元为 $a_1,a_2,\dots ,a_l$, 则 $l\le n$. 我们构造 $\{1,2,\dots ,p\}$ 上的一个 $l$ 染色: 若 $x\in a_{i}G$, 则将 $x$ 染为第 $i$ 色. 那么, 由 Schur 定理, 存在正整数 $N$, 使得 $p\ge N$ 时一定存在同色的 $x,y,z$ 满足 $x+y=z$. 这样就存在 $X,Y,Z\in (\mathbb{Z}/p{)}^{\times }$ 满足$$a_i{X}^n+a_i{Y}^n=a_i{Z}^n,$$即$$X^n+Y^n=Z^n.$$

$\square$

Ramsey 定理也能推广至超图.

定理 1.7. 对任意正整数 $k,n_1,n_2,\cdots ,n_r$, 存在正整数 $N$, 满足: 对于任意 $N$ 元集合 $S$ 和 $S$ 上所有 $k$ 元子集的 $r$ 染色 $\chi$, 总存在正整数 $t\le r$ 和 $S$ 的 $n_t$ 元子集 $K$, $K$ 的所有 $k$ 元子集均为 $t$ 号色. 这样的最小的正整数 $N$ 记为 $R^k(r,n_1,n_2,\cdots ,n_r)$.

注 1.8. 超图 $H$ 是指一个对 $(X,E)$, 其中 $X$ 为集合, 称为顶点集, $E\subseteq P(X)$ 称为边集. 当 $E$ 中的集合均为二元集时, 它就是图. 因此超图就是图的一种推广. 这样就容易看出本定理即 Ramsey 定理在超图上的推广. 特别地, 当 $E$ 中的所有集合均为 $k$ 元集时, 称 $H$ 为 $k$-一致的.

证明. 显然我们只用讨论 $r=2$ 和 $n_k$ 均相等的情况. 以下我们设 $S$ 为 $\mathbb{N}$ 的子集, 并简记 $R^k(n,n)=R^k(n)$. 我们对 $k$ 归纳证明该命题. $k=0$ 时命题成立. 设 $k-1$ 的情况命题成立, 我们考虑 $k$ 的情况.

我们证明下述结论: 对任意正整数 $p\le q$, 存在正整数 $N$, 使得对于任意 $N$ 元集合 $S$ 和 $S$ 上所有 $k$ 元子集的 $r$ 染色 $\chi$, 总存在 $S$ 中的 $q$ 元子集 $Y$, 使得 $Y$ 中的一个 $k$ 元子集若含 $Y$ 中的最小的 $p$ 个元素之一, 则 $Y$ 的颜色仅由 $Y$ 最小的元素决定. 若我们证明了这个结论, 取 $p=q=2n-1$, 注意到这 $2n-1$ 个元素必有 $n$ 个决定相同的颜色, 这 $n$ 个元素就满足要求.

我们再对 $p$ 实行归纳法. $p=0$ 时命题成立. 设 $p-1$ 的情况命题成立, 我们考虑 $p$ 的情况. 取 $q^{\prime }=R^{k-1}(q)+q$. 由归纳假设, 存在 $S$ 中的 $q^{\prime }$ 元子集 $Y$, 使得 $Y$ 中的一个 $k$ 元子集若含 $Y$ 中的最小的 $p-1$ 个元素之一, 则 $Y$ 的颜色仅由 $Y$ 最小的元素决定. 设 $Y$ 中第 $p$ 小的元素为 $t$, 并考虑 $Y$ 去掉最小的 $p$ 个元素后得到的集合 $Y^{\prime }$ 上的 $k-1$ 元集的染色 ${\chi }^{\prime }:{\chi }^{\prime }(X)=\chi (X\cup \{t\})$. 由归纳假设, $Y^{\prime }$ 中存在一个 $q$ 元子集, 任意 $k-1$ 元子集均同色. 那么, 此时易于验证 $Y^{\prime }$ 并上 $Y$ 最小的 $p$ 个元素就满足要求. 结论得证.

$\square$

现在我们开始介绍 Ramsey 数估计相关的一些结论. 各种 Ramsey 数估计一直是图论中的一个重要问题. 例如, 2020 年 Ashwin Sah 关于对角 Ramsey 数的改进$$R(k+1,k+1)\le \exp (-c{\ln }^{2}k)\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$$就被认为是该年组合数学界最重要的结果之一. 我们接下来简单介绍 Ramsey 数估计的一些传统理论.

关于 Ramsey 数估计, 我们将使用的主要手法为概率方法. 一般来说, 只要构建一个合适的概率空间, 并证明一个事件发生的概率为正, 就能证明这个事件非空. 以下结果是经典的:

定理 1.9. $$R(k,k)>2^{\lfloor k/2\rfloor }.$$

证明. 记 $n=2^{\lfloor k/2\rfloor }$. 考虑 $K_n$ 的随机二染色. 对 $K_n$ 顶点集的 $k$ 元子集 $R$, $R$ 诱导的子图同色的概率为 $2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. $R$ 共有 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 种选择, 故存在同色 $K_k$ 的概率不大于$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}<\frac{2^{1+k/2}}{k!}\cdot \frac{n^k}{2^{k/2}}<1.$$因此, $K_n$ 存在一种染色使得没有同色 $K_k$, 即 $R(k,k)>n$.

$\square$

这个简单的例子向我们阐释了概率方法运作的原理. 我们并没有构造出一个符合条件的染色, 而是通过计算概率, 非构造地证明了这种染色的存在性. 不过, 由于概率方法通常选取足够多的对象来估计, 其放缩出来的界往往不是精确的.

在刚刚的估计中, 我们直接考察了所有完全满足条件的染色. 不过, 如果我们将一些具有 “瑕疵” 的染色纳入计算, 再对这些染色做些处理, 可能可以得到更好的结果.

定理 1.10. 对任意正整数 $n$, $$R(k,k)>n-\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}.$$

证明. 考虑 $K_n$ 的随机二染色. 根据上一个定理的证明, 我们知道同色 $K_k$ 的期望个数为 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$, 因此存在一种染色使得同色的 $K_k$ 个数不超过这个数. 我们从每个同色的 $K_k$ 中各去掉一个顶点 (可能重复), 剩下的顶点产生的诱导子图就不存在同色的 $K_k$, 即证得命题.

$\square$

取 $n\sim e^{-1}k{2}^{k/2}(1-o(1))$, 通过简单的估计, 我们可以得到$$R(k,k)>\frac{1}{e}(1+o(1))k{2}^{k/2}.$$

刚才使用的方法称为变易法. 这种方法先考虑更一般的结构, 然后再进行一些处理, 得到我们需要的结构. 它尽管非常朴素, 然而通过使用更深刻的概率工具, 往往能够得到很强的结果.

在刚刚的证明中, 我们考察了 $K_n$ 所含的每一个 $K_k$ 同色的概率, 并作最朴素的概率估计. 然而, 由于 $n$ 远大于 $k$, 有许多 $K_k$ 互不相交, 那么它们同色这些事件独立, 因此我们刚刚的放缩显得没那么有力. 利用下面的 Lovász 局部引理, 我们可以给出一个新的估计.

定义 1.11. 对一族事件 $B_1,B_2,\dots ,B_n$, 以及顶点集为 $\{1,2,\cdots ,n\}$ 的图 $G$, 如果对任意 $i$, 任意由一些与 $i$ 不相邻的点构成的集合 $S$, $B_i$ 和 ${\bigwedge }_{j\in S}{B}_j$ 都无关, 则称 $G$ 为这族事件的相关图.

定理 1.12 (Lovász). 设图 $G$ 为事件 $B_1,B_2,\dots ,B_n$ 的相关图. 若存在实数 $x_1,x_2,\dots ,x_n\in (0,1)$, 满足对任意正整数 $i$, $$\mathbb{P}(B_i)\le x_i\prod _{j\in N(i)}(1-x_j),$$其中 $N(\cdot )$ 表示邻域. 则$$\mathbb{P}\left(\underset{i=1}{\overset{n}{\bigwedge }}\overline{B_i}\right)\ge \prod _{i=1}^n(1-x_i)\ge 0.$$

证明. 我们先指出: 对于 $\{1,2,\cdots ,n\}$ 的任意子集 $S$, $$\begin{array}{r}\mathbb{P}\left(B_i|\underset{j\in S}{\bigwedge }\overline{B_j}\right)\le x_i.\end{array}$$

对 $|S|$ 归纳证明之. $|S|=0$ 时平凡. 若命题对 $|S|\le k$ 成立, $|S|=k+1$ 时, 记 $S_1=S\cap N(i)=\{i_1,\dots ,i_m\}$, $S_2=S\setminus S_1$. 则$$\begin{array}{rl}\mathbb{P}\left(B_i|\underset{j\in S}{\bigwedge }\overline{B_j}\right)& =\mathbb{P}\left(B_i|\underset{j\in S_1}{\bigwedge }\overline{B_j}\wedge \underset{j\in S_2}{\bigwedge }\overline{B_j}\right)=\frac{\mathbb{P}\left(B_i\wedge {\bigwedge }_{j\in S_1}\overline{B_j}|{\bigwedge }_{j\in S_2}\overline{B_j}\right)}{\mathbb{P}\left({\bigwedge }_{j\in S_1}\overline{B_j}|{\bigwedge }_{j\in S_2}\overline{B_j}\right)}\\ & \le \frac{\mathbb{P}\left(B_i|{\bigwedge }_{j\in S_2}\overline{B_j}\right)}{\mathbb{P}\left({\bigwedge }_{j\in S_1}\overline{B_j}|{\bigwedge }_{j\in S_2}\overline{B_j}\right)}=\frac{\mathbb{P}(B_i)}{\mathbb{P}\left({\bigwedge }_{j\in S_1}\overline{B_j}|{\bigwedge }_{j\in S_2}\overline{B_j}\right)}\\ & \le \frac{x_i{\prod }_{j\in N(i)}(1-x_j)}{\mathbb{P}\left({\bigwedge }_{j\in S_1}\overline{B_j}|{\bigwedge }_{j\in S_2}\overline{B_j}\right)}=\frac{x_i{\prod }_{j\in N(i)}(1-x_j)}{{\prod }_{s=1}^m\mathbb{P}\left(\overline{B_{i_s}}|{\bigwedge }_{j\in S_2}\overline{B_j}\wedge {\bigwedge }_{r=1}^{s-1}\overline{B_{i_r}}\right)}\\ & \le \frac{x_i{\prod }_{j\in N(i)}(1-x_j)}{{\prod }_{s=1}^m(1-x_{i_s})}=\frac{x_i{\prod }_{j\in N(i)}(1-x_j)}{{\prod }_{j\in S_1}(1-x_j)}=x_i\prod _{j\in N(i)\setminus S_1}(1-x_j)\le x_i.\end{array}$$

再证明定理本身. 此时$$\begin{array}{r}\mathbb{P}\left(\underset{i=1}{\overset{n}{\bigwedge }}\overline{b_i}\right)=\prod _{i=1}^n\mathbb{P}\left(\overline{B_i}|\underset{j=1}{\overset{i-1}{\bigwedge }}\overline{B_j}\right)=\prod _{i=1}^n\left(1-B_i|\underset{j=1}{\overset{i-1}{\bigwedge }}\overline{B_j}\right)=\prod _{i=1}^n(1-x_i)>0.\end{array}$$即定理成立.

$\square$

Lovász 局部引理有以下显然推论:

推论 1.13. 给定一族事件 $B_1,B_2,\dots ,B_n$. 已知 $B_i$ 发生的概率均小于等于 $p$, 且每个 $B_i$ 均至多与 $d$ 个其他的事件相关. 若 $ep(d+1)\le 1$, 则 $B_i$ 均不发生的概率为正.

接下来利用 Lovász 局部引理来给出 $R(k,k)$ 的一个估计.

定理 1.14. $$R(k,k)>\frac{\sqrt{2}}{e}(1+o(1))k{2}^{k/2}.$$

证明. 对于任意正整数 $n$, 将 $K_n$ 随机二染色. 对 $K_n$ 顶点集的每个 $k$ 元子集 $S$, 考虑 $S$ 同色这一事件 $A_S$. 则 $\mathbb{P}(A_S)=2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$, 且每个 $A_S$ 最多和 $d=\left(\genfrac{}{}{0ex}{}{k}{2}\right)\left(\genfrac{}{}{0ex}{}{n}{k-2}\right)$ 个其他的 $A_T$ 相关 ($|S\cap T|\ge 2$ 时才相关.) 由以上推论, $ep(d+1)\le 1$ 时存在一种染色使得 $A_i$ 均不发生, 即 $R(k,k)>n$. 简单估计即可证得结论.

$\square$

值得注意的是, 我们以上所述的技术不止适用于 $R(k,k)$, 也适用于一般的 $R(k,\ell )$. 例如, 我们可以用 Lovász 局部引理证明, 存在正实数 $c$, 使得对任意正整数 $k$, 均有 $R(3,k)\ge c\frac{k^2}{{\ln }^{2}k}$.

最后, 我们再看一个极其精妙地运用概率方法的例子. 这个例子通过构造一种非常特殊的结构, 给出了关于 $R(3,k)$ 上界的一个精确刻画.

定理 1.15. 存在正实数 $c_1$, 使得对任意正整数 $k$, $$R(3,k)\le c_1\frac{k^2}{\ln k}.$$

证明. 我们证明 $c_1=8$ 满足条件. 为此只需证, 若图 $G(V,E)$ 不含三角形, 且顶点数 $n$ 大于 $8\frac{k^2}{\ln k}$, 则必有 $k$ 个点两两不相邻, 即 $\alpha (G)\ge k$. 由于 $G$ 中不存在三角形, 故若 $G$ 存在一个顶点 $v$ 度数大于等于 $k+1$, 则 $v$ 的邻居中存在 $k$ 个点两两不相邻, 此时已经证得命题. 下设 $G$ 的每个点的度数均小于等于 $k$.

$k\le 16$ 时, 利用平凡的估计 $\alpha (G)(k+1)\ge n$ 即证. 若 $k>16$, 我们从 $G$ 的所有独立集中随机取一个集合 $W$. 对于 $G$ 的任意顶点 $v$, 定义随机变量$$X_v=\{\begin{array}{ll}|N(v)\cap W|,& v\notin W;\\ k,& v\in W.\end{array}$$固定 $W$, 计算$$\begin{array}{r}\sum _{v\in V}{X}_v=\sum _{v\in W}k+\sum _{v\notin W}{X}_v=k|W|+\sum _{v\notin W}|N(v)\cap W|=k|W|+\sum _{v\in W}|N(v)|\le 2k|W|.\end{array}$$

因此, 为证存在 $W$ 使得 $|W|\ge k$, 只需证$$\mathbb{E}\left(\sum _{v\in V}{X}_v\right)\ge 2k^2,$$即证对任意顶点 $v$, 均有 $\mathbb{E}(X_v)\ge \frac{\ln k}{4}$. 注意到 $X_v$ 的取值只与 $W$ 和 $\{v\}\cup N(v)$ 的交有关, 因此, 记 $H$ 为 $G$ 在 $V\setminus (N(v)\cup v)$ 上的诱导子图, 我们只需证, 对 $H$ 中任意独立集 $S$ 均有$$\mathbb{E}(X_v\mid W\cap V(H)=S)\ge \frac{\ln k}{4}.$$

记 $|N(v)|=x$. 由于 $N(v)$ 中的点两两不相邻, 因此 $S$ 固定后, $W$ 恰有 $2^x+1$ 种可能: $S\cup \{v\}$, 或是 $S$ 并上 $N(v)$ 的一个子集. 对于前者, $X_v$ 的期望为 $\frac{k}{2^x+1}$; 对于后者, $X_v$ 的期望为 $\frac{x{2}^{x-1}}{2^x+1}$. 因此只需证明, 对任意正整数 $x$, $$\frac{k}{2^x+1}+\frac{x{2}^{x-1}}{2^x+1}\ge \frac{\ln k}{4},$$求导结合 $k\ge 16$ 易证.

$\square$

这里通过巧妙地构造随机变量 $X_v$ 作桥梁进行概率估计解决了问题. 1995 年 Jeong Han Kim 证明了上述界的阶是最佳的, 即存在正实数 $c_2$, 使得对任意正整数 $k$,$$R(3,k)\ge c_2\frac{k^2}{\ln k}.$$

术语翻译

变易 • 英文 alteration

Lovász 局部引理 • 英文 Lovász local lemma

相关图 • 英文 dependency graph