拉姆齊理論

匈牙利語人名順序為先姓後名。本條目中的譯名遵從此順序。

拉姆齊理論得名自英國數學家兼哲學家弗蘭克·普倫普頓·拉姆齊，是數學的一支，在大而無迭序的結構中尋找必然出現的有迭序的子結構。拉姆齊理論研究的典型問題形如：「某某結構要何等大，才能保證具有某某性質？」更具體而言，葛立恆稱拉姆齊理論為「組合數學的分支」。^[1]

例子

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

例如，考慮 $n$ 階完全圖，即有 $n$ 個頂點，每個頂點皆與其餘 $n-1$ 個頂點各以一條邊相連。 $3$ 階完全圖稱為三角形。現將逐條邊染紅或藍。 $n$ 至少為何，才能保證總有一個同色（全紅或全藍的）三角形？答案為 $6$ 。拉姆齊定理的條目有此結論的嚴格證明。

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

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

成果

拉姆齊理論的著名定理有：

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

與范德瓦爾登定理類似的還有舒爾定理（英語：Schur's theorem）：給定任意 $c$ ，總有某個 $N$ ，使得：若將 $1,2,\ldots ,N$ 染成 $c$ 種色，則其中必有兩個數 $x,y$ ，使得 $x,y,x+y$ 三個數同色。此定理有許多推廣，如：雷多定理（英語：Rado's theorem (Ramsey theory)）、雷多－福克曼－桑德斯定理（英語：Rado–Folkman–Sanders theorem）、海恩德曼定理（英語：Hindman's theorem）、米利肯－泰勒定理（英語：Milliken–Taylor theorem）。關於上述結果（及許多其他結果）的參考書有葛立恆、布魯斯·羅斯柴爾德（英語：Bruce Lee Rothschild）、喬爾·斯賓塞（英語：Joel Spencer）、紹利莫希·約瑟夫（英語：József Solymosi）合著的《拉姆齊理論》（Ramsey Theory），該書於2015年曾更新擴展^[2]

特點

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

非構造性

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

界極大

雖然拉姆齊理論的結果斷言充份大的物件必定包含某個指定的結構，但證明經常要求該物件極巨大：常見指數增長甚至阿克曼函數增長的界。對某些小情況，已找到更好的上下界，但一般而言該些界未能改進。一些情況下，該些巨大的界是證明方法所遺留的，而無人知道能否實質改進。另一些情況下，已知任何界都必須異常大，甚至大於任何原始遞歸函數，例見帕里斯－哈靈頓定理（英語：Paris–Harrington theorem）。著名大數葛立恆數也是與拉姆齊理論有關的問題的上界。也有另一意義下巨大的例子：二染色畢氏三元組問題（英語：Boolean Pythagorean triples problem）的證明有200 TB長。^[3]

定理分類

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

拉姆齊類

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

圖蘭類

有時，某條拉姆齊類定理背後的原因很簡單：最大的分塊必然包含所求的子結構。此類結果稱為密度結果或圖蘭類結果，得名自圖蘭定理。著名例子有塞邁雷迪定理（范德瓦爾登定理的圖蘭類加強）以及黑爾斯－朱威特定理的密度版本。^[4]

參見

遍歷拉姆齊理論（英語：Ergodic Ramsey theory）
極值圖論（英語：Extremal graph theory）
古德斯坦定理
巴爾特·倫德特·范德瓦爾登（英語：Bartel Leendert van der Waerden）
差異理論（英語：Discrepancy theory）

參考資料

^ Graham, Ron; Butler, Steve. Rudiments of Ramsey Theory 2nd. American Mathematical Society. 2015: 1. ISBN 978-0-8218-4156-3 （英語）.
^ Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H.; Solymosi, József, Ramsey Theory 3rd, New York: John Wiley and Sons, 2015, ISBN 978-0470391853 （英語） .
^ Lamb, Evelyn. Two-hundred-terabyte maths proof is largest ever. Nature. 2016-06-02, 534 (7605): 17–18. PMID 27251254. doi:10.1038/nature.2016.19990  （英語）.
^ Furstenberg, Hillel; Katznelson, Yitzhak, A density version of the Hales–Jewett theorem, Journal d'Analyse Mathématique, 1991, 57 (1): 64–119, doi:10.1007/BF03041066 （英語） .

[1] Graham, Ron; Butler, Steve. Rudiments of Ramsey Theory 2nd. American Mathematical Society. 2015: 1. ISBN 978-0-8218-4156-3 （英語）.

[2] Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H.; Solymosi, József, Ramsey Theory 3rd, New York: John Wiley and Sons, 2015, ISBN 978-0470391853 （英語） .

[3] Lamb, Evelyn. Two-hundred-terabyte maths proof is largest ever. Nature. 2016-06-02, 534 (7605): 17–18. PMID 27251254. doi:10.1038/nature.2016.19990  （英語）.

[4] Furstenberg, Hillel; Katznelson, Yitzhak, A density version of the Hales–Jewett theorem, Journal d'Analyse Mathématique, 1991, 57 (1): 64–119, doi:10.1007/BF03041066 （英語） .

[1]

[2]

[3]

[4]