組合數(shù)學2020上半年上課課件8ramsey

1《圖論與組合數(shù)學》第九講

Ramsey數(shù)2Ramsey數(shù)在引出Ramsey數(shù)之前,先給出幾個引理.引理1

若集合S由6個人組成,那么S中或者存在至少3個人互相認識,或者存在至少3個人互不認識.證明

在6個人中,任意固定一個人A,則其余的5人可以分成兩部分,一部分是由與A認識的人組成的F,另外一部分是由與A不認識的人組成的T,由鴿巢原理,這兩部分至少有一部分含有3個人.3|F|≥3.

這時候,如果F中有3個人互相不認識,自然命題得證;如果其中至少有2個人互相認識,則這兩個人與A一起組成互相認識的3個人.|T|≥3.

如果T中3個人互相認識,命題得證;如果其中至少有2個人互相不認識,再添加上A即可得三個互相不認識的人.引理可以敘述為:如果對一個6個頂點的完全圖的邊用紅、藍兩種顏色去染色,則一定存在一個單色的三角行.4引理2

若集合S由10人組成,那么S中存在至少4個人互相認識,或存在至少3個人互不認識.證明

在這10個人當中任意固定一個人A,則其余人可以分成兩類：圖15F：與A相互認識的人的集合

T:

與A相互不認識的人的集合

由鴿巢原理,至少有一類含有不少于5個的人.證明可以分情況得到.若|T|≤3,則|F|≥6,由引理1,F中有3個互相認識的或者互相不認識的.如果有3個互相不認識的,引理得證;如果有3個互相認識的,再加上A就是4個互相認識的,引理成立.6(2)

若|T|≥4,如果T中所有人都是互相認識的,引理得證;如果T中至少有兩個人互相不認識,再加上A就是3個互相不認識的,引理也成立.類似方法可以證明:引理3

由10人組成的集合中或者有4人互不認識,或者至少有3人互相認識.引理4

由20人組成集合中或者有4人互相認識,或者有4人互不認識.7定義1

設p,q是任意給定的正整數(shù),而且p

≥2,q≥2.

如果存在一個最小的正整數(shù)R,使得任意R個人組成的集合S,下面兩件事中有一件必然成立：(1)

S中至少有p個人互相認識；(2)

S中至少有q個人互相不認識;

則稱R是具有參數(shù)p,q;2的Ramsey數(shù),并記作R(p,q;2),可省略2,而簡記作R(p,q).這里我們采用了一個通俗的定義.8由引理1,R(3,3)=6.關于Ramsey數(shù)的幾點注釋：(1)

Ramsey數(shù)可以用完全圖邊的2-染色來解釋.

用Kn來表示n階完全圖,顯然Kn共有

n(n-1)/2條邊.如果用r(r

≥2)

種顏色去染Kn的邊,每

條邊染一種顏色,所得到的每條邊都染

了色的Kn稱為r-染色Kn.

可以用頂點表示人,邊色表示關系.9

R(p,q)=n:

Kn的任意紅、藍染色必然出現(xiàn)紅色Kp,或者藍色的Kq,

但是Kn-1不具備這樣的性質.(2)

Ramsey數(shù)也可以用圖中的獨立集和團來解釋.

R(p,q)=n:

任意n個頂點的圖包含Kp

或者有一個q個點的獨立集,但是存在不具備這樣的性質的n-1階圖.

這時候可以理解為互相認識的人連邊,

互相不認識的不連邊.10

Ramsey數(shù)的決定非常非常困難.要得到R(p,q)=n,須完成下面兩步:(a)Kn的任意(紅,藍)-染色必然有紅色Kp或藍色Kq;(b)構造Kn-1的一個(紅,藍)-染色,使得其中既沒有紅色Kp也沒有藍色Kq.下面的表格給出目前已知的部分結果,完全的結果可以見:

11123456789103691418232836[40,43]41825[35,41][49,61][55,84][69,115][80,149]5[43,49][58,87][80,143][95,216][116,316][141,442]6[102,165][109,298][122,495][153,780][167,1171]7[205,540][1,1031][1,1713][1,2826]8[282,1870][1,3583][1,6090]9[565,6588][1,12677]10[798,23581]13Ramsey數(shù)的性質定理4

Ramsey數(shù)具下列簡單性質:(1)

R(p,q)=R(q,p)(2)

R(p,2)=p,R(2,q)=q(3)

R(p,q)一定存在14定理5

設p,q都是大于2的正整數(shù),則

R(p,q)

≤R(p-1,q)+R(p,q-1).證明

令R(p-1,q)+R(p,q-1)=n.

在n個人中間,任意固定一個人A,其余n-1個人可以分成兩類:F:

與A相互認識的人的集合;T:

與A互相不認識的人的集合.由于n-1=R(p-1,q)+R(p,q-1)-1,

由鴿巢原理,|F|≥R(p-1,q)或者|T|≥R(p,q-1).15(1)

|F|≥R(p-1,q).

此時由R(p-1,q)的定義,F中或者有p-1個人互相認識,加上A就得到p個互相認識的人;或者有q個人互相不認識.(2)

|T|≥R(p,q-1).此時由R(p,q-1)的定義,T中或者有p個人互相認識;或者有q-1個互相不認識的,再加上A就得到q個互相認識的人.因此任意n個人中間一定有p個互相認識,或者有q個人互相不認識.16定理6

設p,q都是大于2的正整數(shù),當R(p-1,q)和R(p,q-1)都是偶數(shù)時,有R(p,q)

≤R(p-1,q)+R(p,q-1)-1.推論1

R(3,4)=9.證明

因為R(2,4)=4,R(3,3)=6,所以由定理6,有R(3,4)≤R(2,4)+R(3,3)-1=4+6-1=9.由下圖中構造一個(紅,藍)-著色K8不含有藍色K3也不含有紅色K4.R(3,4)>8,從而可得R(3,4)=9.17圖218推論2

R(3,5)=14.證明

因為R(2,5)=5,R(3,4)=9,