確率的方法

これにより、事象同士がどう相互作用するかを一切気にすることなく、個々の確率を一つずつ足し合わせるだけでカウントの平均を計算できる——確率的方法において最も役立つ近道である。

$X = \sum_{i=1}^m \mathbb{1}[A_i]$ と書く。ここで $\mathbb{1}[A_i]$ は $A_i$ が起これば $1$、そうでなければ $0$ である。期待値はそれ自体、結果を確率で重み付けした和(または積分)として定義され、この和は有限個の確率変数について常に加法的である——これは変数が独立かどうかに関わらず成り立つ。なぜなら期待値の加法性は独立性を一切使わず、同じ確率測度の上で足し合わせているという事実だけを使うからである。

形式的には、有限和の期待値の加法性により $\mathbb{E}[X] = \mathbb{E}\left[\sum_{i=1}^m \mathbb{1}[A_i]\right] = \sum_{i=1}^m \mathbb{E}[\mathbb{1}[A_i]]$ である。

最後に、任意の指示変数について $\mathbb{E}[\mathbb{1}[A_i]] = 1 \cdot \Pr[A_i] + 0 \cdot \Pr[\overline{A_i}] = \Pr[A_i]$ が成り立つ。これを和に代入すると、$A_i$ 同士の関係について何の仮定もなしに、まさに $\mathbb{E}[X] = \sum_{i=1}^m \Pr[A_i]$ が得られる。

$k$ が大きくなるにつれ、$n$ 頂点グラフの $k$ 元部分集合の数は $n$ の多項式でしか増えないが、特定の部分集合が単色である確率は $k$ に関して二重指数的に縮小する。この二つの速度のバランスにより、$n$ が $k$ に対して指数的に大きくても単色クリークの期待個数は $1$ 未満に保たれることが分かる。これは人手で構成されたどの例よりもはるかに良い。

$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}$ が得られる。