組合數(shù)學(xué)-第二節(jié)：Ramsey問題與Ramsey數(shù)

組合數(shù)學(xué)-第二節(jié)：Ramsey問題與Ramsey數(shù)組合數(shù)學(xué)-第二節(jié)：Ramsey問題與Ramsey數(shù)組合數(shù)學(xué)-第二節(jié)：Ramsey問題與Ramsey數(shù)組合數(shù)學(xué)-第二節(jié)：Ramsey問題與Ramsey數(shù)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:第二節(jié)：Ramsey問題與Ramsey數(shù)1958年6~7月號(hào)美國(guó)《數(shù)學(xué)月刊》上登載著這樣一個(gè)有趣的問題：“任何6個(gè)人的聚會(huì)，其中總會(huì)有3個(gè)互相認(rèn)識(shí)或3人互相不認(rèn)識(shí)?！边@就是著名的Ramsey問題。以6個(gè)頂點(diǎn)分別代表6個(gè)人，如果兩人相識(shí)，則在相應(yīng)的兩頂間連一紅邊，否則在相應(yīng)的兩頂點(diǎn)間連一藍(lán)邊，則上述的Ramsey問題等價(jià)于下面的命題：命題對(duì)6個(gè)頂點(diǎn)的完全圖任意進(jìn)行紅、藍(lán)兩邊著色，都存在一個(gè)紅色三角形或一個(gè)藍(lán)色三角形。證明設(shè)是的6個(gè)頂點(diǎn)，與所連的5條邊著紅色或藍(lán)色。由鴿巢原理知，其中至少有條邊同色，不妨設(shè)與所連的3條邊均為紅色，如圖所示。若間有一條紅邊，不妨設(shè)為，則是一紅色三角形。否則，間均為藍(lán)邊，即是一藍(lán)色三角形。類似于命題，還有如下的命題命題：命題對(duì)6個(gè)頂點(diǎn)的完全圖任意進(jìn)行紅、藍(lán)兩邊著色，都至少有兩個(gè)同色三角形。證明設(shè)是的6個(gè)頂點(diǎn)，由命題知，對(duì)任意進(jìn)行紅、藍(lán)兩邊著色都有一個(gè)同色三角形，不妨設(shè)是紅色三角形，以下分各種情況來(lái)討論：（1）若均為藍(lán)邊，如圖所示，則若之間有一藍(lán)邊，不妨設(shè)為，則為藍(lán)色三角形；否則，為紅色三角形。（2）若中有一紅邊，不妨設(shè)為紅邊，此時(shí)若邊中有一條紅邊，不妨設(shè)是紅邊，則是一紅色三角形，見圖。以下就均為藍(lán)邊的情況對(duì)與相關(guān)聯(lián)的邊的顏色進(jìn)行討論：（i）若中有一藍(lán)邊，不妨設(shè)為藍(lán)邊，如圖所示。此時(shí)，若均為紅邊，則是紅色三角形；否則，或是藍(lán)色三角形。（ii）若均為紅邊，見圖。此時(shí)，若之間有一條紅邊，不妨設(shè)為紅邊，則為紅色三角形；否則，為藍(lán)色三角形。由以上對(duì)各種情況的討率知，對(duì)的任意紅、藍(lán)兩邊著色均有兩個(gè)同色三角形。命題對(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è)命題的分析證明過程可以得出結(jié)論，具體分析過程見圖。命題對(duì)9個(gè)頂點(diǎn)的完全圖任意進(jìn)行紅、藍(lán)兩邊著色，都或者有一個(gè)紅色，或者有一藍(lán)色。證明在中，如果與每個(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。Ramsey數(shù)從1..小節(jié)的討論中可以歸納出如下的一般性定義：對(duì)于任意給定的兩個(gè)正整數(shù)與，如果存在最小的正整數(shù)，使得當(dāng)時(shí)，對(duì)中均有紅色或藍(lán)色，則稱為Ramsey數(shù)。由命題知；在中按圖的方式進(jìn)行紅、藍(lán)兩邊著色（實(shí)線為紅邊，虛線為藍(lán)邊），則既無(wú)紅色也無(wú)藍(lán)色，所以。從而得知。由命題；在中按圖的方式進(jìn)行紅、藍(lán)兩邊著色，則既無(wú)紅色也無(wú)藍(lán)色，所以。從而得知Ramsey于1930年證明了對(duì)于任給的整數(shù)和，Ramsey數(shù)的存在性。但是，Ramsey數(shù)的確定卻是一個(gè)非常難的問題，以至于至今尚不為世人所知。表中列出了目前所知的一些Ramsey數(shù)。易證（留作習(xí)題）（1） （）（2） （）定理對(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)邊。在以這些藍(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），知。由定理及等式（）容易歸納出對(duì)于任意的正整數(shù)和的存在性。關(guān)于還有定理所述的不等式成立。定理對(duì)任意的正整數(shù)，有 證明對(duì)作歸納。當(dāng)時(shí)，或，由等式（）知定理成立。假設(shè)對(duì)一切滿足的定理成立，由定理及歸納假設(shè)，有 所以，對(duì)于任意的正事業(yè)，定理的結(jié)論成立。Ramsey數(shù)的推廣將節(jié)中的紅、藍(lán)兩色推廣到任意k種顏色，對(duì)N個(gè)頂點(diǎn)的完全圖用共k種顏色任意進(jìn)行k邊著色，它或者出現(xiàn)顏色的，或者出現(xiàn)顏色的，……，或者出現(xiàn)顏色的。滿足上述性質(zhì)的N的最小值記為。定理對(duì)任意的正整數(shù)，有 證明留作習(xí)題類似于定理和定理，有如下的結(jié)論：定理對(duì)任意的正整數(shù)，有證明類似于定理的證明。定理對(duì)任意的正整數(shù)，有證明類似于定理的證明。利用廣義Ramsey數(shù)，我們來(lái)討論一類集合劃分問題?？荚嚰系囊粋€(gè)劃分可以看出，在上面的劃分的每一塊中，都不存在三個(gè)數(shù)（不一定不同）滿足方程 （然而，無(wú)論如何將集合劃分成三個(gè)子集合，總有一個(gè)子集合中有三個(gè)數(shù)滿足方程（）。Schur于1916年證明了對(duì)任意的正整數(shù)n，都存在一個(gè)整數(shù)，使得無(wú)論如何將集合劃分成n個(gè)子集合，總有一個(gè)子集合中有三個(gè)數(shù)滿足方程（）。下面，我們用Ramsey數(shù)來(lái)證明這個(gè)結(jié)論。定理設(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ù)，滿足方程（）。容易證明（見本章習(xí)題24）。在本章的習(xí)題中，還列有一些關(guān)于和的上、下界的結(jié)論。將前面的鴿巢原理和Ramsey數(shù)進(jìn)一步推廣，可以得到下面更一般的Ramsey定理：定理（Ramsey定理）設(shè)，是正整數(shù)，且，則必存在最小的正整數(shù)，使得當(dāng)時(shí)，設(shè)S是一集合且，將S的所有元子集任意分放到n個(gè)盒子里，那么要么有S中的個(gè)元素，它的所有元子集全在第二個(gè)盒子里；……；要么有S中的個(gè)元素，它的所有元子集全在第n個(gè)盒子里。證明略。當(dāng)時(shí)，Ramsey定理說明存在，使得對(duì)任何，把m個(gè)物體放入n個(gè)盒子里，或者有個(gè)物體都在第一個(gè)盒子里，或者有個(gè)物體都在第二個(gè)盒子里，……，或者有個(gè)物體都在第n個(gè)盒子里。從節(jié)中鴿巢原理的加強(qiáng)形式知 當(dāng)時(shí)，可以設(shè)想S是一完全圖的頂點(diǎn)集合，n個(gè)盒子可以設(shè)想成n種顏色，S的2元子集就是圖中連接兩個(gè)頂點(diǎn)的邊。此時(shí)，Ramsey定理中的 特別地，當(dāng)時(shí)，由節(jié)中的結(jié)論知 定理證明若S中元素少于或等于個(gè)，則將S的所有元子集全部放入第一個(gè)盒子里。這里，沒有S的元子集，它的所有元子集全在