拉姆齐定理

✍ dations ◷ 2025-10-22 04:07:59 #组合数学,数学定理,图染色

在组合数学上,拉姆齐(Ramsey)定理,又称拉姆齐二染色定理,是要解决以下的问题:要找这样一个最小的数 ,使得 个人中,无论相识关系如何,必定有 个人相识或 个人互不相识。

这个定理以弗兰克·普伦普顿·拉姆齐命名,1930年他在论文(《形式逻辑上的一个问题》)证明了R(3,3)=6。

拉姆齐数,用图论的语言有两种描述:

拉姆齐证明,对与给定的正整数数及,R(,)的答案是唯一和有限的。

拉姆齐数亦可推广到多于两个数:

已知的拉姆齐数非常少,保罗·艾狄胥曾以一个譬喻来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若他们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。”

显然易见的公式:R(0,)=0,R(1,)=1,R(2,)=, R ( l 1 , l 2 , l 3 , . . . , l r ) = R ( l 2 , l 1 , l 3 , . . . , l r ) = R ( l 3 , l 1 , l 2 , . . . , l r ) {\displaystyle \mathrm {R} (l_{1},l_{2},l_{3},...,l_{r})=R(l_{2},l_{1},l_{3},...,l_{r})=R(l_{3},l_{1},l_{2},...,l_{r})} (将 l i {\displaystyle l_{i}} 的顺序改变并不改变拉姆齐的数值)。

R(3,3,3)=17

更详尽的可见于

证明:在一个 K 6 {\displaystyle K_{6}} 的完全图内,每边涂上红或蓝色,必然有一个红色的三角形或蓝色的三角形。

而在 K 5 {\displaystyle K_{5}} 内,不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点的线是红色,和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。

相关

  • 绦虫见内文绦虫纲(学名:Cestoda)是一个寄生性扁形动物门的一个纲。人们常说的绦虫其实是多个物种的泛称。所有绦虫纲的物种都是寄生虫,其生活史可能各有不同,但这些物种的成虫寄生于
  • B淋巴细胞B细胞(B淋巴球)有时称之为“朝囊定位细胞”(bursa oriented cells),这是因为它们首次在鸡的腔上囊(Bursa of Fabricius)被提及的关系。在肠道的派亚氏腺体(Peyer's glands)中的淋巴组
  • 科学普及科学普及,简称科普,又称大众科学、流行科学(英语:popular science)或者普及科学,是指利用各种传媒以浅显的方式向普通大众普及科学技术知识,倡导科学方法、传播科学思想、弘扬科学
  • 东圣吉16号事件东圣吉16号事件是一起渔业纠纷事件,发生于2016年4月25日,屏东琉球籍渔船“东圣吉16号”在冲之鸟礁(日方称“冲之鸟岛”)东南东约150海里(280千米)国际水域作业时遭到日本公务船扣
  • 提乌德贝尔特二世提乌德贝尔特二世(Theudebert II)是墨洛温王朝的法兰克国王,奥斯特拉西亚国王(595年—612年在位)。奥斯特拉西亚及勃艮第国王希尔德贝尔特二世与妻子法伊洛贝(Faileube)的长子、勃
  • 剁椒鱼头剁椒鱼头,是中国八大菜系之一,湘菜的代表菜色。该菜以大鱼鱼头,辅以湖南特色调味料剁辣椒,一同蒸熟即可。剁椒鱼头味辣、偏咸鲜,尤以湖南湘潭所作最为出名。菜品色泽红亮、味浓、
  • Lambda Phi EpsilonLambda Phi Epsilon(或称ΛΦΕ、LPhiE、LFE、Lambdas、人中王)是个国际性、以社交为主的亚裔兄弟会。该会被多数希腊组织及联盟承认。其主要活动据点在美国及加拿大。Lambda
  • 张维 (力学家)张维(1913年5月22日-2001年10月4日),北京人,中国固体力学家。1913年出生于北京。1924年考入北京四中,15岁转考至天津北洋大学预科。1933年毕业于唐山交通大学,1938年获伦敦帝国理工
  • 俄罗斯国庆日俄罗斯国庆日,是俄罗斯联邦的国庆日。1990年6月12日俄罗斯联邦第一次人民代表大会通过了俄联邦国家主权宣言的日子。1992年,这一天被定为俄罗斯联邦国家主权宣言日,2002年后又
  • 协同反应协同反应(英语:Concerted Reaction)是一类键的断裂和形成同时发生的化学反应。这类反应不受溶剂、催化剂等的影响,反应机理既非离子型又非自由基型,而是往往通过一个环状过渡态进