ラムゼー数に対するエルデシュの指数下界

$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$ が非負整数値しか取らないことから、$X=0$ となる2彩色が存在する——さもなければ常に $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$ 元クリークを持たない $K_n$ の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}$ が得られる。