Erdős对Ramsey数的指数下界

令 $n = \lfloor 2^{k/2} \rfloor$。由上面一阶矩的计算,$\mathbb{E}[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$。若能证明 $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$,那么由于 $X$ 只取非负整数值,必存在某个2染色使得 $X=0$——否则总有 $X \ge 1$,从而迫使 $\mathbb{E}[X]\ge 1$。满足 $X=0$ 的染色完全不含单色 $k$ 元团。

用 $\binom{n}{k} \le n^k/k!$ 估计二项式系数,且由 $n \le 2^{k/2}$ 得 $n^k \le 2^{k^2/2}$。代入期望公式,$\mathbb{E}[X] \le \dfrac{2^{k^2/2}\cdot 2^{1-\binom{k}{2}}}{k!}$。

化简指数:$\dfrac{k^2}{2} + 1 - \dfrac{k(k-1)}{2} = 1 + \dfrac{k^2 - k^2 + k}{2} = 1 + \dfrac{k}{2}$。于是 $\mathbb{E}[X] \le \dfrac{2^{1+k/2}}{k!}$,因此只需对所有 $k \ge 3$ 证明 $k! > 2^{1+k/2}$。

对 $k$ 用归纳法验证。基础情形 $k=3$:$3! = 6$,$2^{1+3/2} = 2^{2.5} \approx 5.657$,确实 $6 > 5.657$。归纳步骤:设某个 $k \ge 3$ 时 $k! > 2^{1+k/2}$ 成立。那么 $(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^{1+k/2}$,又因 $k+1 \ge 4 > \sqrt2$,此式超过 $\sqrt2 \cdot 2^{1+k/2} = 2^{1+(k+1)/2}$,这正是 $k+1$ 时的结论。故 $k! > 2^{1+k/2}$ 对一切 $k \ge 3$ 成立,由此得到所需的 $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$。

因此存在 $K_n$ 的一个不含单色 $k$ 元团的2染色,故 $R(k,k) > n = \lfloor 2^{k/2}\rfloor$。对任意实数 $x$ 都有 $\lfloor x\rfloor + 1 > x$,所以 $R(k,k) \ge \lfloor 2^{k/2}\rfloor + 1 > 2^{k/2}$,这正是 $R(k,k) > 2^{k/2}$。