Loading AI tools
數學分支 来自维基百科,自由的百科全书
拉姆齐理论得名自英国数学家兼哲学家弗兰克·普伦普顿·拉姆齐,是数学的一支,在大而无迭序的结构中寻找必然出现的有迭序的子结构。拉姆齐理论研究的典型问题形如:“某某结构要何等大,才能保证具有某某性质?”更具体而言,葛立恒称拉姆齐理论为“组合数学的分支”。[1]
拉姆齐理论的典型例子中,先有某个数学结构,然后该数学结构会切成若干小份,问题是原结构要多大,才能保证不论切法为何,仍有某一份具有指定的性质。此想法带出分划正则性的严格定义。
例如,考虑阶完全图,即有个顶点,每个顶点皆与其余个顶点各以一条边相连。阶完全图称为三角形。现将逐条边染红或蓝。至少为何,才能保证总有一个同色(全红或全蓝的)三角形?答案为。拉姆齐定理的条目有此结论的严格证明。
换言之:若任一个宴会上有至少六人,则必有三人,该三人或两两互为朋友,或两两互为陌生人。此版本又称朋友与陌路人定理。
上述结论为拉姆齐定理的特殊情况。该定理断言,给定正整数,及正整数,则必存在某个正整数,使得不论阶完全图的边如何染成种颜色,仍有某个,令包含某个所有边皆为颜色的阶同色完全子图。取和即得上段的特殊情况。
拉姆齐理论的著名定理有:
与范德瓦尔登定理类似的还有舒尔定理:给定任意,总有某个,使得:若将染成种色,则其中必有两个数 ,使得三个数同色。此定理有许多推广,如:雷多定理、雷多-福克曼-桑德斯定理、海恩德曼定理、米利肯-泰勒定理。关于上述结果(及许多其他结果)的参考书有葛立恒、布鲁斯·罗斯柴尔德、乔尔·斯宾塞、绍利莫希·约瑟夫合著的《拉姆齐理论》(Ramsey Theory),该书于2015年曾更新扩展[2]
拉姆齐理论的结果通常有以下两个特点:
虽然拉姆齐理论的结果断言充份大的物件必定包含某个指定的结构,但证明经常要求该物件极巨大:常见指数增长甚至阿克曼函数增长的界。对某些小情况,已找到更好的上下界,但一般而言该些界未能改进。一些情况下,该些巨大的界是证明方法所遗留的,而无人知道能否实质改进。另一些情况下,已知任何界都必须异常大,甚至大于任何原始递归函数,例见帕里斯-哈灵顿定理。著名大数葛立恒数也是与拉姆齐理论有关的问题的上界。也有另一意义下巨大的例子:二染色毕氏三元组问题的证明有200 TB长。[3]
拉姆齐理论的成果可粗略分为两类:
若干定理与拉姆齐定理类似,断言某个大结构中,不论如何分划,都必有一块包含大的子结构,但不能得知该子结构位处何块。
有时,某条拉姆齐类定理背后的原因很简单:最大的分块必然包含所求的子结构。此类结果称为密度结果或图兰类结果,得名自图兰定理。著名例子有塞迈雷迪定理(范德瓦尔登定理的图兰类加强)以及黑尔斯-朱威特定理的密度版本。[4]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.