拉姆齐定理

拉姆齐数，用图论的语言有两种描述：

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

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

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

对于完全圖${\displaystyle K_{n}}$的每條邊都任意塗上r種顏色之一，分別記為${\displaystyle e_{1},e_{2},e_{3},...,e_{r}}$，在${\displaystyle K_{n}}$中，必定有個顏色為${\displaystyle e_{1}}$的${\displaystyle l_{1}}$阶子完全图，或有個顏色為${\displaystyle e_{2}}$的${\displaystyle l_{2}}$阶子完全图……或有個顏色為${\displaystyle e_{r}}$的${\displaystyle l_{r}}$阶子完全图。符合條件又最少的數n則記為${\displaystyle R(l_{1},l_{2},l_{3},...,l_{r})}$。

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

顯然易見的公式： R(0,s)=0， R(1,s)=1， R(2,s)=s， ${\displaystyle \mathrm {R} (l_{1},l_{2},l_{3},...,l_{r})=R(l_{2},l_{1},l_{3},...,l_{r})=R(l_{3},l_{1},l_{2},...,l_{r})}$（將${\displaystyle l_{i}}$的順序改變並不改變拉姆齐的數值）。

R(3,3,3)=17

更詳盡的可見於

證明：在一個${\displaystyle K_{6}}$的完全圖內，每邊塗上紅或藍色，必然有一個紅色的三角形或藍色的三角形。

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

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

• 证明R(3,6) = 18

1. Brendan D. McKay, Stanislaw P. Radziszowski. (PDF). Journal of Graph Theory. May 1995, 19 (3): 309–322. doi:10.1002/jgt.3190190304.
2. Exoo, Geoffrey; Tatarevic, Milos. . The Electronic Journal of Combinatorics. 2015, 22 (3): 3.