Jun 072012
 

Ramsey’s theorem   给定正整数 \(c(\geqslant2), m(\geqslant3)\), 则存在正整数 \(N\), 当 \(n\geqslant N\) 时, 任意 \(c\) 色完全图 \(K_n\)必有单色完全子图 \(K_m\).

这两天读 terence tao的文章” What is good mathematics?”, 里面提到了这个定理. 当然, 很早以前我就学过这个组合中有名的结果, 那时我是一个高中生. 李炯生的书, “数学竞赛中的图论方法”(中国科学技术大学出版社,1992年)有一章是谈这个定理的, 还有一章谈应用. 这书证明了两色的情况, 用的归纳法(Mathematical induction), 和一般的书籍没有不同. 比如, 在这里可以找到一个这样的证明. 李炯生的书给出的实际上就是这个证明的前半部分.

我的证明严重依靠抽屉原理(Pigeonhole principle)(这也难怪, Ramsey’s theorem 本身就是Pigeonhole principle 的推广)不用归纳法. 当然, 我也想不出什么了不起的办法, 说来也只不过是世上任意 \(6\) 人中, 必有\( 3\) 人互相认识或互不认识这个广为人知的结果的流传最广的证明的发扬光大而已:

下面对 \(8\)个人证明必有 \(3\) 人互相认识或互不认识.

\( 2\) 种颜色为\( a,b\).  记这 \( 8\)个人是 \(v_1, v_2, \dotsc, v_8\). 可以认为边 \(v_1v_2, v_1v_3, v_1v_4, v_1v_5 \) 颜色相同, 是 \(c_1, c_1\) 为 \( a\) 或 \(b\) . 边 \(v_2v_3, v_2v_4, v_2v_5 \) 必有两条颜色相同, \(v_2v_3, v_2v_4\) 颜色都是 \(c_2, c_2\) 为 \(a\) 或 \(b\). 下面再看边 \(v_3v_4\) 的颜色, 是 \(c_3, c_3\) 为 \(a\) 或\(b\).

注意 \(c_1, c_2, c_3\) 必有两个相同. 于是不管怎样, \( 2\) 色 \(K_8\)都有单色三角形.

一般情况下的证明也差不多.

\(c\) 种颜色\(t_1, t_2,\dotsc, t_c\).  我们来证明当 \( n\geqslant c^{cm}\) 时, 任意 \(c\) 色完全图 \( K_n\) 必有单色完全子图 \(K_m\).

事实上, 任取顶点 \( v_1\), 以\(v_1\) 为一端点的边至少有 \(c^{mc- 1}\)条是同色的. 设这个颜色是 \( c_1, c_1 \)为 \( t_1, t_2,\dotsc, t_c\) 之一. 只要考虑这 \(c^{mc – 1}\)条边及这些边的 \(c^{mc-1}+1\)个顶点就够了.

设 \(v_1v_2\)是这 \(c^{mc- 1}\)条边中的任意一条. 同理, 以\(v_2\) 为一端点的边至少有 \( c^{mc- 2}\)条是同色的, 设这个颜色是 \(c_2, c_2\) 为\(t_1, t_2,\dotsc, t_c\)之一. 依次类推,  最后得到 以\(v_{mc}\) 为一端点的边至少有 \(1\)条边, 把这 条边颜色记为 \(c_{mc},  c_{mc}\) 为 \(t_1, t_2,\dotsc, t_c \) 之一.

请注意: \(c_1, c_2, \dotsc, c_{mc}\) 中至少有 \( m\) 个相同, 不妨设为 \( c_{i_1}, c_{i_2}, \dotsc, c_{i_m}\) . 考虑 \(v_{i_1}, v_{i_2}, \dotsc, v_{i_m}\), 显然存在单色 \(K_m\).

[本文完成于 2009年 8月 19 日]