ラムゼー数に対するエルデシュ=セケレシュの上界

**ステップ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)$ が成り立つ。

ステップ2(帰納的結論)。 $|V_R| \ge R(s - 1, t)$ ならば、$V_R$ 上の部分グラフは青の $K_t$、または $v$ と合わせて赤の $K_s$ をなす赤の $K_{s-1}$ を含む。$V_B$ についても対称的に成り立つ。

ステップ3(帰納法による二項係数上界)。 基底 $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}$ となる。