拉姆齐理论

數學分支

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

例子

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

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

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

上述結論為拉姆齊定理的特殊情況。該定理斷言,給定正整數 ,及正整數 ,則必存在某個正整數 ,使得不論 階完全圖 的邊如何染成 種顏色,仍有某個 ,令 包含某個所有邊皆為顏色  階同色完全子圖。取  即得上段的特殊情況。

成果

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

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

與范德瓦爾登定理類似的還有舒爾定理英语Schur's theorem:給定任意 ,總有某個 ,使得:若將 染成 種色,則其中必有兩個數  ,使得 三個數同色。此定理有許多推廣,如:雷多定理英语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]

參見

參考資料

  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 (英语) .