拉姆齐定理

维基百科,自由的百科全书
(重定向自拉姆齊定理
跳到导航 跳到搜索

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

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

拉姆齐数的定義[编辑]

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

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

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

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

对于完全圖的每條邊都任意塗上r種顏色之一,分別記為,在中,必定有個顏色為阶子完全图,或有個顏色為阶子完全图……或有個顏色為阶子完全图。符合條件又最少的數n則記為

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

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

顯然易見的公式: R(0,s)=0, R(1,s)=1, R(2,s)=s(將的順序改變並不改變拉姆齐的數值)。

拉姆齐数R(r, s)的值/已知上下界 (OEIS中的数列A212954
s
r
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 2 3 4 5 6 7 8 9 10
3 6 9 14 18 23 28 36 40–42
4 18 25[1] 36–41 49–61 59[2]–84 73–115 92–149
5 43–48 58–87 80–143 101–216 133–316 149[2]–442
6 102–165 115[2]–298 134[2]–495 183–780 204–1171
7 205–540 217–1031 252–1713 292–2826
8 282–1870 329–3583 343–6090
9 565–6588 581–12677
10 798–23556

R(3,3,3)=17

更詳盡的可見於[1]

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

K6 2colors.png

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

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

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

RamseyTheory K5 no mono K3.PNG

外部链接[编辑]

  1. ^ Brendan D. McKay, Stanislaw P. Radziszowski. R(4,5) = 25 (PDF). Journal of Graph Theory. May 1995, 19 (3): 309–322. doi:10.1002/jgt.3190190304. 
  2. ^ 2.0 2.1 2.2 2.3 Exoo, Geoffrey; Tatarevic, Milos. New Lower Bounds for 28 Classical Ramsey Numbers. The Electronic Journal of Combinatorics. 2015, 22 (3): 3.