拉姆齐理论
拉姆齐理论得名自英国数学家兼哲学家弗兰克·普伦普顿·拉姆齐,是数学的一支,在大而无迭序的结构中寻找必然出现的有迭序的子结构。拉姆齐理论研究的典型问题形如:“某某结构要何等大,才能保证具有某某性质?”更具体而言,葛立恒称拉姆齐理论为“组合数学的分支”。[1]
例子
拉姆齐理论的典型例子中,先有某个数学结构,然后该数学结构会切成若干小份,问题是原结构要多大,才能保证不论切法为何,仍有某一份具有指定的性质。此想法带出分划正则性的严格定义。
例如,考虑阶完全图,即有个顶点,每个顶点皆与其余个顶点各以一条边相连。阶完全图称为三角形。现将逐条边染红或蓝。至少为何,才能保证总有一个同色(全红或全蓝的)三角形?答案为。拉姆齐定理的条目有此结论的严格证明。
换言之:若任一个宴会上有至少六人,则必有三人,该三人或两两互为朋友,或两两互为陌生人。此版本又称朋友与陌路人定理。
上述结论为拉姆齐定理的特殊情况。该定理断言,给定正整数,及正整数,则必存在某个正整数,使得不论阶完全图的边如何染成种颜色,仍有某个,令包含某个所有边皆为颜色的阶同色完全子图。取和即得上段的特殊情况。
成果
拉姆齐理论的著名定理有:
- 范德瓦尔登定理:对任意,必有某个,使得:若将个连续正整数染成种颜色,则必有长度为的同色等差数列。
- 黑尔斯-朱威特定理 :对任意和,必有某个使得:若将维的立方体中,每个单位立方体染色之一,则必有某个方向(允许某些特定的斜向)的连线上,全部个小立方体皆同色。换言之:在多人版过关(井字过三关的推广)中,不论玩家人数为何,也不论为何,只要维数足够高,则必有一人先获胜,而不可能出现平局。该定理可推出范德瓦尔登定理。
与范德瓦尔登定理类似的还有舒尔定理:给定任意,总有某个,使得:若将染成种色,则其中必有两个数 ,使得三个数同色。此定理有许多推广,如:雷多定理、雷多-福克曼-桑德斯定理、海恩德曼定理、米利肯-泰勒定理。关于上述结果(及许多其他结果)的参考书有葛立恒、布鲁斯·罗斯柴尔德、乔尔·斯宾塞、绍利莫希·约瑟夫合著的《拉姆齐理论》(Ramsey Theory),该书于2015年曾更新扩展[2]
特点
拉姆齐理论的结果通常有以下两个特点:
非构造性
可能证明了某个结构存在,但却并无给出构造该个结构的方法(除暴力搜索外)。例如,过程中可能采用鸽巢原理,便是非构造性的。
界极大
虽然拉姆齐理论的结果断言充份大的物件必定包含某个指定的结构,但证明经常要求该物件极巨大:常见指数增长甚至阿克曼函数增长的界。对某些小情况,已找到更好的上下界,但一般而言该些界未能改进。一些情况下,该些巨大的界是证明方法所遗留的,而无人知道能否实质改进。另一些情况下,已知任何界都必须异常大,甚至大于任何原始递归函数,例见帕里斯-哈灵顿定理。著名大数葛立恒数也是与拉姆齐理论有关的问题的上界。也有另一意义下巨大的例子:二染色毕氏三元组问题的证明有200 TB长。[3]
定理分类
拉姆齐理论的成果可粗略分为两类:
拉姆齐类
若干定理与拉姆齐定理类似,断言某个大结构中,不论如何分划,都必有一块包含大的子结构,但不能得知该子结构位处何块。
图兰类
有时,某条拉姆齐类定理背后的原因很简单:最大的分块必然包含所求的子结构。此类结果称为密度结果或图兰类结果,得名自图兰定理。著名例子有塞迈雷迪定理(范德瓦尔登定理的图兰类加强)以及黑尔斯-朱威特定理的密度版本。[4]
参见
参考资料
- ^ 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 (英语).