Chặn trên Erdős–Szekeres cho số Ramsey

**Bước 1 (tách lân cận của $v$ theo Dirichlet).** Đặt $N = R(s - 1, t) + R(s, t - 1)$ và cố định một đỉnh $v \in V(K_N)$. Phân hoạch $N - 1$ đỉnh còn lại thành $V_R$ (cạnh đỏ tới $v$) và $V_B$ (cạnh xanh tới $v$). Vì $|V_R| + |V_B| = R(s - 1, t) + R(s, t - 1) - 1$, ta buộc phải có $|V_R| \ge R(s - 1, t)$ hoặc $|V_B| \ge R(s, t - 1)$.

Bước 2 (kết luận quy nạp). Nếu $|V_R| \ge R(s - 1, t)$, đồ thị con trên $V_R$ chứa một $K_t$ xanh hoặc một $K_{s-1}$ đỏ ghép với $v$ thành $K_s$ đỏ. Tương tự cho $V_B$.

Bước 3 (chặn nhị thức bằng quy nạp). Cơ sở $R(2, t) = t$ và $R(s, 2) = s$ khớp với $\binom{t}{1}$ và $\binom{s}{s-1}$. Với $s, t \ge 3$, hằng đẳng thức Pascal cho $R(s, t) \le \binom{s + t - 3}{s - 2} + \binom{s + t - 3}{s - 1} = \binom{s + t - 2}{s - 1}$.