数学定理列表的L？【科普】拉姆齐定理RamseyTheory-1

数学定理列表的L

零一律卢辛定理勒贝格控制收敛定理勒文海姆-斯科伦定理罗尔定理拉格朗日定理 (群论)拉格朗日中值定理拉姆齐定理拉克斯-米尔格拉姆定理黎曼映射定理吕利耶定理勒让德定理拉格朗日定理 (数论)勒贝格微分定理雷维收敛定理刘维尔定理六指数定理黎曼级数定理林德曼-魏尔斯特拉斯定理　　洛必达法则

【科普】拉姆齐定理RamseyTheory-1

拉姆齐定理揭示了无序中必然出现有序的辩证统一。

Frank P. Ramsey弗兰克·拉姆齐，1903~1930，英国哲学家、数学家和经济学家。 是的，你没看错，拉姆齐生年仅到26岁便英年早逝。 拉姆齐在数学和逻辑方面的一个重要贡献就是1928年他提出的一个组合数学理论，即后来以他的名字命名的拉姆齐定理（拉姆齐理论）。

这是一个组合数学中的问题，拉姆齐定理，也称之为拉姆齐二染色定理。它的直观描述是：

在超过6人的群体中，必然有3个人互相都认识或者有3个人互相都不认识。

换个说法：

在平面上超过6个点组成的群体中，必然有3个点互相连接成为三角形或者3个点互不相连。

再换个说法： 在一个完整的6阶图中，即6个点且每个点都和其他所有点进行连线，如果连线有红蓝两种，那么必然有一个红色三角形或者蓝色三角形。

或者说： 使得n个人中至少有k个人互相认识或u个人互相不认识，即R(k,u)=n。如果k=3，u=3，那么n最小值是6。

如图咋知道R(3,3)=6,R(4,4)=18...

友谊定理是指：在一群人数不少于三的人群中，若任意两人都刚好只有一个共同认识的人，这群人中总有一人是所有人都认识的。

在图论的角度来说，一幅图，若每个顶点都跟另一个顶点刚好只有一个共同相邻的顶点，这幅图中有一个顶点和其他顶点都相邻。

如图，友谊定理的图表示也称为友谊图，或者风车图，或n-fan图，最左侧的蝴蝶结装造型也称为蝴蝶图。

拉姆齐定理还有几个推论，例如：范德瓦尔登定理、Hales-Jewett定理、舒尔定理、Rado定理等。

END

拉姆齐定理的拉姆齐数的定义

拉姆齐数，用图论的语言有两种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn含有一个l边形，则称满足这个条件的最小的n为一个拉姆齐数。（注意：Ki按照图论的记法表示i阶完全图）拉姆齐证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。拉姆齐数亦可推广到多于两个数：对于完全图Kn的每条边都任意涂上r种颜色之一，分别记为 e1,e2,e3,...,er ，在Kn中，必定有个颜色为e1的l1边形，或有个颜色为e2的l2边形……或有个颜色为er的lr边形。符合条件又最少的数n则记为R(l1,l2,l3,...,lr;r)。拉姆齐数的数值或上下界已知的拉姆齐数非常少，保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”显然易见的公式：1°R(1,s)=12°R(2,s)=s R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r) （将li的顺序改变并不改变拉姆齐的数值）

拉姆齐(Ramsly)二染色定理是什么

Ramsey定理：　Ramsey(1903~1930)是英国数理逻辑学家,他把抽屉原理加以推广，得出广义抽屉原理，也称为Ramsey定理。 　　Ramsey定理（狭义）的内容：任意六个人中要么至少三个人认识，要么至少三个不认识 　　证明如下：首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设：如果两个人识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。由抽屉原则可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若**或CD为红色，则结论显然成立。若**和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识。希望采纳，谢谢o(∩_∩)o

Ramsey定理的Ramsey数

一对常数a和b，对应于一个整数r，使得r个人中或有a个人相互认识，或有b个人互不认识；或有a个人互不认识，或有b个人相互认识。这个数r的最小值用R(a,b)来表示，也就是R(a,b)个顶点的完全图。用红蓝两种颜色进行着色，无论何种情况必至少存在以下两者之一：(1)一个a个顶点着红颜色的完全子图，或一个b个顶点着蓝颜色的完全子图；(2)一个a个顶点着蓝颜色的完全子图，或一个b个顶点着红颜色的完全子图。上述问题可以看作是R(3,3)=6的一个特例，上面的证明利用图的形象而直观的特点，证明了R(3,3)=6。下面不用图给出R(3,3)=6的证明：对于A以外的5个人可分为Friend和Strange两个集合。Friend=其余5人中与A互相认识的集合；Strange=其余5人中与A互相不认识的集合。根据抽屉原理，Friend和Strange中有一个集合至少有3个人，不妨假设是集合Friend。Friend中3个人P,Q,R若是彼此互相不认识，则问题已得到证明。否则有两个人互相认识，不妨设这两个人是P和Q，则A，P，Q这3个人彼此认识。若是集合Strange至少有3个人，可以同样讨论如下：若Strange有3人L，M，N彼此互相认识，则问题的条件已得到满足。否则设L和M互不相识，则A，L，N互不相识。可以把推理过程形象地表示，如图所示：虽然R(3,3)的证明十分巧妙，但是实际上已知的Ramsey数非常少，比如R(3,3)=6，R(3,4)=9，R(4,4)=18保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”Ramsey证明，对于给定的正整数数k及l，R(k,l)的答案是唯一和有限的。目前的进展如下图所示（很多只有一个范围）：　　更一般的Ramsey数若把以上讨论中红、蓝两种颜色改为k种颜色c1,c2,...,ck，把存在a条边的同色完全图，或b条边的同色完全图，改为或a1,或a2,...，或a条边的同色完全图，即得到Ramsey数R(a1,a2,...,ak)，即对r个顶点的完全图，用k种颜色c1,c2,...,ck任意染色，必然是或出现以c1颜色的a1个顶点的完全图,或出现以c2颜色的a2个顶点的完全图，...,或出现以ck颜色的ak个顶点的完全图，这样的整数r的最小值用R(a1,a2,...ak)表示。针对Ramsey定理扩展到任意多种颜色的情况，我们给出一个非常简略的介绍。如果n1，n2和n3都是大于或等于2的整数，则存在整数p，使得Kp→Kn1，Kn2，Kn3。也就是说，如果把Kp的每条边着上红色、蓝色或绿色，那么或者存在一个**n1，或者存在一个蓝Kn2，或者存在一个绿Kn3。使该结论成立的最小整数p称为Ramsey数r(n1，n2，n3)。已知这种类型的仅有的非平凡Ramsey数为r(3，3，3)=17。因此，K17→K3，K3，K3，而K16→K3，K3，K3。我们可以用类似的方法定义Ramsey数r(n1，n2，…，nk)，而对于点对Ramsey定理的完全一般形式是这些数存在；即存在整数p，使得Kp→Kn1，Kn2，…，Knk成立。Ramsey定理还有更一般的形式，在这种形式中点对（两个元素的子集）换成了t个元素的子集，其中t≥1是某个整数。令Ktn表示n元素集合中所有t个元素的子集的集合。将上面的概念扩展，Ramsey定理的一般形式可叙述如下：给定整数t≥2及整数q1，q2，…，qk≥t，存在一个整数p，使得Ktp→Ktq1，Ktq2，…，Ktqk成立。也就是说，存在一个整数p，使得如果给p元素集合中的每一个t元素子集指定k种颜色c1，c2，…，ck中的一种，那么或者存在q1个元素，这些元素的所有t元素子集都被指定为颜色c1，或者存在q2个元素，这些元素的所有t元素子集都被指定为颜色c2，…，或者存在qk个元素，它的t元素子集都被指定为颜色ck。这样的整数中最小的整数p为Ramsey数rt(q1，q2，…，qk)。假设t=1。于是，r1(q1，q2，…，qk)就是满足下面条件的最小的数p：如果p元素集合的元素被用颜色c1，c2，…，ck中的一种颜色着色，那么或者存在q1个都被着成颜色c1的元素，或者存在q2个都被着成颜色c2的元素，…，或者存在qk个都被着成颜色ck的元素。因此，根据鸽巢原理的加强版，有r1(q1，q2，…，qk)=q1+q2+…+qk-k+1这就证明Ramsey定理是鸽巢原理的加强版的扩展。确定一般的Ramsey数rt(q1，q2，…，qk)是一个困难的工作。关于它们的准确值我们知道得很少。但不难看出，rt(t，q2，…，qk)=rt(q2，…，qk)并且q1，q2，…，qk的排列顺序不影响Ramsey数的值。

如何证明拉姆齐定理R(3,3)=6 多种方法

多种方法这个要求我估计是达不到了...不过一个等价命题是比较好证明的：如果在平面上给出六个（任意三个不共线的）点,只能用红线和黑线在它们之间连接,证明要不有一个三边都为红色的三角形,要不有一个三边都为黑色的三角形；并且如果只给5个这样的点（任意三点不共线）,可以构造出既没有三边都为红色的三角形,也没有一个三边都为黑色的三角形. 考虑其中任意一个点A,设其余的点为**DEF,那么根据抽屉原理,AB,AC,AD,AE,AF这五条边中至少有三条是同一种颜色的. 那么我们不妨设AB,AC,AD都是红色的. 1)如果**,BD,CD这三条都是黑色的,那么**D就是一个黑色三角形,满足要证的条件 2)如果**,BD,CD这三条中至少有一条红色,那么结合AB,AC,AD都是红色,可以找到一个红色的三角形. 于是这六个点被红黑两种颜色连接的15条线段中,要不有一个三边都为红色的三角形,要不有一个三边都为黑色的三角形. 下面给出5个点的构造.（抱歉我不会上图,我描述下你自己画吧,挺容易的.） 假想一个正五边形,这个正五边形的五条边都是红色的.连出剩下的10条对角线,都用黑色.这样一来就的确既没有三边都为红色的三角形,也没有一个三边都为黑色的三角形. 这就是R(3,3)=6的证明.如果你感兴趣的话,可以试试看R(3,4)和R(4,4),都挺有意思的.有什么我没有写明白的地方,请一定追问,我会尽力解答.

Ramsey定理的介绍

Frank Plumpton Ramsey（弗兰克·普伦普顿·拉姆齐，1903-1930）是英国1哲学家、数学家、经济学家，26 岁英年早逝，对经济学纯理论是一个重大损失，尽管他的主要兴趣在哲学和数理逻辑方面。关于他的身份，也是十分高贵的，他是剑桥皇家学院会员、温彻斯特和三一学院昔日的学者、马格达兰校长之子 。在组合数学中的Ramsey定理，又称拉姆齐二染色定理，涉及Ramsey数和Ramsey问题，关于Ramsey问题有一个广泛流传的例子，即世界上任意6个人中，总有3个人相互认识，或互相皆不认识。

如何证明拉姆齐定理R(3,3)=6

多种方法这个要求我估计是达不到了...不过一个等价命题是比较好证明的：如果在平面上给出六个（任意三个不共线的）点，只能用红线和黑线在它们之间连接，证明要不有一个三边都为红色的三角形，要不有一个三边都为黑色的三角形；并且如果只给5个这样的点（任意三点不共线），可以构造出既没有三边都为红色的三角形，也没有一个三边都为黑色的三角形。 考虑其中任意一个点A, 设其余的点为**DEF, 那么根据抽屉原理，AB,AC,AD,AE,AF这五条边中至少有三条是同一种颜色的。那么我们不妨设AB,AC,AD都是红色的。1)如果**,BD,CD这三条都是黑色的，那么**D就是一个黑色三角形，满足要证的条件2)如果**,BD,CD这三条中至少有一条红色，那么结合AB,AC,AD都是红色，可以找到一个红色的三角形。 于是这六个点被红黑两种颜色连接的15条线段中，要不有一个三边都为红色的三角形，要不有一个三边都为黑色的三角形。 下面给出5个点的构造。（抱歉我不会上图，我描述下你自己画吧，挺容易的。）假想一个正五边形，这个正五边形的五条边都是红色的。连出剩下的10条对角线，都用黑色。这样一来就的确既没有三边都为红色的三角形，也没有一个三边都为黑色的三角形。 这就是R(3,3)=6的证明。如果你感兴趣的话，可以试试看R(3,4)和R(4,4)，都挺有意思的。有什么我没有写明白的地方，请一定追问，我会尽力解答。