查看“︁拉姆齐理论”︁的源代码

{{for2|無窮集上的拉姆齊理論|[[無窮元組合學]]}}
{{Eastern name order|匈牙利语|匈牙利人名}}

'''拉姆齊理論'''得名自英國數學家兼哲學家[[弗蘭克·普倫普頓·拉姆齊]]，是[[數學]]的一支，在大而無迭序的結構中尋找必然出現的有迭序的子結構。拉姆齊理論研究的典型問題形如：「某某結構要何等大，才能保證具有某某性質？」更具體而言，[[葛立恆]]稱拉姆齊理論為「[[組合數學]]的分支」。<ref>{{cite book| last = Graham | first = Ron | last2 = Butler | first2 = Steve | title = Rudiments of Ramsey Theory | edition = 2nd  | year = 2015 | publisher = American Mathematical Society | isbn = 978-0-8218-4156-3 | page = 1 |language = en}}</ref>

==例子==
拉姆齊理論的典型例子中，先有某個數學結構，然後該數學結構會切成若干小份，問題是原結構要多大，才能保證不論切法為何，仍有某一份具有指定的性質。此想法帶出{{le|分劃正則性|partition regularity}}的嚴格定義。

例如，考慮<math>n</math>階[[完全圖]]，即有<math>n</math>個頂點，每個頂點皆與其餘<math>n-1</math>個頂點各以一條邊相連。<math>3</math>階完全圖稱為三角形。現將逐條邊染紅或藍。<math>n</math>至少為何，才能保證總有一個'''同色'''（全紅或全藍的）三角形？答案為<math>6</math>。[[拉姆齐定理#R(3,3)等於6的證明|拉姆齊定理]]的條目有此結論的[[數學證明|嚴格證明]]。

換言之：若任一個宴會上有至少六人，則必有三人，該三人或兩兩互為朋友，或兩兩互為陌生人。此版本又稱[[友誼定理|朋友與陌路人定理]]。

上述結論為[[拉姆齊定理]]的特殊情況。該定理斷言，給定正整數<math>c</math>，及正整數<math>n_1, n_2, \ldots, n_c</math>，則必存在某個正整數<math>R(n_1, \ldots, n_c)</math>，使得不論<math>R(n_1, \ldots, n_c)</math>階完全圖<math>G</math>的邊如何染成<math>c</math>種顏色，仍有某個<math>i \ (1 \le i \le c)</math>，令<math>G</math>包含某個所有邊皆為顏色<math>i</math>的<math>n_i</math>階同色完全子圖。取<math>c = 2</math>和<math>n_1 = n_2 = 3</math>即得上段的特殊情況。

==成果==
拉姆齊理論的著名定理有：

* [[范德瓦爾登定理]]：對任意<math>c, n</math>，必有某個<math>V</math>，使得：若將<math>V</math>個連續正整數染成<math>c</math>種顏色，則必有長度為<math>n</math>的同色[[等差數列]]。
* {{le|黑爾斯－朱威特定理|Hales–Jewett theorem}}<!--按[[托馬斯·黑爾斯]]和[[巨海豚屬]]中Jewett Sand Formation的先例--> ：對任意<math>n</math>和<math>c</math>，必有某個<math>H</math>使得：若將<math>H</math>維的<math>n \times n \times \cdots \times n</math>立方體中，每個單位立方體染<math>c</math>色之一，則必有某個方向（允許某些特定的斜向）的連線上，全部<math>n</math>個小立方體皆同色。換言之：在多人版過<math>n</math>關（[[井字過三關]]的推廣）中，不論玩家人數為何，也不論<math>n</math>為何，只要維數足夠高，則必有一人先獲勝，而不可能出現平局。該定理可推出[[范德瓦爾登定理]]。

與范德瓦爾登定理類似的還有{{le|舒爾定理|Schur's theorem}}：給定任意<math>c</math>，總有某個<math>N</math>，使得：若將<math>1, 2, \ldots, N</math>染成<math>c</math>種色，則其中必有兩個數<math>x, y</math> ，使得<math>x, y, x+y</math>三個數同色。此定理有許多推廣，如：{{le|雷多定理 (拉姆齊理論)|Rado's theorem (Ramsey theory)|雷多定理}}<!--按[[柯召]]中Erdős–Ko–Rado的先例-->、{{le|雷多－福克曼－桑德斯定理|Rado–Folkman–Sanders theorem}}<!--按[[猶大·福克曼]]的先例-->、{{le|海恩德曼定理|Hindman's theorem}}<!--按《世界人名翻譯大辭典》-->、{{le|米利肯－泰勒定理|Milliken–Taylor theorem}}<!--按[[米利肯 (科羅拉多州)]]的先例-->。關於上述結果（及許多其他結果）的參考書有[[葛立恆]]、{{le|布魯斯·羅斯柴爾德|Bruce Lee Rothschild}}、{{le|喬爾·斯賓塞|Joel Spencer}}、{{le|紹利莫希·約瑟夫|József Solymosi}}合著的《拉姆齊理論》（''Ramsey Theory''），該書於2015年曾更新擴展<ref>{{Citation |author-link=葛立恆 |first=Ronald L. |last=Graham 
 |first2=Bruce L.|last2=Rothschild 
 |first3=Joel H. |last3=Spencer 
 |first4=József |last4=Solymosi 
|title=Ramsey Theory 
|publisher=John Wiley and Sons 
|location=New York 
|year=2015 
|isbn=978-0470391853 
|edition=3rd 
|language = en}}.</ref>

===特點===
拉姆齊理論的結果通常有以下兩個特點：

====非構造性====
可能證明了某個結構存在，但卻並無給出構造該個結構的方法（除[[暴力搜索]]外）。例如，過程中可能採用[[鴿巢原理]]，便是非[[構造性證明|構造性]]的。

====界極大====
雖然拉姆齊理論的結果斷言充份大的物件必定包含某個指定的結構，但證明經常要求該物件極巨大：常見[[指數增長]]甚至[[阿克曼函數|阿克曼函數增長]]的界。對某些小情況，已找到更好的上下界，但一般而言該些界未能改進。一些情況下，該些巨大的界是證明方法所遺留的，而無人知道能否實質改進。另一些情況下，已知任何界都必須異常大，甚至大於任何[[原始遞歸函數]]，例見{{le|帕里斯－哈靈頓定理|Paris–Harrington theorem}}<!--按[[帕里斯麗脂鯉]]和[[德斯蒙·哈靈頓]]的先例-->。著名大數[[葛立恆數]]也是與拉姆齊理論有關的問題的上界。也有另一意義下巨大的例子：{{le|二染色畢氏三元組問題|Boolean Pythagorean triples problem}}的證明有200 [[太字节|TB]]長。<ref>{{Cite journal|last=Lamb|first=Evelyn|date=2016-06-02|title=Two-hundred-terabyte maths proof is largest ever|journal=Nature|language=en|volume=534|issue=7605|pages=17–18|doi=10.1038/nature.2016.19990|pmid=27251254|doi-access=free }}</ref>

===定理分類===
拉姆齊理論的成果可粗略分為兩類：

====拉姆齊類====
若干定理與拉姆齊定理類似，斷言某個大結構中，不論如何[[集合劃分|分劃]]，都必有一塊包含大的子結構，但不能得知該子結構位處何塊。

====圖蘭類====
有時，某條拉姆齊類定理背後的原因很簡單：最大的分塊必然包含所求的子結構。此類結果稱為'''密度結果'''或'''圖蘭類結果'''，得名自[[圖蘭定理]]。著名例子有[[塞邁雷迪定理]]（范德瓦爾登定理的圖蘭類加強）以及黑爾斯－朱威特定理的密度版本。<ref>{{Citation |author-link=希勒爾·弗斯滕伯格 |first=Hillel |last=Furstenberg |first2=Yitzhak |last2=Katznelson |title=A density version of the Hales–Jewett theorem |journal=Journal d'Analyse Mathématique |volume=57 |issue=1 |year=1991 |pages=64–119 |doi=10.1007/BF03041066 |language = en}}.</ref>

== 參見 ==
* {{le|遍歷拉姆齊理論|Ergodic Ramsey theory}}
* {{le|極值圖論|Extremal graph theory}}
* [[古德斯坦定理]]
* {{le|巴爾特·倫德特·范德瓦爾登|Bartel Leendert van der Waerden}}<!--按[[埃米·諾特]]中的先例-->
* {{le|差異理論|Discrepancy theory}}<!--按[[克勞斯·羅特]]中的先例-->

== 參考資料 ==
{{Reflist}}

<!--:en:另有參考書-->

[[Category:拉姆齊理論]]