突然的自我伍佰-这次

第二节：Ramsey问题与Ramsey数
1958年6~7月号美国《数学月刊》 上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个
互相认识或3人互相不认识。”这 就是著名的Ramsey问题。
以6个顶点分别代表6个人，如果两人相识，则在相应的两顶间连一红 边，否则在相应的两顶点间连一蓝
边，则上述的Ramsey问题等价于下面的命题：
命题1.3.1 对6个顶点的完全图
K
6
任意进行红、蓝两边着色，都存 在一个红色三角形或一个蓝色三角形。
证明 设

1
,

2
,

3
,

4
,

5
,

6
是
K
6
的6个顶点，

1
与

2
,

3
,

4
,

5
,

6
所连的5条边着红色或蓝色。由鸽巢
原理知， 其中至少有

3
条边同色，不妨设

1
与
< br>2
,

3
,

4
所连的3条边均为红色，如 图1.3.1所示。
2
若

2
,

3
,< br>
4
间有一条红边，不妨设为

2

3
，则


1

2

3
是一红色三角形。否则，

2
,

3
,

4
间均为蓝边， 即

5




2

3

4
是一蓝色三角形。
类似于命题1.3.1，还有如下的命题1.3.2~命题1.3.4：




命题1.3.2 对6个顶点的完全图
K
6
任意进行红、蓝两边着色，都至少有两个同色三角形。
证明 设

1
,

2
,

3< br>,

4
,

5
,

6
是< br>K
6
的6个顶点，由命题1.3.1知，对
K
6
任意进行红、 蓝两边着色都有一个
同色三角形，不妨设


1

2

3
是红色三角形，以下分各种情况来讨论：
（1）若

1,

2
,

3
,

4
,
5
,

6
均为蓝边，如图1.3.2所示，则若
< br>4
,

5
,

6
之间有一蓝边，不妨设为< br>
4
,

5
，则


1

4

5
为蓝色三角形；否则，


4
< br>5

6
为红色三角形。

（2）若

1
,

2
,

3
,

4
,

5
,

6
中有一红边，不妨设

1
,
4
为红边，此时若边

2

4
,

3

4
中有一条红边，不妨设

3

4< br>是红边，则


1

3

4
是一红 色三角形，见图1.3.3。
以下就

2

4
,

3

4
均为蓝边的情况对与

4
相关联的边的颜 色进行讨论：
（i）若

4

5
,

4

6
中有一蓝边，不妨设

4
,

5为蓝边，如图1.3.4所示。此时，若

2

5
,

3

5
均为红边，则


2

3

5
是红色三角形；否则，


2

4< br>
5
或


3

4

5< br>是蓝色三角形。
（ii）若

4

5
,

4

6
均为红边，见图1.3.5。此时，若

1
,

5
,

6
之间有一条红边，不妨设

1
,

5
为红边，则


1

4

5
为红色三角形；否则，


1

5< br>
6
为蓝色三角形。
由以上对各种情况的讨率知，对
K
6< br>的任意红、蓝两边着色均有两个同色三角形。
命题1.3.3 对10个顶点的完全图
K
10
任意进行红、蓝两边着色，都或者有一红色
K
4
，或者有一 蓝色
K
3
。
证明 设
a
是
K
10的一个顶点，与
a
相关联的9条边用红、蓝两色着色，由鸽巢原理知，这9条边中要么有6条红边，要么有4条蓝边。类似于前面两个命题的分析证明过程可以得出结论，具体分析过程见图1.3 .6。

命题1.3.4 对9个顶点的完全图
K
9
任意 进行红、蓝两边着色，都或者有一个红色
K
4
，或者有一蓝色
K
3< br>。
证明 在
K
9
中，如果与每个顶点关联的红边均为5条，因为一 条红边连着两个顶点，所以
K
9
中应有
5945
条边，它不是整数 ，所以不成立。故必有一个顶点关联的红边数不为5，设此顶点为
a
，则与
a

22
关联的红边数至少为6或至多为4。
1.3.2 Ramsey数
从1..3.1小节的讨论中可以归纳出如下的一般性定义：对于任意给定的两个正整数
a
与< br>b
，如果存在最小
的正整数
r(a,b)
，使得当
Nr(a ,b)
时，对
K
N
中均有红色
K
a
或蓝色
K
b
，则
r(a,b)
称为Ramsey数。
由命题1.3.1知
r(3,3)6
；在
K
5
中按图1.3.7的方式进行红、蓝两边 着色（实线为红边，虚线为蓝边），
则既无红色
K
3
也无蓝色
K3
，所以
r(3,3)5
。从而得知
r(3,3)6
。










由命题1.3.4
r(4,3)9
；在
K
8
中按图1.3 .8的方式进行红、蓝两边着色，则既无红色
K
4
也无蓝色
K
3，所
以
r(4,3)8
。从而得知
r(4,3)9

Ramsey于1930年证明了对于任给的整数
a
和
b
，Ramsey数
r(a,b)
的存在性。但是，Ramsey数的确定却
是一个非常难的问题，以至于 至今
r(5,5)
尚不为世人所知。表1.3.1中列出了目前所知的一些Ramsey数。

易证（留作习题）
（1）
r(a,b)r(b,a);

（2）
r(a,2)a

定理1.3.1 对任意的正整数
a 3,b3
，有
r

a,b

r

a 1,b

r

a,b1


证明 令
Nr

a1,b

r

a,b1
，对
K
N
任意进行红、蓝两边着色。设
x
是
K
N
的一个顶点，在
K
N
中
与
x
相关联的边共有r

a1,b

r

a,b1

1
条，这些边要么为红色，要么为蓝色。由鸽巢原理知，与
x
相关联的这些边中， 要么至少有
r

a1,b

条红边，要么至少有
r

a,b1

条蓝边。
（1）这些边中有
r

a1,b

条红边。在以这些红边与
x
相关联的
r
< br>a1,b

个顶点构成的完全图
K
r

a1,b

中，必有一个红色
K
a1
或有一个蓝色
K
b< br>，若有红色
K
a1
，则该红色
K
a1
加上顶点< br>x
以及
x
与
K
a1
之间的
红边，即构成一 个红色
K
a
；否则，就有一个蓝色
K
b
。
（2） 这些边中有
r

a1,b

条蓝边。在以这些蓝边与
x< br>相关联的
r

a,b1

个顶点构成的完全图
K< br>r

a,b1

中，必有一个红色
K
a
或 有一个蓝色
K
b1
。若有一个蓝色
K
b1
，则该
K
b1
加上顶点
x
以及
x
与
K
b1
之间的
蓝边，即构成一个蓝色
K
b
；否则，就有一个红色
K
a
。
综合（1）和（2），知
r

a,b

N
。 < br>由定理1.3.1及等式（1.3.2）容易归纳出对于任意的正整数
a
和
b, r(a,b)
的存在性。关于
r(a,b)
还有定理
1.3.2所述的不等式 成立。
定理1.3.2 对任意的正整数
a2,b2
，有
（1.3.1）
（1.3.2）

证明 对
ab
作归纳。
ab2

!

ab2


r

a,b




a1
a1 !b1!


当
ab5
时，
a2
或
b2
，由等式（1.3.2）知定理成立。
假设对一切满足
5ab mn
的
a,b
定理成立，由定理1.3.1及归纳假设，有
r

m,n

r

m,n1

r
< br>m1,n



mn3

mn3







m1

m2


mn2



m1


所以，对于任意的正事业
a2,b2
，定理的结论成立。
1.4 Ramsey数的推广
将1.3节中的红、蓝两色推广到任意k种颜色，对N个顶 点的完全图
K
N
用
c
1
,c
2
,L,c< br>k
共k种颜色任意进
行k边着色，它或者出现
c
1
颜色的K
a
，或者出现
c
2
颜色的
K
a
2< br>，……，或者出现
c
k
颜色的
K
a
k
。满足 上
1
述性质的N的最小值记为
r

a
1
,a
2
,La
k

。
定理1.4.1 对任意的正整数
a
1
,a
2
,La
k
，有

证明 留作习题
类似于定理1.3.1和定理1.3.2，有如下的结论：
定理1.4.2 对任意的正整数
a
1
2,a
2
2, La
k
2
，有
r

a
1
,a
2
,La
k

r

a
1
,r

a
2
,La
k



r

a
1
,a
2
,La
k

r

a
1
1,a
2
La
k

r

a
1
,a
2
1,La
k

L
r
a
1
,a
2
,La
k
1

n2
证明 类似于定理1.3.1的证明。
定理1.4.3 对任意的正整数a
1
,a
2
,La
k
，有
r

a
1
1,a
2
1,La
k
1


证明 类似于定理1.3.2的证明。
利用广义Ramsey数，我们来讨论一类集合划分问题。
考试集合

1, 2,L,13

的一个划分

1,4,10,13

,
2,3,11,12

,

5,6,7,8,9
< br>
可以看出，在上面的划分的每一块中，都不存在三个数
x,y,z
（不一定不 同）满足方程



a
1
a
2
L a
k

!

a
1
!a
2
!La< br>k
!

xyz
（1.4.1
然而，无论如何将集合

1,2,L,14

划分成三个子集合，总有一个子集合中有三个数满足方 程（1.4.1）。Schur
于1916年证明了对任意的正整数n，都存在一个整数
fn
，使得无论如何将集合

1,2,Lf
n

划分成n 个子
集合，总有一个子集合中有三个数满足方程（1.4.1）。下面，我们用Ramsey数来证明这 个结论。
定理1.4.4 设

S
1
,S
2
, LS
n

是集合

1,2,L,r
n

的 任一划分，即
U

1,2,L,r

n
i1
n< br>，且
S
i
IS
j


(ij,1i,j n)
，则对某一个
i,S
i
中有三个数
x,y,z
（不一 定不同），满足方程
xyz
。
其中
r
n
r

3,3,L,3


14243
n

证明 将完全图
K
r
n
中的
r
n
个顶点分别用
1 ,2,L,r
n
来标记，对
K
r
n
的边进行n着色如下：设
u,

是
K
r
n
的
任意两个项点，若u

S
j
，则将边
u

染成第
j
种颜色。由广义Ramsey数
r
n
的定义知一定存在同色三
角形， 即有三个项
a,b,c
，使得边
ab,bc,ca
有相同的颜色，设为第i
种颜色。另不妨设
abc
，则有
ab,bc,acSi
，令
xab,ybc,zac
，则有
x,y,zSi
，且
xyz
。
设
S
n
是满足下述性质 的最小整数：将

1,2,LS
n

任意划分成n个子集合，总有一 个子集合中含有三个数
。容易证明
s
1
2,s
2
5,s
3
14
（见本章习题24）。在本章的习题中，还列有
x,y,z
，满足方程（1.4.1）
一些关于
r
n
和
s
n
的 上、下界的结论。
将前面的鸽巢原理和Ramsey数进一步推广，可以得到下面更一般的Ramsey定理：
定理1.4.5（Ramsey定理） 设
q
1
,q
2
, Lq
n
，
t
是正整数，且
q
i
t(1in)
，则必存在最小的正整数
N

q
1
,q
2
,Lq
n
;t

，使得当
mN

q
1< br>,q
2
,Lq
n
;t

时，设S是一集合且
Sm
，将S的所有
t
元子集任意
分放到n个盒子里，那么要么有S中的q
1
个元素，它的所有
t
元子集全在第二个盒子里；……；要么有S中的
q
n
个元素，它的所有
t
元子集全在第n个盒子里。
证明 略。
当
t1
时，Ramsey定理说明
N(q
1
,q
2
,Lq
n
;1)
存在，使得对任何
mN

q
1
,q
2
,Lq
n
;1
< br>，把m个物体放
入n个盒子里，或者有
q
1
个物体都在第一个盒子里， 或者有
q
2
个物体都在第二个盒子里，……，或者有
q
n
个 物体都在第n个盒子里。从1.2节中鸽巢原理的加强形式知

N

q1
,q
2
,Lq
n
;1

q
2q
2
Lq
n
n1

当
t2
时，可以设想S是一完全图的顶点集合，n个盒子可以设想成n种颜色
c
1
,c2
,c
n
，S的2元子集就
是图中连接两个顶点的边。此时，Ramse y定理中的

N

q
1
,q
2
,Lq< br>n
;2

r

q
1
,q
2
,Lq
n


特别地，当
n2
时，由1.3节中的结论知

N(3,3;2)r(3,3)6

N(3,4;2)r(3,4)9
定理1.4.6
N(q
1
,t;t)q
1
,N(t,q
2
;t)q
2

证明 若S中元素少于或等于
q
1
1
个，则将S的所有
t
元子集全部放入第一个盒子里。这里，没有S的
q
1
元子集，它的所有t
元子集全在第一个盒子里；第二个盒子为空，也没有
t
元子集在第二个盒子里。 故

N(q
1
,t;t)q
1

若S中恰有
q
1
个元素，把S的t元子集分放到两个盒子中。若第二个盒子非空，即盒中至少存在 一个t元
子集，该t元子集的t元子集在第二个盒子中；若第二个盒子为空，则S的所有t元子集全在第 一个盒子里，
且
Sq
1
，无论哪种情况，均满足要求，故
N(q< br>1
,t;t)q
1
。
综合以上分析，知
N(q
1
,t;t)q
1

同理可证
N(t,q
2
;t)q
2