組合數(shù)學(xué)Ramsey問題與Ramsey數(shù)

1、1958年67月號美國數(shù)學(xué)月刊上登載著這樣一個有趣的問題：“任何6個人的聚會，其中總會有3個互相認識或3人互相不認識?！边@就是著名的Ramsey問題。以6個頂點分別代表6個人，如果兩人相識，則在相應(yīng)的兩頂間連一紅邊，否則在相應(yīng)的兩頂點間連一藍邊，則上述的Ramsey問題等價于下面的命題：命題1.3.1 對6個頂點的完全圖任意進行紅、藍兩邊著色，都存在一個紅色三角形或一個藍色三角形。證明 設(shè)是的6個頂點，與所連的5條邊著紅色或藍色。由鴿巢原理知，其中至少有條邊同色，不妨設(shè)與所連的3條邊均為紅色，如圖1.3.1所示。若間有一條紅邊，不妨設(shè)為，則是一紅色三角形。否則，間均為藍邊，即是一藍色三角形。類

2、似于命題1.3.1，還有如下的命題1.3.2命題1.3.4：命題1.3.2 對6個頂點的完全圖任意進行紅、藍兩邊著色，都至少有兩個同色三角形。證明 設(shè)是的6個頂點，由命題1.3.1知，對任意進行紅、藍兩邊著色都有一個同色三角形，不妨設(shè)是紅色三角形，以下分各種情況來討論：（1）若均為藍邊，如圖1.3.2所示，則若之間有一藍邊，不妨設(shè)為，則為藍色三角形；否則，為紅色三角形。（2）若中有一紅邊，不妨設(shè)為紅邊，此時若邊中有一條紅邊，不妨設(shè)是紅邊，則是一紅色三角形，見圖1.3.3。以下就均為藍邊的情況對與相關(guān)聯(lián)的邊的顏色進行討論：（i）若中有一藍邊，不妨設(shè)為藍邊，如圖1.3.4所示。此時，若均為紅邊，則

3、是紅色三角形；否則，或是藍色三角形。（ii）若均為紅邊，見圖1.3.5。此時，若之間有一條紅邊，不妨設(shè)為紅邊，則為紅色三角形；否則，為藍色三角形。由以上對各種情況的討率知，對的任意紅、藍兩邊著色均有兩個同色三角形。命題1.3.3 對10個頂點的完全圖任意進行紅、藍兩邊著色，都或者有一紅色，或者有一藍色。證明 設(shè)是的一個頂點，與相關(guān)聯(lián)的9條邊用紅、藍兩色著色，由鴿巢原理知，這9條邊中要么有6條紅邊，要么有4條藍邊。類似于前面兩個命題的分析證明過程可以得出結(jié)論，具體分析過程見圖1.3.6。命題1.3.4 對9個頂點的完全圖任意進行紅、藍兩邊著色，都或者有一個紅色，或者有一藍色。證明 在中，如果與每

4、個頂點關(guān)聯(lián)的紅邊均為5條，因為一條紅邊連著兩個頂點，所以中應(yīng)有條邊，它不是整數(shù)，所以不成立。故必有一個頂點關(guān)聯(lián)的紅邊數(shù)不為5，設(shè)此頂點為，則與關(guān)聯(lián)的紅邊數(shù)至少為6或至多為4。1.3.2 Ramsey數(shù)從1.3.1小節(jié)的討論中可以歸納出如下的一般性定義：對于任意給定的兩個正整數(shù)與，如果存在最小的正整數(shù)，使得當時，對中均有紅色或藍色，則稱為Ramsey數(shù)。；在中按圖1.3.7的方式進行紅、藍兩邊著色（實線為紅邊，虛線為藍邊），則既無紅色也無藍色，所以。從而得知。；在中按圖1.3.8的方式進行紅、藍兩邊著色，則既無紅色也無藍色，所以。從而得知Ramsey于1930年證明了對于任給的整數(shù)和，Ramse

5、y數(shù)的存在性。但是，Ramsey數(shù)的確定卻是一個非常難的問題，以至于至今尚不為世人所知。表1.3.1中列出了目前所知的一些Ramsey數(shù)。易證（留作習(xí)題）（1）（1.3.1）（2）（1.3.2）定理1.3.1 對任意的正整數(shù)，有證明 令，對任意進行紅、藍兩邊著色。設(shè)是的一個頂點，在中與相關(guān)聯(lián)的邊共有條，這些邊要么為紅色，要么為藍色。由鴿巢原理知，與相關(guān)聯(lián)的這些邊中，要么至少有條紅邊，要么至少有條藍邊。（1）這些邊中有條紅邊。在以這些紅邊與相關(guān)聯(lián)的個頂點構(gòu)成的完全圖中，必有一個紅色或有一個藍色，若有紅色，則該紅色加上頂點以及與之間的紅邊，即構(gòu)成一個紅色；否則，就有一個藍色。（2）這些邊中有條藍邊

6、。在以這些藍邊與相關(guān)聯(lián)的個頂點構(gòu)成的完全圖中，必有一個紅色或有一個藍色。若有一個藍色，則該加上頂點以及與之間的藍邊，即構(gòu)成一個藍色；否則，就有一個紅色。綜合（1）和（2），知。由定理1.3.1及等式（1.3.2）容易歸納出對于任意的正整數(shù)和的存在性。關(guān)于還有定理1.3.2所述的不等式成立。定理1.3.2 對任意的正整數(shù)，有證明 對作歸納。當時，或，由等式（1.3.2）知定理成立。假設(shè)對一切滿足的定理成立，由定理1.3.1及歸納假設(shè)，有所以，對于任意的正事業(yè)，定理的結(jié)論成立。1.4 Ramsey數(shù)的推廣將1.3節(jié)中的紅、藍兩色推廣到任意k種顏色，對N個頂點的完全圖用共k種顏色任意進行k邊著色，它

7、或者出現(xiàn)顏色的，或者出現(xiàn)顏色的，或者出現(xiàn)顏色的。滿足上述性質(zhì)的N的最小值記為。定理1.4.1 對任意的正整數(shù)，有證明 留作習(xí)題類似于定理1.3.1和定理1.3.2，有如下的結(jié)論：定理1.4.2 對任意的正整數(shù)，有證明 類似于定理1.3.1的證明。定理1.4.3 對任意的正整數(shù)，有證明 類似于定理1.3.2的證明。利用廣義Ramsey數(shù)，我們來討論一類集合劃分問題?？荚嚰系囊粋€劃分可以看出，在上面的劃分的每一塊中，都不存在三個數(shù)（不一定不同）滿足方程然而，無論如何將集合劃分成三個子集合，總有一個子集合中有三個數(shù)滿足方程（1.4.1）。Schur于1916年證明了對任意的正整數(shù)n，都存在一個整數(shù)

8、，使得無論如何將集合劃分成n個子集合，總有一個子集合中有三個數(shù)滿足方程（1.4.1）。下面，我們用Ramsey數(shù)來證明這個結(jié)論。定理1.4.4 設(shè)是集合的任一劃分，即，且，則對某一個中有三個數(shù)（不一定不同），滿足方程。其中證明 將完全圖中的個頂點分別用來標記，對的邊進行n著色如下：設(shè)是的任意兩個項點，若，則將邊染成第種顏色。由廣義Ramsey數(shù)的定義知一定存在同色三角形，即有三個項，使得邊有相同的顏色，設(shè)為第種顏色。另不妨設(shè)，則有，令，則有，且。設(shè)是滿足下述性質(zhì)的最小整數(shù)：將任意劃分成n個子集合，總有一個子集合中含有三個數(shù)，滿足方程（1.4.1）。容易證明（見本章習(xí)題24）。在本章的習(xí)題中，還

9、列有一些關(guān)于和的上、下界的結(jié)論。將前面的鴿巢原理和Ramsey數(shù)進一步推廣，可以得到下面更一般的Ramsey定理：定理1.4.5（Ramsey定理） 設(shè)，是正整數(shù)，且，則必存在最小的正整數(shù)，使得當時，設(shè)S是一集合且，將S的所有元子集任意分放到n個盒子里，那么要么有S中的個元素，它的所有元子集全在第二個盒子里；要么有S中的個元素，它的所有元子集全在第n個盒子里。證明 略。當時，Ramsey定理說明存在，使得對任何，把m個物體放入n個盒子里，或者有個物體都在第一個盒子里，或者有個物體都在第二個盒子里，或者有當時，可以設(shè)想S是一完全圖的頂點集合，n個盒子可以設(shè)想成n種顏色，S的2元子集就是圖中連接兩個頂點的邊。此時，Ramsey定理中的特別地，當定理1.4.6 證明 若S中元素少于或等于個，則將S的所有元子集全部放入第一個盒子里。這里，沒有S的元子集，它的所有元子集全在第一個盒子里