拉姆齐理论

數學分支

拉姆齐理论得名自英国数学家兼哲学家弗兰克·普伦普顿·拉姆齐,是数学的一支,在大而无迭序的结构中寻找必然出现的有迭序的子结构。拉姆齐理论研究的典型问题形如:“某某结构要何等大,才能保证具有某某性质?”更具体而言,葛立恒称拉姆齐理论为“组合数学的分支”。[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 (英语) .