拉姆齊法則詳解（拉姆齊定理有哪些）

1903年，弗蘭克·拉姆齊出生于英國倫敦，后來進入劍橋大學三一學院學習數學，成為了一名杰出的數學家、哲學家和經濟學家。可惜天妒英才，1930年就病逝于倫敦。但是在短短的歲月中，他在數學和其它領域做出了很多貢獻。今天所要談論的是他在1930年發表的論文《形式邏輯上的一個問題》所提出來的拉姆齊定理。

拉姆齊定理(Ramsey Theorem)是圖論中的一個重要概念，它被表述為對于任一具有N個頂點的完全圖(complete graph)，所有的頂點之間可以用紅色或藍色的線條聯結，圖中一定會呈現出完全一致的大子集——要么全紅，要么全藍。我們也可以先通過確定一致子集的大小，再根據拉姆齊定理反推出能夠形成該子集所需的完全圖。

△ 完全圖是指所有頂點間兩兩相連構成的圖。（圖片來源：LucyReading-Ikkanda/QuantaMagazine）

拉姆齊定理還有一個簡樸易懂的版本叫“情誼定理”：六個人當中至少有三個人相互熟悉（朋友）或者相互不熟悉（生疏人）。但為什么這個定理是準確的？為什么完全圖中的這些不同顏色的線條不能被完全打亂？數學家Jonathan Jedwab用一系列圖形直觀的解釋了這個定理為什么是準確的。

讓我們看一個簡樸的示例——一個六邊形的完全圖可以形成最少三條顏色一致的線組成的子集。這是為什么呢？

把這六個點看成六個人，其中任何一人與另一人必定處于熟悉或者不熟悉的狀態。若熟悉，我們將二人用紅線聯結；若不熟悉，則用藍線聯結。因此在這個社交小圈子中，每個人都輻射出五條線與其他五人相連，并且其中至少三條線的顏色相同。這意味著無論你怎樣聯結這些人，結果肯定會出現一個全紅或者全藍的三角形。

（圖片來源：QuantaMagazine）

首先我們來看1，從他身上發射出的五條線中，像之前說過的至少有三條線顏色相同。如果他熟悉2、4、5，則這三條線便是紅色。

（圖片來源：QuantaMagazine）

再看2和5，如果2和5相識，則2與5間的連線也是紅色，從而得到一個紅色的三角形。我們看看是否有辦法避免這樣的三角形產生，所以假定2與5互不相識，并將2、5之間用藍色線條標記。

（圖片來源：QuantaMagazine）

接下來再思索4和5的關系，同樣的，為了避免1、4、5形成紅色三角形，我們假設4、5也互不相識。

（圖片來源：QuantaMagazine）

最后考慮2和4的關系，結果發現不論2月4相識與否，都會形成一個紅色或藍色的三角形。于是一個單色的小色塊集合便會出現，拉姆齊定理得到印證。

（圖片來源：QuantaMagazine）

用這種辦法研究更大的集合中樣本時，比如數百萬、數千萬、數億的人群，能看到組成的單色色團由大量相同顏色的線段搭配而成。但畢竟這個“大量”有多大呢？數學家們并不能確定，在已知一個單色子集的大小前，我們無法明白形成它所需要的完全圖的最小大小。

拉姆齊定理也如其他許很多多日常運用的工具一樣——它相稱有用，但我們卻不盡了解其背后所有的工作原理。