拉姆齐定理表明在二染色中对任意整数 $r$ 一定存在 $n$，使得完全图 $K_n$ 必然包含的同色子完全图$K_s$。
$R(s):=R(s,s)$. 我们已经知道 $R(1)=1$, $R(2)=2$, $R(3)=6$, 以及 $R(4)=18$. 然后寻找确切的拉姆齐数十分困难, 事实上, $R(5)$ 及其以上的确切值仍然没有确定. 因此, 自然的想法就是不断缩小上下界. P. Erdös 在其1947年的文章中开创性的利用概率方法给出第一个下界.
Theorem [3]. The Ramsey number $R(s)$ is bigger than $2^{(s-1)/2}$.
该定理的证明是概率性而非构造性证明。我们选择 $K_n$ 边的一个随机着色。然后我们将得到一个同色完全图$K_s$的概率的一个上界。我们将证明如果我们非常小心地选取 $n$，我们可以令这个概率（严格）小于1。如果这个概率小于1，则必然存在某些着色方式使得不存在同色的 $K_s$。
那么如何选择一个随机着色呢？我们将 $K_n$ 的每条边染为红色或者蓝色，每次染色都是独立事件，且任意一次染色两种颜色的概率为1/2。那么我们得到一个同色的完全图 $K_s$ 的概率如何？利用简单粗暴的估计，我们知道这等于所有使得 $K_s$ 是同色的概率的和。我们可以通过计算 $K_s$ 的所有数量乘以每一个 $K_s$ 是同色的概率。
$K_s$ 的数量显而易见是 $n \choose s$. 那么每一个 $K_s$ 同色的概率为多少？我们知道每条边为红色概率是 1/2，$K_s$ 有 $s\choose 2$ 个边。因此，$K_s$ 是红色的概率是 $2^{-{s\choose 2}}$，因此这个 $K_s$ 同色的概率为 $2^{1-{s\choose 2}}=2\times 2^{-{s\choose 2}}$。
因此，$K_s$ 同色的概率是 ${n\choose s} 2^{1-{s\choose 2}}$. 我们想选择足够大的 n，使得这一概率小于1。如果我们选择 $n=\lfloor{2^{(s-1)/2}}\rfloor$，则我们得到
$$ 2^{1-{s\choose 2}}{n\choose s}\leq 2^{1-{s\choose 2}}\frac{n^s}{s!} < 2^{-s(s-1)/2}2^{s(s-1)/2}=1. $$
这正是我们想要的结果。注意到在 Erdos 最初的证明中，他使用的是计数而非概率，而现在概率是现代的语言。
References
- Wikipedia, Ramsey Number.
- Michael Krivelevich, Topics in Random Graphs, 1.6.1 pp. 8-9, 2010.
- P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294.
- Theorem of the week, Theorem 25: Erdős’s lower bound for the Ramsey numbers.