拉姆齐定理

✍ dations ◷ 2025-10-24 10:54:02 #组合数学,数学定理,图染色

在组合数学上,拉姆齐(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}} 内,不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点的线是红色,和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。

相关

  • 死亡细胞死亡(Cell death)是描述生物细胞永久中止运作生理功能的状态。细胞死亡可能起因于个体计划性的细胞死亡,或是因疾病或创伤导致细胞不可逆的损伤而死亡。Category:Medical a
  • 新城市主义新城市主义(英语:New urbanism)是一种城市设计的理念,该理念希望建设可以容纳各种不同住房和工作岗位的步行社区,并改善环境。新城市主义起源于20世纪80年代初的美国,并逐渐影响了
  • 蒂宾根大学210百万欧元(不含医疗开支)蒂宾根大学 (Eberhard Karls Universität in Tübingen),,又译图宾根大学、杜宾根大学,位于德国蒂宾根,是德国最古老的大学之一,在自然科学和人文科学领域
  • 格列苯脲格列苯脲(INN),又名 优降糖(USAN),是一种磺酰脲类降糖药。市面上也可买到它与甲福明二甲双胍制成的合剂,名为 Glucovance。用来治疗2型糖尿病。截止到2007年,是世界卫生组织药典中两
  • 浑河抚清之战 · 萨尔浒之战 · 开铁之战 · 辽沈之战 · 镇江之战 · 林畔之战 · 广宁之战 · 辽南之战 · 亮马佃大捷 · 牛毛大捷 · 乌鸡关大捷 · 横
  • 闽南语中的古百越语词列表闽南语中的古百越语词列表
  • 布雷特·古斯瑞布雷特·古斯瑞(Brett Guthrie;1964年2月18日-)是美国的一位政治人物。自2009年开始,他是肯塔基州第二选举区选出的美国众议院议员。他的党籍是共和党。古斯瑞为美国陆军中尉。19
  • 恰利斯加奥恩恰利斯加奥恩(Chalisgaon),是印度马哈拉施特拉邦Jalgaon县的一个城镇。总人口91094(2001年)。该地2001年总人口91094人,其中男性47647人,女性43447人;0—6岁人口11440人,其中男6222人
  • 大车手《大车手》(英语:)是一部由史蒂芬·金于2010年所著的中篇小说,收录在中篇小说集《暗夜无星》内。故事于2014年被改编成同名电影《Big Driver(英语:Big Driver (film))》,由玛丽亚·
  • 台礁台礁(Platform reef,Table reef)生物礁体。为一种平顶孤立的珊瑚礁礁盘,其礁盘明显高出周围海底,而礁盘中央没有潟湖。很多台礁顶部中央非但没有低洼的潟湖,反而突出海面,形成由珊