?
關鍵字搜索:
快速導航
Ramsey定理
發布時間: 2019-06-11       瀏覽次數:次

  確定一般的Ramsey數rt(q1,q2,…,qk)是一個堅苦的工做。關于它們的精確值我們曉得得很少。但不難看出,rt(t,q2,…,qk)=rt(q2,…,qk)而且q1,q2,…,qk的陳列挨次不影響Ramsey數的值。

  Ramsey證明,對于給定的正整數數k及l,R(k,l)的謎底是獨一和無限的。目前的進展如下圖所示(良多只要一個范疇):

  雖然R(3,3)的證明十分巧妙,可是現實上已知的Ramsey數很是少,好比R(3,3)=6,R(3,4)=9,R(4,4)=18保羅·艾狄胥曾以一個故事來描述尋找拉姆齊數的難度:

  聲明:百科詞條人人可編纂,詞條建立和點竄均免費,毫不存正在及代辦署理商付費代編,請勿上當。詳情

  按照抽屜道理,Friend和Strange中有一個調集至多有3小我,不妨假設是調集Friend。

  Friend中3小我P,Q,R若是相互互相不認識,則問題已獲得證明。不然有兩小我互相認識,不妨設這兩小我是P和Q,則A,P,Q這3小我相互認識。

  一對a和b,對應于一個整數r,使得r小我中或有a小我彼此認識,或有b小我互不認識;或有a小我互不認識,或有b小我彼此認識。這個數r的最小值用R(a,b)來暗示,也就是R(a,b)個極點的完全圖。用紅藍兩種顏色進行著色,無論何種環境必至多存正在以下兩者之一:(1)一個a個極點著紅顏色的完全子圖,或一個b個極點著藍顏色的完全子圖;(2)一個a個極點著藍顏色的完全子圖,或一個b個極點著紅顏色的完全子圖。

  假設t=1。于是,r1(q1,q2,…,qk)就是滿腳下面前提的最小的數p:若是p元素調集的元素被用顏色c1,c2,…,ck中的一種顏色著色,那么或者存正在q1個都被著成顏色c1的元素,或者存正在q2個都被著成顏色c2的元素,…,或者存正在qk個都被著成顏色ck的元素。因而,按照鴿巢道理的加強版,有r1(q1,q2,…,qk)=q1+q2+…+qk-k+1這就證明Ramsey定理是鴿巢道理的加強版的擴展。

  若把以上會商中紅、藍兩種顏色改為k種顏色c1,c2,...,ck,把存正在a條邊的同色完全圖,或b條邊的同色完全圖,改為或a1,或a2,...,或a條邊的同色完全圖,即獲得Ramsey數R(a1,a2,...,ak),即對r個極點的完全圖,用k種顏色c1,c2,...,ck肆意染色,必然是或呈現以c1顏色的a1個極點的完全圖,或呈現以c2顏色的a2個極點的完全圖,...,或呈現以ck顏色的ak個極點的完全圖,如許的整數r的最小值用R(a1,a2,...ak)暗示。

  給定整數t≥2及整數q1,q2,…,qk≥t,存正在一個整數p,使得Ktp→Ktq1,Ktq2,…,Ktqk成立。也就是說,存正在一個整數p,使得若是給p元素調集中的每一個t元素子集指定k種顏色c1,c2,…,ck中的一種,那么或者存正在q1個元素,這些元素的所有t元素子集都被指定為顏色c1,或者存正在q2個元素,這些元素的所有t元素子集都被指定為顏色c2,…,或者存正在qk個元素,它的t元素子集都被指定為顏色ck。如許的整數中最小的整數p為Ramsey數rt(q1,q2,…,qk)。

 ?。?)證明9小我中若不是3小我互不認識,則必有4小我互相認識,同樣,9小我中若不是3小我互相認識,則必有4小我互不認識。

  針對Ramsey定理擴展到肆意多種顏色的環境,我們給出一個很是簡單的引見。若是n1,n2和n3都是大于或等于2的整數,則存正在整數p,使得Kp→Kn1,Kn2,Kn3。

  Ramsey F P. On a Problem of Formal Logic[J]. Proceedings of the London Mathematical Society, 2009, 30(1):1-24.

  由抽屜道理可知:這五條線段中至多有是同色的。不妨設AB、AC、AD為紅色。若BC或CD為紅色,則結論明顯成立。若BC和CD均為藍色,則若BD為紅色,則必然有三小我彼此認識;若BD為藍色,則必然有三小我互相不認識。

  上述問題能夠看做是R(3,3)=6的一個特例,的證明操縱圖的抽象而曲不雅的特點,證了然R(3,3)=6。

  因而,K17→K3,K3,K3,而K16→K3,K3,K3。我們能夠用雷同的方義Ramsey數r(n1,n2,…,nk),而對于點對Ramsey定理的完全一般形式是這些數存正在;即存正在整數p,使得Kp→Kn1,Kn2,…,Knk成立。

  該定理等價于證明這6個極點的完全圖的邊,用紅、藍二色肆意著色,必然至多存正在一個紅色邊三角形,或藍色邊三角形。

  注:關于以上推論和定理的證明,能夠參考《組合數學(第4版)》盧開澄、盧華明編著,此中的第3章第15節給取了證明

  Frank Plumpton Ramsey(弗蘭克·普倫普頓·拉姆齊,1903-1930)是英國

  也就是說,若是把Kp的每條邊著上紅色、藍色或綠色,那么或者存正在一個紅Kn1,或者存正在一個藍Kn2,或者存正在一個綠Kn3。使該結論成立的最小整數p稱為Ramsey數r(n1,n2,n3)。已知這品種型的僅有的非普通Ramsey數為r(3,3,3)=17。

  定理4對所有的整數a和b,a,b=2,若R(a,b-1)和R(a-1,b)是偶數,則

  注:這個定理以弗蘭克·普倫普頓·拉姆齊定名,1930年他正在論文On a Problem in Formal Logic

  “想像有隊外星人戎行正在地球下降,要求取得R(5,5)的值,不然便會地球。正在這個環境,我們該當集中所有電腦和數學家測驗考試去找這個數值。若它們要求的是R(6,6)的值,我們要測驗考試這班外星人了?!?/p>

  Ramsey定理還有更一般的形式,正在這種形式中點對(兩個元素的子集)換成了t個元素的子集,此中t≥1是某個整數。令Ktn暗示n元素調集中所有t個元素的子集的調集。將的概念擴展,Ramsey定理的一般形式可論述如下:

  若是調集Strange至多有3小我,能夠同樣會商如下:若Strange有3人L,M,N相互互相認識,則問題的前提已獲得滿腳。不然設L和M互不了解,則A,L,M互不了解。

  證明如下:起首,把這6小我設為A、B、C、D、E、F六個點。由A點能夠引出AB、AC、AD、AE、AF五條線段。設:若是兩小我認識,則設這兩小我構成的線段為紅色;若是兩小我不認識,則設這兩小我構成的線段為藍色。

?