跳转到内容

拉姆齐理论

维基百科,自由的百科全书

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