拉姆齐数一个下界的概率证明

拉姆齐定理表明在二染色中对任意整数 $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

  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.
Wenchao Zhang
Wenchao Zhang
PhD Student in Mathematics

My research interests include ring and algebra, algebraic geometry and some combinatorics.

Related