Ransey問題與Ransey數(shù).ppt

1、1.3 Ramsey問題與Ramsey數(shù),組合數(shù)學 Chapter 1,Contents,一、 Ramsey問題 完全圖的染色問題,二、 Ramsey數(shù),一、Ramsey問題完全圖的染色問題,著名的Ramsey 問題：,問題1: 1958年67月號美國數(shù)學月刊上登載著這樣一個有趣的問題：“任何6個人的聚會，其中總會有3人互相認識或互相不認識.”,問題2: 1959年美國數(shù)學月刊第2期又進一步提出：“任何18個人的聚會，其中總會有4人互相認識或互相不認識.”,轉化為完全圖的染色問題來解決.,定義 有n個頂點且每兩個頂點都有一條邊的簡單圖稱為n階完全圖，記為Kn .,于是, Ramsey問題1為下

2、面的定理1.,定理1 對6階完全圖K6的邊任意涂紅、藍兩色, 則必存在一個紅色三角形或一個藍色三角形.,證明 設 是K6的6個頂點, 所連的5條邊著紅色或藍色，由鴿巢原理知，其中至少有3條邊同色.,不妨設 所連的3條邊均為紅色,如圖所示,若 間有一條紅邊,不妨設為 ，,則 是一紅色三角形.,否則，,間均為藍邊,即 是一藍色三角形.,顯然, 當 時,把K6換成 Kn定理的結論顯然仍成立. 但當n=5時,定理的結論就不一定成立了.例如對下圖所示的 實邊涂紅色, 虛邊涂藍色, 既無紅色的三角形，也無藍色的三角形,所以,6為結論成立的最小數(shù).,這個最小數(shù)稱為Ramsey數(shù),記為N(3,3;2)，即N(

3、3,3;2)=6.,定理1 我們還可敘述為：,S為n元集合,當n6時,把S的所有2元子集放入兩個盒子,則或者有3個元素其所有2元子集全在第一個盒子里，或者有3個元素其所有2元子集全在第二個盒子里,定理2 對9階完全圖K9的邊任意涂紅、藍兩色，則必存在一個紅色(藍色)的K4 ,或者必存在一個藍色(紅色)的K3.,為了證明定理2先證下面的引理,引理 對9階完全圖K9的邊任意涂紅、藍兩色,則必存在一個頂點, 從這點引出的8條線段中, 紅色（藍色）線段或多于3條或少于3條,證明 用反證法,如果不存在這樣的頂點, 即從每一頂點發(fā)出的線段中,紅色（藍色）線段都是三條.現(xiàn)在對9個頂點逐點統(tǒng)計由它們發(fā)出的紅色

4、（藍色）線段的條數(shù), 應為27條,另一方面，若設,K9中實有紅色（藍色）線段總數(shù)為m條, 現(xiàn)對這m條邊的端點逐點統(tǒng)計由它們發(fā)出的紅色線段的條數(shù)，,由于每條線段有,兩個端點, 故應有2m條,由此得出2m=27這是不可能的,故引理得證,證明定理2:,設 是構成K9的9個頂點, 由引理其中必有一點,或少于3條. 對這兩種情況分別討論如下：,(1) 從v0引出的8條線段中, 藍色線段多于3條, 即至少有4條，,不妨設 為藍色線段,點所構成的完全圖K4，,若這個K4中沒有一條線段是藍色的,則,這個K4就是一個紅色的完全四邊形.若這個K4至少有一條藍邊,則它的兩個端點連同v0便構成一個藍色三角形；,即結論

5、成立,定理2 對9階完全圖K9的邊任意涂紅、藍兩色，則必存在一個紅色(藍色)的K4 ,或者必存在一個藍色(紅色)的K3.,(2) 從v0引出的8條線段中,藍色線段少于3條，即至多有2條,這時, 從v0引出的紅色線段就會至少有6條，不妨設為,再看由 這6個點構成的K6，,由定理1可知,這個K6必有一個同色三角形.,若是紅色的,則這個紅色三角形,的頂點連同v0一起便構成一個紅色的完全四邊形K4.,即結論成立,綜合以上兩種情況，定理2得證,若是藍色的, 這個三角形即為藍色的K3 .,顯然, 當 時,把K9換成 Kn定理的結論顯然仍成立. 但當n=8時,定理的結論就不一定成立了.例如對下圖所示的 實邊

6、涂紅色, 虛邊涂藍色, 既無紅色的完全四邊形，也無藍色的三角形,所以,9為結論成立的最小數(shù).,這個最小數(shù)稱為Ramsey數(shù),記為N(3,4;2)，即N(3,4;2)=9.,定理2 我們還可敘述為：,S為n元集合,當n9時,把S的所有2元子集放入兩個盒子,則或者有3個元素其所有2元子集全在第一個盒子里，或者有4個元素其所有2元子集全在第二個盒子里,Ramsey問題2為下面的定理3.,定理3 對18階完全圖K18的邊任涂紅、藍兩色, 則必存在一個紅色的K4, 或者存在一個藍色的K4 .,證明 設 是K18的18個頂點，現(xiàn)考察K18中,從v0出發(fā)的17條線段, 它們分成了紅、藍兩類, 由鴿巢原理知,

7、至少有9條是同色的，,不妨設它們是紅色.,考察這9條紅色線段,異于v0的9個端點所構成的K9，,由定理2知K9中必存在一個紅色,三角形K3, 或一個藍色完全四邊形K4.,若是后者，則命題得證；,若是前者,則這個紅色三角形的三個頂點和v0便構成一個紅色的完全四邊形.,所以,定理成立.,顯然, 當 時,把K18換成 Kn定理的結論顯然仍成立. 但當n=17時,定理的結論就不一定成立了.,例如把K17的17個頂點記為 ,在把數(shù)字1,2,16分為A,B兩組,按以下規(guī)則對K17的邊進行涂色：,涂紅色；,涂藍色；,這樣涂得的K17即不存在紅色K4的也不存在藍色的K4 ,所以n=18是定理結論成立的最小數(shù).

8、這個數(shù)記為,這個數(shù)記為 ,定理3 我們還可敘述為：,S為n元集合,當n18時,把S的所有2元子集放入兩個盒子,則或者有4個元素其所有2元子集全在第一個盒子里，或者有4個元素其所有2元子集全在第二個盒子里,當n=?時,對完全圖Kn的邊任涂紅、藍兩色, 則必存在一個紅色的K5, 或者存在一個藍色的K5 .,目前已證得43n 49.,當n=?時,對完全圖Kn的邊任涂紅、藍兩色, 則必存在一個紅色的K6, 或者存在一個藍色的K6 .,目前已證得102n 165.,二、Ramsey數(shù),關于完全圖的兩種顏色的染色問題，可歸納出如下的一般情況：,對于任意給定的兩個正整數(shù)a和b，存在最小的正整數(shù)N(a,b;2

9、), 使得當,對Km的邊任意涂于紅、,藍兩色, Km中必存在紅色的Ka或藍色Kb.,我們把N(a,b;2)稱為Ramsey數(shù).簡記為r(a,b).,由上面的定理可知 :,S為n元集合,對于任意給定的兩個正整數(shù)a和b，存在最小的正整數(shù)N(a,b;2),當nN(a,b;2)時,把S的所有2元子集放入兩個盒子,則或者有a個元素其所有2元子集全在第一個盒子里，或者有b個元素其所有2元子集全在第二個盒子里,Ramsey于1928年已經(jīng)證明了對于任給的整數(shù)a和b, Ramsey數(shù) 的存在性. 但是Ramsey數(shù)的確定卻是一個非常難的問題, 以致于至今知道的還極少.,(見P17表.),雖然 難以確定，但關于

10、它具有以下的一些性質,性質1 為Ramsey數(shù)，則有,性質2 對任意的正整數(shù) , 有,證明 令 下面只要證明對KN的邊任著紅、藍兩色，必存在紅色的Ka或藍色的Kb . 設x為KN的一個頂點，與x關聯(lián)的邊有N-1條，對這些邊任意著紅、藍兩色,由鴿巢原理,性質2 對任意的正整數(shù) , 有,1. 若至少有r(a-1,b)條紅邊.這些紅邊與x相關聯(lián)的頂點有 r(a-1,b)個, 在這些頂點構成的完全圖 中, 必有一個紅色,的Ka-1或一個藍色的Kb .,若為紅色的Ka-1 , 則該紅色的Ka-1加上,頂點x及x與Ka-1 之間的紅邊,即構成一個紅色的Ka ;否則，就有一個藍色的Kb .,2.若至少有r(

11、a, b-1)條藍邊.這些藍邊與x相關聯(lián)的頂點有,r(a,b-1)個, 在這些頂點構成的完全圖 中, 必有一 個紅色,的Ka或藍色的Kb-1 .,若為前者結論成立,若為后者,則該藍色的,的Kb-1加上頂點x及關聯(lián)的藍邊即構成一個藍色的Kb .,所以有,性質3 對任意的正整數(shù) ,當 都為偶數(shù)時,有,證明,考慮由t個點所構成的完全圖Kt，將它的邊涂以紅、藍兩色,我們證明必定存在紅色（藍色）的Ka 或存在藍色（紅色） Kb ,為此, 我們從t個點中選取一個點v0, 它與其余t-1個點所連成的t-1條邊中，一定出現(xiàn)有多于2m-1條紅色邊，或少于2m-1條紅色邊,因為否則從每一頂點引出的紅色邊都是2m-

12、1條, 這時從t個頂點引出的紅色邊將共(2m-1) (2m+2l-1)有條. 由于其中每條邊有兩個端點都被計算了兩次, 假設kt中有h條紅色邊,于是便有,產(chǎn)生矛盾，所以從v0引出的t-1條邊中，一定出現(xiàn)有多于2m-1條紅色邊，或少于2m-1條紅色邊,對上面的兩種情況分別討論如下：,(1)從v0點引出的t-1條邊中紅色邊多于2m-1條，即至少 有2m條,我們考察由2m條紅色邊所有異于v0的端點構成的完全圖K2m . 因為 , 所以K2m中必定存在紅色的Ka-1，或存在藍色的Kb ,若為后者結論成立,若為前者, 則紅色的Ka-1連同v0一起便構成了紅色的Ka ,結論也成立。,(2)從v0點引出的t

13、-1條邊中紅色邊少于2m-1條，即至多有2m-2條,于是藍色邊至少有2l條，,我們考察由2l條藍色邊所有異于v0的端點構成的完全圖K2l 因為 ,所以K2l中必定存在紅色的Ka，或存在藍色的Kb-1 ,若為前者結論成立,若為后者,則藍色的Kb-1連同v0一起便構成了藍色的Kb ,結論也成立,所以有,性質4 對任意的正整數(shù) , 有,證明 對a+b進行歸納.,當a+b5時，有a=2或b=2,由性質1結論成立.,假設對一切滿足5 a+b m+n的a,b都成立，下面證明a+b=m+n時結論也成立.,由歸納假設有,由歸納法，結論成立.,世界各國的數(shù)學競賽經(jīng)常出現(xiàn)與Ramsey問題有關的題目.,例1 （波

14、蘭）平面上有6個點，任何3點都是一個不等邊三角形的頂點，則這些三角形中，有一個三角形的最長邊是另一個三角形的最短邊.,證明：以平面上這6個點構作完全圖K6 ,并按如下方式用紅、藍二色對K6的邊著色：,對K6的每個三角形的最短邊都涂上紅色，剩余的邊再涂上藍色.,由定理1，此K6中必有同色的三角形.,由于該三角形的最短邊,為紅色, 因此這個同色的三角形是紅色的三角形.,而這個三角,形的最長邊為紅色, 按涂色方法知, 必是另一個三角形的最短邊.,所以, 有一個三角形的最長邊是另一個三角形的最短邊.,1964年第六屆國際數(shù)學奧林匹克數(shù)學竟賽有這樣一道試題：,有17名學生互相通信討論3個問題，但每對學生

15、間僅討論其中一個問題，證明至少有3名學生間彼此討論的是同一個問題.,這個問題是前面Ramsey問題1問題2的推廣，把它轉化為圖的染色問題，可得到下面定理：,定理4 對17階完全圖K17的邊任涂紅、藍、黃三色，則必存在一個同色的三角形.,證明 設 是K17的17個頂點，現(xiàn)考察K17中,從v0出發(fā)的16條線段,當對它們涂于紅、藍、黃三色時 , 由鴿巢原理知至少有6條邊是同色的 ，,不妨設,是紅色邊，,再看由 這6個點構成的K6，,若這個K6有一條紅邊，則它的兩個端點連同v0便構成一個紅色三角形,結論成立；,若這個K6沒有一條紅邊，,則它的邊,只能涂于藍色和黃色，由定理1知它一定會出現(xiàn)一個藍色的三角形，或一個黃色三角形，結論成立,所以定理得證,而且