拉姆齐理论

$K_6$ 中任一顶点有 $5$ 个邻点;分成 $2$ 类则至少有 $3$ 个同类,无论这 $3$ 个顶点之间是否有该色边,都会产生单色三角形。

**第一步(上界 $R(3,3) \le 6$)。** 任取 $K_6$ 的一个顶点 $v$。与 v 关联的 $5$ 条边染成红色或蓝色。由抽屉原理($\lceil 5/2 \rceil = 3$),至少有 $3$ 条边同色——不妨设 $vu_1, vu_2, vu_3$ 全为红边。

**第二步(对 $\{u_1, u_2, u_3\}$ 分类讨论)。** 考察 $\{u_1, u_2, u_3\}$ 内部的 $3$ 条边。若其中有一条——如 $u_1u_2$——为红边,则 $\{v, u_1, u_2\}$ 构成红色 $K_3$;否则 $u_1u_2, u_2u_3, u_3u_1$ 这 $3$ 条边全为蓝边,于是 $\{u_1, u_2, u_3\}$ 本身构成蓝色 $K_3$。

**第三步(下界 $R(3,3) > 5$)。** 用 $\mathbb{Z}/5\mathbb{Z}$ 标记 $K_5$ 的顶点。当 $i - j \equiv \pm 1 \pmod 5$ 时将边 $ij$ 染红,当 $i - j \equiv \pm 2 \pmod 5$ 时染蓝。两种颜色类都构成不含三角形的 $5$ 元环,从而 $R(3,3) > 5$,证得 $R(3,3) = 6$。

固定顶点 $v$:要么其红邻域足够大迫使出现红色 $K_{s-1}$ 或蓝色 $K_t$;要么其蓝邻域足够大迫使出现红色 $K_s$ 或蓝色 $K_{t-1}$。

**第一步(按抽屉原理划分 $v$ 的邻域)。** 令 $N = R(s - 1, t) + R(s, t - 1)$,固定顶点 $v \in V(K_N)$。将其余 $N - 1$ 个顶点划分为 $V_R$(到 $v$ 为红边)与 $V_B$(到 $v$ 为蓝边)。由于 $|V_R| + |V_B| = R(s - 1, t) + R(s, t - 1) - 1$,必有 $|V_R| \ge R(s - 1, t)$ 或 $|V_B| \ge R(s, t - 1)$。

第二步(归纳推论)。 若 $|V_R| \ge R(s - 1, t)$,则 $V_R$ 上的子图含蓝色 $K_t$,或含与 $v$ 合并成红色 $K_s$ 的红色 $K_{s-1}$。对 $V_B$ 同理。

第三步(归纳证明二项式上界)。 归纳奠基 $R(2, t) = t$ 与 $R(s, 2) = s$ 分别等于 $\binom{t}{1}$ 与 $\binom{s}{s-1}$。当 $s, t \ge 3$ 时,由帕斯卡恒等式得 $R(s, t) \le \binom{s + t - 3}{s - 2} + \binom{s + t - 3}{s - 1} = \binom{s + t - 2}{s - 1}$。