拉姆齐数的埃尔德什—塞克雷斯上界

**第一步(按抽屉原理划分 $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}$。