拉姆齐数(Ramsey number)

引例.  任意六个人组成一个小组, 小组中或者有三个人互不相识, 或者有三个人互相认识.

使用图的术语,  将六个人视为六个点. 两个人认识则用红边(或实线)相连; 不认识则用蓝边(或虚线)相连. 则总可以找到一个红边三角形或一个蓝边三角形.

图论中将顶点两两连接的图称为完全图, $p$ 个顶点的完全图记为 $K_p$. 于是上面的例子可以叙述为:

对于完全图 $K_6$ 的所有边进行着色, 必存在一个红边 $K_3$ 或一个蓝边 $K_3$.

此时我们记为 $K_6\to (K_3,K_3)$.

一般的, $K_p\to (K_m,K_n)$ 是指对于完全图 $K_p$ 的所有边着色(红色和蓝色), 存在红色完全子图 $K_m$ 或蓝色完全子图 $K_n$.  (这里 $2⩽m,n⩽p$.)

显然, 若 $K_p\to (K_m,K_n)$, 则对所有比 $p$ 大的正整数 $q$, 都有 $K_q\to (K_m,K_n)$.

定义.  给定正整数 $m,n$, 使得 $K_p\to (K_m,K_n)$ 成立的最小正整数 $p$ 被称为关于 $m,n$ 的拉姆齐数(Ramsey number) , 记作 $r(m,n)$.

注: 英国逻辑学家 Frank Ramsey 首先研究了这个问题, 并最终证明了 $r(m,n)$ 有上界. 因此这个数以他的名字命名.

例:  $r(3,3)=6$.

基本性质

Prop 1.  $r(m,n)=r(n,m)$

Pf.  通过交换两种颜色即证明.  事实上, 设 $p=r(m,n)$, 即 $K_p$ 所有边涂色后, 存在红色 $K_m$ 或蓝色 $K_n$. 若将 $K_p$ 中两种颜色对调, 则存在红色 $K_n$ 或蓝色 $K_m$. 由于 $p$ 使得 $K_p\to (K_m,K_n)$ 成立的最小正整数, 因此 $p$ 也是使得 $K_p\to (K_n,K_m)$ 成立的最小正整数. 因此 $r(n,m)=p$.

Prop 2.  $r(m,2)=m$,  $r(2,n)=n$.

Pf.  只需证明 $r(2,n)=n$. 首先 $r(2,n)⩾n$.  若将 $K_n$ 所有边涂为蓝色, 则包含 $K_n$; 若存在某条边是红色, 则包含 $K_2$. 证毕.

称 $r(m,2)$ 和 $r(2,n)$ 为平凡的 Ramsey 数.

参考文献

[1] 殷剑宏  编著 《组合数学》.