Ramsey定理

Ramsey(1903~1930)是英国数理逻辑学家,他把鸽巢原理加强形式的推广,得出广义鸽巢原理,也称为Ramsey定理。

Ramsey定理最流行和容易理解的例子:

在6个或更多人中,或者有3个人,他们中的每两个人都互相认识;或者有3个人,他们中的每两个人都彼此不认识。抽象为公式

K6 -> K3, K3     用K6代表六个物体和他们配成的全部15对无序对集合。(画一个图,六个不在同一直线上的点,然后每两个点连线,共有n(n-1)/2个点,图论中的完全图),K3的图是一个三角形。把边涂成红色表示认识,蓝色不认识,则K6的边用红蓝色去涂色,总有一个红K3或蓝K3。

证明:(先画出K6)设K6的边被以 任何 一种方式涂成红色或蓝色。考虑其任一点p接触其余五条边,这五条边的每一条都被涂成红色或蓝色,从加强形式的鸽巢原理(参考上一篇鸽巢原理)可知,这五条边或者至少有三条边是红色或者至少有三条边是蓝色。接触到P的三条边假设是红色的(蓝色同理),设p与这三条边上三点a,b,c相连,只要把abc三点两两相连成三角形就确定了一个红K3。所以可以得到一个红或蓝K3,定理证毕。

另外可以证明K5 -> K3, K3是不成立的。

更一般的Ramsey定理叙述:

如果m>=2 && n >=2 (m,n整数),则存在一个正整数p使得Kp -> Km, Kn.

性质:若Kp->Km,Kn   ,那么对任意q >= p   Kq->Km,Kn也成立。将成立的最小值r(m,n)称为Ramsey数。Ramsey定理断言了数r(m,n)的存在性。以上证明了r(3,3) = 6,且有r(m,n) = r(n,m), r(2,n) = n。

还有一些内容略去,数学符号实在不会打。参考书目《Introductory Combinatorics》by Richard A.Brualdi.

原文地址:https://www.cnblogs.com/PegasusWang/p/2870780.html