Chặn dưới mũ của Erdős cho số Ramsey

Đặt $n = \lfloor 2^{k/2} \rfloor$. Từ công thức mô-men bậc nhất ở trên, $\mathbb{E}[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$. Nếu ta chỉ ra $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$, thì vì $X$ chỉ nhận giá trị nguyên không âm, phải tồn tại một cách tô 2 màu đạt $X=0$ — nếu không, luôn có $X \ge 1$, buộc $\mathbb{E}[X]\ge 1$. Một cách tô với $X=0$ hoàn toàn không có đồ thị con đầy đủ $k$ đỉnh đơn sắc.

Chặn hệ số nhị thức bằng $\binom{n}{k} \le n^k/k!$, và vì $n \le 2^{k/2}$ nên $n^k \le 2^{k^2/2}$. Thay vào công thức kỳ vọng, $\mathbb{E}[X] \le \dfrac{2^{k^2/2}\cdot 2^{1-\binom{k}{2}}}{k!}$.

Rút gọn số mũ: $\dfrac{k^2}{2} + 1 - \dfrac{k(k-1)}{2} = 1 + \dfrac{k^2 - k^2 + k}{2} = 1 + \dfrac{k}{2}$. Vậy $\mathbb{E}[X] \le \dfrac{2^{1+k/2}}{k!}$, và chỉ cần chỉ ra $k! > 2^{1+k/2}$ với mọi $k \ge 3$.

Kiểm tra điều này bằng quy nạp theo $k$. Cơ sở $k=3$: $3! = 6$ và $2^{1+3/2} = 2^{2.5} \approx 5.657$, và đúng là $6 > 5.657$. Ở bước quy nạp, giả sử $k! > 2^{1+k/2}$ đúng tại $k \ge 3$. Khi đó $(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^{1+k/2}$, và vì $k+1 \ge 4 > \sqrt2$, đại lượng này vượt $\sqrt2 \cdot 2^{1+k/2} = 2^{1+(k+1)/2}$, chính là khẳng định tại $k+1$. Vậy $k! > 2^{1+k/2}$ đúng với mọi $k \ge 3$, cho ta $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$ như mong muốn.

Do đó tồn tại một cách tô 2 màu của $K_n$ không có đồ thị con đầy đủ $k$ đỉnh đơn sắc nào, nên $R(k,k) > n = \lfloor 2^{k/2}\rfloor$. Vì $\lfloor x\rfloor + 1 > x$ với mọi số thực $x$, ta có $R(k,k) \ge \lfloor 2^{k/2}\rfloor + 1 > 2^{k/2}$, chính là $R(k,k) > 2^{k/2}$.