拉姆齐定理表明在二染色中对任意整数 rr 一定存在 nn,使得完全图 KnK_n 必然包含的同色子完全图KsK_s

R(s):=R(s,s)R(s):=R(s,s). 我们已经知道 R(1)=1R(1)=1, R(2)=2R(2)=2, R(3)=6R(3)=6, 以及 R(4)=18R(4)=18. 然后寻找确切的拉姆齐数十分困难, 事实上, R(5)R(5) 及其以上的确切值仍然没有确定. 因此, 自然的想法就是不断缩小上下界. P. Erdös 在其1947年的文章中开创性的利用概率方法给出第一个下界.

Theorem [3]. The Ramsey number R(s)R(s) is bigger than 2(s1)/22^{(s-1)/2}.

该定理的证明是概率性而非构造性证明。我们选择 KnK_n 边的一个随机着色。然后我们将得到一个同色完全图KsK_s的概率的一个上界。我们将证明如果我们非常小心地选取 nn,我们可以令这个概率(严格)小于1。如果这个概率小于1,则必然存在某些着色方式使得不存在同色的 KsK_s

那么如何选择一个随机着色呢?我们将 KnK_n 的每条边染为红色或者蓝色,每次染色都是独立事件,且任意一次染色两种颜色的概率为1/2。那么我们得到一个同色的完全图 KsK_s 的概率如何?利用简单粗暴的估计,我们知道这等于所有使得 KsK_s 是同色的概率的和。我们可以通过计算 KsK_s 的所有数量乘以每一个 KsK_s 是同色的概率。

KsK_s 的数量显而易见是 (ns)n \choose s. 那么每一个 KsK_s 同色的概率为多少?我们知道每条边为红色概率是 1/2,KsK_s(s2)s\choose 2 个边。因此,KsK_s 是红色的概率是 2(s2)2^{-{s\choose 2}},因此这个 KsK_s 同色的概率为 21(s2)=2×2(s2)2^{1-{s\choose 2}}=2\times 2^{-{s\choose 2}}

因此,KsK_s 同色的概率是 (ns)21(s2){n\choose s} 2^{1-{s\choose 2}}. 我们想选择足够大的 n,使得这一概率小于1。如果我们选择 n=2(s1)/2n=\lfloor{2^{(s-1)/2}}\rfloor,则我们得到

21(s2)(ns)21(s2)nss!<2s(s1)/22s(s1)/2=1.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

  1. Wikipedia, Ramsey Number.
  2. Michael Krivelevich, Topics in Random Graphs, 1.6.1 pp. 8-9, 2010.
  3. P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294.
  4. Theorem of the week, Theorem 25: Erdős’s lower bound for the Ramsey numbers.