西塔潘猜想的定義
對於所有的N頂圖,包含k個頂的團或l個頂的獨立集。具有這樣性質的最小自然數N就稱為壹個拉姆齊數,記作R(k,l);
在著色理論中描述為:對於完全圖Kn任意壹個2邊著色(e1,e2),使得Kn[e1]裏含有壹個k階子完全圖,Kn[e2]含有壹個l階子的完全圖,則稱滿足這個條件的最小的n是壹個拉姆齊數。(註意的是Ki按照圖論的記法表示i階完全圖)拉姆齊證明,對與給定的正整數數k及l,R(k,l)的答案為唯壹和有限的。
拉姆齊數亦可推廣到多於兩個數:
對完全圖Kn每條邊都任意塗上r種顏色之壹,要分別記e1,e2,e3,...,er,在Kn裏,壹定有壹個顏色為e1的l1階子完全圖,或有壹個顏色為e2的l2階子完全圖……或有壹個顏色是er的lr階子完全圖。符合條件又最少的數n則記R(l1,l2,l3,...,lr;r)。 已知的拉姆齊數非常少,保羅·艾狄胥曾以壹個故事來描述尋找拉姆齊數難度:“想像有隊外星人軍隊在地球降落,要取得R(5,5)的值,否則就會毀滅地球。
在這壹個情況,應該集中所有電腦和數學家嘗試去找這壹個數值。假如它們要求的是R(6,6)的值,要嘗試毀滅這班外星人了。”