拉姆齐定理
数学定理 / 维基百科,自由的 encyclopedia
在组合数学上,拉姆齐定理(英语:Ramsey's theorem),又称拉姆齐二染色定理,断言对任意正整数和,若一个聚会的人数足够大,则无论相识关系如何,必定有个人相识或个人互不相识。给定时,保证前述结论的最小值称为拉姆齐数,其值取决于。用图论术语复述:若将足够大的完全图各边染红蓝两色,则不论如何染,必定有红色的阶完全图或蓝色的阶完全图。[注 1]
此条目目前正依照en: Ramsey's theorem上的内容进行翻译。 (2021年12月21日) |
拉姆齐定理是组合数学的重要结论,以弗兰克·普伦普顿·拉姆齐命名。他在1930年论文《论形式逻辑的一个问题》[1]证明此定理最初的版本,开创现称拉姆齐理论的组合理论分支。拉姆齐理论的主题是从“无序”寻找“规律”,希望找出某数学结构中,存在规律子结构的一般条件。在拉姆齐定理的图论表述中,此“规律子结构”是同色集(monochromatic set),即顶点集的子集,其中各边皆染成同一颜色。
拉姆齐定理不止一条,前述版本的若干引伸仍称拉姆齐定理。例如,可以将二染色推广至更多种色,此时定理断言:对任意色数,和任意正整数,必有某数,使阶的完全图各边不论如何染色,仍必可找到某(介于至)和某阶完全子图,其各边皆染第色。可见拉姆齐二染色定理是的特例(同时取)。