Lý thuyết Ramsey

Một đỉnh bất kỳ trong $K_6$ có $5$ đỉnh kề; chia chúng vào $2$ màu thì có ít nhất $3$ đỉnh cùng lớp, và dù giữa $3$ đỉnh đó có cạnh màu ấy hay không thì một tam giác đơn sắc đều xuất hiện.

**Bước 1 (chặn trên $R(3,3) \le 6$).** Chọn một đỉnh $v$ bất kỳ của $K_6$. Có $5$ cạnh nối từ v được tô đỏ hoặc xanh. Theo nguyên lý Dirichlet ($\lceil 5/2 \rceil = 3$), có ít nhất $3$ cạnh cùng màu — giả sử $vu_1, vu_2, vu_3$ đều màu đỏ.

**Bước 2 (chia trường hợp trên $\{u_1, u_2, u_3\}$).** Xét $3$ cạnh nối giữa $\{u_1, u_2, u_3\}$. Nếu có một cạnh nào đó — chẳng hạn $u_1u_2$ — màu đỏ, thì $\{v, u_1, u_2\}$ tạo thành một $K_3$ đỏ. Ngược lại, cả $3$ cạnh $u_1u_2, u_2u_3, u_3u_1$ đều màu xanh, nên chính $\{u_1, u_2, u_3\}$ là một $K_3$ xanh.

**Bước 3 (chặn dưới $R(3,3) > 5$).** Đánh số các đỉnh của $K_5$ bởi $\mathbb{Z}/5\mathbb{Z}$. Tô cạnh $ij$ màu đỏ nếu $i - j \equiv \pm 1 \pmod 5$ và màu xanh nếu $i - j \equiv \pm 2 \pmod 5$. Cả hai lớp màu đều tạo thành chu trình $5$ đỉnh không tam giác, chứng tỏ $R(3,3) > 5$ và do đó $R(3,3) = 6$.

Cố định một đỉnh $v$: hoặc tập kề đỏ của nó đủ lớn để buộc có $K_{s-1}$ đỏ hay $K_t$ xanh, hoặc tập kề xanh của nó đủ lớn để buộc có $K_s$ đỏ hay $K_{t-1}$ xanh.

**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}$.