拉姆齊法則_拉姆齊法則詳解（拉姆齊定理有哪些）?以下由小編為大家?guī)斫榻B。

1903年，弗蘭克·拉姆齊出生于英國倫敦，后來進入劍橋大學三一學院學習數(shù)學，成為了一名杰出的數(shù)學家、哲學家和經(jīng)濟學家。可惜天妒英才，1930年就病逝于倫敦。但是在短短的歲月中，他

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

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

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

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

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

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

（圖片來源：QuantaMagazine）

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

（圖片來源：QuantaMagazine）

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

（圖片來源：QuantaMagazine）

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

（圖片來源：QuantaMagazine）

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

（圖片來源：QuantaMagazine）

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

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