在組合數學上,拉姆齊定理(英語:Ramsey's theorem),又稱拉姆齊二染色定理,斷言對任意正整數
和
,若一個聚會的人數
足夠大,則無論相識關係如何,必定有
個人相識或
個人互不相識。給定
時,保證前述結論的最小
值稱為拉姆齊數
,其值取決於
。用圖論術語複述:若將足夠大的完全圖各邊染紅藍兩色,則不論如何染,必定有紅色的
階完全圖或藍色的
階完全圖。[註 1]
拉姆齊定理是組合數學的重要結論,以弗蘭克·普倫普頓·拉姆齊命名。他在1930年論文〈論形式邏輯的一個問題〉[1]證明此定理最初的版本,開創現稱拉姆齊理論的組合理論分支。拉姆齊理論的主題是從「無序」尋找「規律」,希望找出某數學結構中,存在規律子結構的一般條件。在拉姆齊定理的圖論表述中,此「規律子結構」是同色集(monochromatic set),即頂點集的子集,其中各邊皆染成同一顏色。
拉姆齊定理不止一條,前述版本的若干引伸仍稱拉姆齊定理。例如,可以將二染色推廣至更多種色,此時定理斷言:對任意色數
,和任意正整數
,必有某數
,使
階的完全圖各邊不論如何染
色,仍必可找到某
(介於
至
)和某
階完全子圖,其各邊皆染第
色。可見拉姆齊二染色定理是
的特例(同時取
)。