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

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

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

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

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

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

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

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

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

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