第八章 Ramsey 定理

8.1 独立集和覆盖

(点) 独立集与 (点) 覆盖

点独立集, 点独立数 $\alpha (G)$

设 $G=(V,E)$ 是一个图. $V$ 的一个顶点子集 $V_1$ 称为 $G$ 的一个点独立集, 如果 $V_1$ 中的顶点互不邻接.

$G$ 的一个包含顶点数最多的独立集称为 $G$ 的最大独立集. 最大独立集包含的顶点数, 称为 $G$ 的点独立数 (independence number), 记为 $\alpha (G)$.

点覆盖, 点覆盖数 $\beta (G)$

$V$ 的一个顶点子集 $K$ 称为图 $G=(V,E)$ 的一个点覆盖 (vertex cover), 如果 $E$ 中的每条边至少有一个端点在 $K$ 中.

$G$ 的一个包含顶点数最少的点覆盖称为 $G$ 的最小点覆盖. 最小点覆盖包含的顶点数, 称为 $G$ 的点覆盖数, 记为 $\beta (G)$.

Gallai 恒等式

(Gallai,1959) 对任意不含孤立点的 $n$ 阶图 $G$, 有:

$$\alpha (G)+\beta (G)=n$$

证明: 一方面, 设 $S$ 是 $G$ 的最大点独立集. 因为 $G$ 中每条边的端点最多一个在 $S$ 中, 所以 $G$ 中每条边的端点至少有一个在 $V-S$ 中. 即 $V-S$ 构成 $G$ 的一个点覆盖, 于是有:

$$\beta (G)\le |V-S|=n-\alpha (G)$$

另一方面, 设 $K$ 是 $G$ 的最小点覆盖. 因为 $G$ 中每条边的端点至少有一个在 $K$ 中, 所以 $G$ 中每条边的端点至多有一个在 $V-K$ 中. 即 $V-K$ 构成 $G$ 的一个点独立集, 于是有:

$$\alpha (G)\ge |V-K|=n-\beta (G)$$

由上面两个不等式, 得到:

$$\alpha (G)+\beta (G)=n$$

边独立集与边覆盖

边独立集, 边独立数 ${\alpha }^{\prime }(G)$

若图 $G=(V,E)$ 的一个边子集 $M$ 中的边互不邻接, 则称 $M$ 是一个边独立集 (或匹配). 包含边数最多的边独立集称为 $G$ 的最大边独立集, 其包含的边数, 称为 $G$ 的边独立数,记为 ${\alpha }^{\prime }(G)$.

注: 简单图的一个边独立集实际上就是图的一个匹配, 一个最大边独立集就是其一个最大匹配.

边覆盖, 边覆盖数 ${\beta }^{\prime }(G)$

图 $G=(V,E)$ 的一个边子集 $L$ 称为 $G$ 的一个边覆盖 (edge cover), 如果 $G$ 中的每个顶点均是 $L$ 中某条边的端点. 包含边数最少的边覆盖称为 $G$ 的最小边覆盖 (minimum edge cover), 其包含的边数, 称为 $G$ 的边覆盖数, 记为 ${\beta }^{\prime }(G)$.

Gallai 恒等式

(Gallai,1959) 对任意不含孤立点的 $n$ 阶简单图 $G$, 有:

$${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)=n$$

证明: 一方面, 设 ${\alpha }^{\prime }(G)=k$, 则 $G$ 的最大匹配由 $k$ 条边组成, 且覆盖了 $2k$ 个顶点.

所以, 余下的 $n-2k$ 个顶点至多需要 $n-2k$ 条边就可以被覆盖, 于是 ${\beta }^{\prime }(G)\le k+(n-2k)=n-k$.

于是 ${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)\le k+(n-k)=n$.

另一方面, 设 $L$ 是 $G$ 的一个最小边覆盖, 即 $|L|={\beta }^{\prime }(G)$. 设 $H=G[L]$. 并设 $M$ 是 $H$ 的最大匹配. 用 $U$ 记 $H$ 中的 $M$ 未饱和点的集合. 因 $M$ 是最大匹配, 则 $H[U]$ 不包含边. 从而

$$|L|-|M|=|L-M|\ge |U|=|V(G)|-2|M|$$

故有 $|L|+|M|\ge n$.

又因为 $H$ 是 $G$ 的子图, 所以 $M$ 也是 $G$ 的匹配. 则 ${\alpha }^{\prime }(G)\ge |M|$.

所以 ${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)\ge n$.

由上面两个不等式, 得到: ${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)=n$.

例

确定下图 $G$ 的 $\alpha (G),\beta (G),{\alpha }^{\prime }(G),{\beta }^{\prime }(G)$.

解: 顶点 $2$ 的左右两部分均是 $K_4$, 所以可以推知 $\alpha (G)=2$, 再由 Gallai 恒等式得: $\beta (G)=5$.

又因为 $G$ 的阶数为 $7$, 所以, $G$ 的最大匹配包含的边数不会超过 $3$, 即 ${\alpha }^{\prime }(G)\le 3$;

而在 $G$ 中找出了匹配: $\{16,23,45\}$, 所以 ${\alpha }^{\prime }(G)\ge 3$, 即 ${\alpha }^{\prime }(G)=3$.

再由 Gallai 恒等式: ${\beta }^{\prime }(G)=4$.

二部图的最大点独立集和最小边覆盖

定理 (Kőnig,1916)

设 $G$ 是无孤立点的二部图, 则 $G$ 中最大点独立集包含的顶点数等于最小边覆盖所包含的边数.

证明: 首先由两个 Gallai 恒等式得:

$$\alpha (G)+\beta (G)={\alpha }^{\prime }(G)+{\beta }^{\prime }(G)$$

其次, 由第 5 章中的 Kőnig 定理得: $\beta (G)={\alpha }^{\prime }(G)$.

所以得 $\alpha (G)={\beta }^{\prime }(G)$. 定理得到证明.

8.2 Ramsey 定理

Ramsey 理论的核心可以概括成: 完全的无序是不可能的.

具体的, Ramsey 理论中典型的问题是: 为了保证在某个集合 (或系统) 中有某种性质 (或结构) 一定出现, 这个集合的元素个数应该达到多少?

我们熟悉的鸽笼原理也是 Ramsey 理论的一个例子.

Ramsey 数

★Ramsey 数 $r(m,n)$

设 $k$ 和 $l$ 是两个正整数, 如果存在最小的 $r(k,l)$ 阶的图 $G$, 使得 $G$ 中或者有 $K_k$ 或者有 $l$ 个顶点的独立集, 则称正整数 $r(k,l)$ 为 $(k,l)$ Ramsey (拉姆齐) 数.

对于 $r(5,5)$, 仅知道在 43 (Geoffrey Exoo, 1989) 和 48 (2017 年 McKay 和 Angeltveit 通过计算机验证) 之间.

★用定义直接求 $r(k,l)$

如果用定义直接求 $r(k,l)$:

• 一般是先得到 $r(k,l)\le n$ (一个理想的上界);

• 然后找出一个 $n–1$ 阶完全图 $G$, 说明它既不含红色 $K_k$, 也不含蓝色 $K_l$, 得到 $r(k,l)>n–1$. (或找 $k$ 阶图, 说明它既不包含 $K_k$, 也不包含 $l$ 点独立集)

通过上面的方法得到: $r(k,l)=n$.

例

求:
(1) $r(1,l)$;
(2) $r(2,l)$;
(3) $r(3,3)$.

解:

(1) $r(1,l)=1$. 因为 $1$ 阶图存在 $K_1$.

(2) $r(2,l)=l$. 因为 $l$ 阶图若有边, 则存在 $K_2$; 若无边, 则存在 $l$ 个顶点的独立集.

(3) 一方面: 注意到下图 $K_5$ 中既不包含红色 $K_3$, 也不包含蓝色 $K_3$ ($3$ 点独立集), 所以: $r(3,3)\ge 6$;

另一方面: 可以证明, 任一 $6$ 阶简单图, 或者含有 $K_3$, 或者含有 $3$ 点独立集.

事实上, 设 $V(G)=\{v_1,v_2,\dots ,v_6\}$. 考虑 $v_1$.

情形1: 若 $G$ 中至少有 $3$ 个点与 $v_1$ 邻接. 不失一般性, 设 $v_1$ 与 $v_2,v_3,v_4$ 邻接.

如果 $v_2,v_3,v_4$ 互不邻接, 则它们构成 $G$ 的 $3$ 点独立集; 否则, 显然在 $G$ 中存在 $K_3$.

情形2: 若 $G$ 中至多有 $2$ 个点与 $v_1$ 邻接. 那么在 $G$ 的补图中至少有 $3$ 个顶点与 $v_1$ 邻接. 于是由情形1, $G$ 的补图中或者存在 $K_3$ 或者存在 $3$ 点独立集, 当然在 $G$ 中也就或者存在 $3$ 点独立集或者存在 $K_3$.

所以, $r(3,3)=6$.

Ramsey 数的性质

Ramsey 数的计算很难, 所以研究 Ramsey 数的上下界是该问题的主题. 下面综述一些结果.

定理

Erdős 教授在 1935 年提出如下结论:

对于任意两个正整数 $k$ 和 $l$, 且 $k,l\ge 2$, 有:

$$r(k,l)\le r(k,l-1)+r(k-1,l)$$

并且, 如果 $r(k,l-1)$ 和 $r(k-1,l)$ 都是偶数, 则上面严格不等式成立. 即 $r(k,l)\le r(k,l-1)+r(k-1,l)-1$.

例 [Greenwood and Gleason, 1955]

求:
(1) $r(3,4)$;
(2) $r(3,5)$;
(3) $r(4,4)$.

解:

(1) 由定理, 有: $r(3,4)\le r(2,4)+r(3,3)$.

而 $r(2,4)=4,r(3,3)=6$ 均为偶数. 故有 $r(3,4)\le r(2,4)+r(3,3)-1=9$.

另一方面, 存在 $K_8$ 既不含红色 $K_3$, 也不含蓝色 $K_4$ (如下图).

所以, $r(3,4)=9$.

(2) 由定理, 有: $r(3,5)\le r(2,5)+r(3,4)=5+9=14$.

另一方面可以构造出一个 $13$ 阶图 $G$, 它既不含 $K_3$, 又不含 $5$ 点独立集.

该图是模 $13$ 的三次剩余 $(1,5,8,12)$ 图. 两个顶点 $i,j$ 相差剩余中的数则相邻.

所以, $r(3,5)=14$.

(3) 由定理: $r(4,4)\le r(3,4)+r(4,3)=18$.

另一方面可以构造出一个 $17$ 阶图 $G$. 事实上, 该图是 Paley 图, 模 $17$ 的二次剩余图 (剩余为$1,2,4,8,9,13,15,16$), 它是自补的. Paley 图既不含 $K_4$, 又不含 $4$ 点独立集.

所以, $r(4,4)=18$.

定理

当 $k,l\ge 2$ 时, 有:

$$r(k,l)\le \left(\genfrac{}{}{0ex}{}{k+l-2}{k-1}\right)$$

对角型拉姆齐数

称 $r(k,k)$ 为对角型拉姆齐数 (diagonal Ramsey number).

定理’ (Erdős, Szekeres1935)

当 $k\ge 2$ 时,

$$r(k,k)\le \left(\genfrac{}{}{0ex}{}{2k-2}{k-1}\right)\le 2^{2k-2}\le 4^k$$

定理 (Erdős, 1947)

$$r(k,k)\ge 2^{k/2}$$

证明: 略