拉姆齐定理

维基百科,自由的百科全书
跳转至: 导航搜索

組合數學上,拉姆齐(Ramsey)定理,又称拉姆齐二染色定理,是要解決以下的問題:要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识。

這個定理以弗兰克·普伦普顿·拉姆齐命名,1930年他在論文On a Problem in Formal Logic(《形式邏輯上的一個問題》)證明了R(3,3)=6。

拉姆齐数的定義[编辑]

拉姆齐数,用图论的语言有两种描述:

  1. 对于所有的N顶图,包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数,记作R(k,l);
  2. 在着色理论中是这样描述的:对于完全圖K_n的任意一个2边着色(e_1,e_2),使得K_n[e_1]中含有一個k阶子完全图,K_n[e_2]含有一個l阶子完全图,则称满足这个条件的最小的n为一个拉姆齐数。(注意:K_i按照图论的记法表示i阶完全图)

拉姆齐证明,对与给定的正整數数kl,R(k,l)的答案是唯一和有限的。

拉姆齐數亦可推廣到多於兩個數:

对于完全圖K_n的每條邊都任意塗上r種顏色之一,分別記為e_1,e_2,e_3, ... , e_r,在K_n中,必定有個顏色為e_1l_1阶子完全图,或有個顏色為e_2l_2阶子完全图……或有個顏色為e_rl_r阶子完全图。符合條件又最少的數n則記為R(l_1,l_2,l_3, ... , l_r ; r)。

拉姆齐數的數值或上下界[编辑]

已知的拉姆齐數非常少,保羅·艾狄胥曾以一個譬喻來描述尋找拉姆齐數的難度:「想像有隊外星人軍隊在地球降落,要求取得R(5,5)的值,否則便會毀滅地球。在這個情況,我們應該集中所有電腦和數學家嘗試去找這個數值。若它們要求的是R(6,6)的值,我們要嘗試毀滅這班外星人了。」

顯然易見的公式: R(1,s)=1, R(2,s)=s, R(l_1,l_2,l_3, ... , l_r ; r)=R(l_2,l_1,l_3, ... , l_r ; r)=R(l_3,l_1,l_2, ... , l_r ; r)(將l_i的順序改變並不改變拉姆齐的數值)。

r,s 3 4 5 6 7 8 9 10
3 6 9 14 18 23 28 36 40 – 42
4 9 18 25 36 – 41 49 – 61 56 – 84 73 – 115 92 – 149
5 14 25 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 442
6 18 36 – 41 58 – 87 102 – 165 113 – 298 127 – 495 169 – 780 179 – 1171
7 23 49 – 61 80 – 143 113 – 298 205 – 540 216 – 1031 233 – 1713 289 – 2826
8 28 56 – 84 101 – 216 127 – 495 216 – 1031 282 – 1870 317 – 3583 317 – 6090
9 36 73 – 115 125 – 316 169 – 780 233 – 1713 317 – 3583 565 – 6588 580 – 12677
10 40 – 42 92 – 149 143 – 442 179 – 1171 289 – 2826 317 – 6090 580 – 12677 798 – 23556

R(3,3,3)=17

更詳盡的可見於http://www.combinatorics.org/Surveys/ds1/sur.pdf

R(3,3)等於6的證明[编辑]

K6 2colors.png

證明:在一個K_6的完全圖內,每邊塗上紅或藍色,必然有一個紅色的三角形或藍色的三角形。

  • 任意選取一個端點P,它有5條邊和其他端點相連。
  • 根據鴿巢原理,5條邊的顏色至少有3條相同,不失一般性設這種顏色是紅色。
  • 在這3條邊除了P以外的3個端點,它們互相連結的邊有3條。
    • 若這3條邊中任何一條是紅色,這條邊的兩個端點和P相連的2邊便組成一個紅色三角形。
    • 若這3條邊中任何一條都不是紅色,它們必然是藍色,因此,它們組成了一個藍色三角形。

而在K_5內,不一定有一個紅色的三角形或藍色的三角形。每個端點和毗鄰的兩個端點 的線是紅色,和其餘兩個端點的連線是藍色即可。这个定理的通俗版本就是友谊定理

RamseyTheory K5 no mono K3.PNG

外部链接[编辑]