拉姆齐定理

✍ dations ◷ 2025-07-22 05:28:31 #组合数学,数学定理,图染色

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

相关

  • 千禧高峰会千禧高峰会(英语:Millennium Summit)是于2000年9月6日至9月8日在纽约市联合国总部大楼举行,由世界各国领袖参与、为期三天的会议,旨在讨论21世纪以后联合国的地位和角色。在会议
  • SbHsub3/sub锑化氢,是化学式为SbH3的化合物,是具有恶臭气味的无色剧毒气体,不稳定。与氨同类,是主要的锑氢化物。其为三角锥结构,H–Sb–H 键角为 91.7°,Sb–H 键长 1.707Å(170.7pm)。锑化氢
  • 甘博甘博(英语:Sidney David Gamble,1890年7月12日-1968年3月29日),美国社会学家。他曾四度前往中国,其间拍摄过大量有关中国的珍贵照片。甘博出生于俄亥俄州辛辛那提,他是宝洁公司创始
  • 寸部寸部,为汉字索引里为部首之一,康熙字典214个部首中的第四十一个(三划的则为第十二个)。就繁体和简体中文中,寸部归于三划部首。寸部通常是从下、右方均可为部字,且无其他部首可用
  • 鱼鳍鱼鳍是鱼类最明显的一个特征,是大部分鱼类用来游动的器官。在不同部位的鱼鳍有不同的作用,例如向上、向下、前进、后退或者保持身体平衡都需要动用或协调不同的鳍。鳍的功能也
  • 埃维语埃维语( 或 ,发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gentium","Gentium Alte
  • 户田忠温户田忠温(日语:戸田忠温/とだ ただはる ,1804年2月26日-1851年8月22日)是日本江户时代后期的谱代大名,下野宇都宫藩(日语:宇都宮藩)第4代藩主,宇都宫藩户田氏(日语:戸田氏)第10代。忠温是
  • 卡里斯·范·豪滕卡里斯·范·豪滕(Carice Anouk van Houten,发音为/karis anuk fɑn ˈhʌutɛn/,1976年9月5日-)一位荷兰女演员与歌手。自2012年在美国电视剧集《权力游戏》中饰演红袍女巫一角
  • 在地球上恋爱《在地球上恋爱》(韩语:지구에서 연애중;英语:)为2008年由郑钦文执导的韩国电影。朴有天(朴有天 饰)是一名高中生,他的班上来了一位新的班导洪秀贤(徐玄振 饰),新导师是他的老婆这件事
  • 文康文康,生卒年月不详,费莫氏,字铁仙,一字悔庵,别号燕北闲人,清朝小说家,满洲镶红旗人。祖父为大学士勒保,父英绶。文康在世时间大致为道光初年到光绪初年,曾任理藩院郎中、驻藏大臣、徽