拉姆齐定理

维基百科，自由的百科全书

在組合數學上，拉姆齐(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₁,e₂)，使得K_n[e₁]中含有一個k邊形，K_n[e₁]含有一個l邊形，则称满足这个条件的最小的n为一个拉姆齐数。（注意：K_i按照图论的记法表示i阶完全图）

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

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

对于完全圖K_n的每條邊都任意塗上r種顏色之一，分別記為 e₁,e₂,e₃,...,e_r ，在K_n中，必定有個顏色為e₁的l₁邊形，或有個顏色為e₂的l₂邊形……或有個顏色為e_r的l_r邊形。符合條件又最少的數n則記為R(l₁,l₂,l₃,...,l_r;r)。

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

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

顯然易見的公式： R(1,s)=1， R(2,s)=s， R(l₁,l₂,l₃,...,l_r;r)=R(l₂,l₁,l₃,...,l_r;r)=R(l₃,l₁,l₂,...,l_r;r) （將l_i的順序改變並不改變拉姆齐的數值）。

r,s	3	4	5	6	7	8	9	10
3	6	9	14	18	23	28	36	40 – 43
4	9	18	25	35 – 41	49 – 61	56 – 84	69 – 115	92 – 149
5	14	25	43 – 49	58 – 87	80 – 143	101 – 216	121 – 316	141 – 442
6	18	35 – 41	58 – 87	102 – 165	111 – 298	127 – 495	169 – 780	178 – 1171
7	23	49 – 61	81 – 143	111 – 298	205 – 540	216 – 1031	232 – 1713	< 2826
8	28	56 – 84	101 – 216	127 – 495	216 – 1031	282 – 1870	317 – 3583	< 6090
9	36	69 – 115	121 – 316	169 – 780	232 – 1713	317 – 3583	565 – 6588	580 – 12677
10	40 – 43	92 – 149	141 – 442	178 – 1171	< 2826	< 6090	580 – 12677	798 – 23556

R(3,3,3)=17

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

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

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

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

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