拉姆齐理论

拉姆齐定律

拉姆齐理论是以英国数学家和哲学家弗兰克·P·拉姆齐（Frank P. Ramsey）的名字命名的，是数学的一个分支，致力于研究必须出现阶数的条件。 拉姆齐理论中的问题通常会问一个形式的问题：“某种结构中必须有多少个元素才能保证特定的财产能够持有”。拉姆齐理论的核心可以概括成：完全的无序是不可能的。从最初的拉姆齐定理到后来发展出的众多拉姆齐型定理都表明：一个集合只要元素数量达到某个临界值后，一定会出现我们预先定义好的某种性质或结构。组合数学的拉姆齐（Ramsey）定理在组合数学上，拉姆齐（Ramsey）定理，又称拉姆齐二染色定理，是要解决以下的问题：要找这样一个最小的数 n，使得 n 个人中必定有 k 个人相识或 k 个人互不相识。这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。6 个人中至少存在3人相互认识或者相互不认识。该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。

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

鸽笼原理也称作盒子原理Box Principle或抽屉原理Draw Principle。 简而言之就是将N+1只鸽子放入N个笼子，必然有一个笼子里的鸽子不止一只。 数学表示就是，如果要把km+1个对象放到m个盒子里，则至少有一个盒子里的对象不少于k+1只。 以荷兰数学家BL van der Waerden的名字命名的范德瓦尔登定理，描述的是： 对于 1,2,3,4...n 数字序列，如果随机把每个数字染上 种颜色，那么一定有k个颜色相同的数字形成等差数列。 如图所示，共n=8个数字，r=2种颜色，如果我们添加第9个数字是红色的，那么3、6、9这三个红色数字(k=3)形成等差数列，如果我们添加第9个数字是蓝色的，那么1、5、9三个蓝色数字（k=3）形成等差数列。 所以，范德瓦尔登数字计作 ,就是在2种颜色情况下形成3连等差的最少是9个数字。 tic-tac-teo是个极简单游戏，圆圈和叉叉两方，如果谁先竖向3个或者横向3个或者斜向45度3个连成一条线，那么就获胜。如图中叉叉右斜45度连成一条线获胜。 这个图可以换成数字坐标版本： 我们从上图可以发现，横向11，12，13可以获胜，竖向13，23，33可以获胜，这两种横竖获胜的三个数字中都有一位是相同的，比如13，23，33中第二位都是3. 斜线获胜额是11,22,33和13,22,31，对这种情况的规律是每一位数字都不同，比如13，22，31第一位是1-，2-，3-，第二位是-3,-2,-1。 这是二维坐标的情况，当然可以变成3维坐标或者4维坐标甚至更多（超级立方体）。 对于这个图，如果交互第一排第二个圈和第三个叉，那么就是平局。但是黑尔斯-朱厄特定理指出，当维度达到8的时候（就是每个位置需要8个数字表示），将不可能出现平局，也就是一定会有一方无可避免的连3个成一线。 黑尔斯-朱厄特定理的核心哲学就是没有绝对的随机，当随机达到一定程度的时候就必然出现带有规律的局部特征。 局部有序是随机的必然，有序和随机是辩证统一的。所以生命并不是宇宙的偶然，而是大量随机所产生的必然结果。 这带给我们以下问题： END

拉姆齐法则

拉姆齐法则（Ramsey Rule）


是指既然无法实现对包括 闲暇 在内的所有 商品 征收不产生 超额负担 的总额税，

则效率损失最小的条件是所有商品的边际 税收负担 相等。


拉姆齐法则是 英国剑桥大学 的 福利经济学 家 弗兰克·拉姆齐 最早在1927年提出的。



内容

拉姆齐在政府不能征收归总税的前提下给出了对不同 需求弹性 的商品如何征税才能做到效率损失最小的原则。

解读：


政府向地产商征税，或者向购房者征税，两者有区别吗？

经济学明白无误地告诉我们：两者没有任何区别。不管政府规定税赋是向哪一方征收的，都不影响买卖双方分担税负的比例。这是拉姆齐法则(RamseyRule)，任何接触税务问题的经济学学生必学的内容。


拉姆齐法则是说：在食盐的交易中，由于需求者好歹都得吃盐，需求较缺乏弹性，所以即使政府向供应者征税，税负也必定会转嫁给需求者；而在青菜的交易中，由于供应者好歹都得把当天的青菜卖掉，供给较缺乏弹性，所以即使政府向需求者征税，税负也必定会转嫁给供应者。

显而易见，政府以打击房地产高价为名而抽取的税收，并非无中生有、从天而降，而是供应者和需求者共同支付的——只是较缺乏弹性的一方，支付的比例较大；较富有弹性的一方，支付的比例较小而已。

拉姆齐二染色定理

“拉姆齐二染色定理”以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。拉姆齐数的定义拉姆齐数，用图论的语言有两种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e1]中含有一个k阶子完全图，Kn[e2]含有一个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)的值，我们要尝试毁灭这班外星人了。”显而易见的公式： R(1,s)=1， R(2,s)=s， R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r)（将li的顺序改变并不改变拉姆齐的数值）。　r,s 3 4 5 6 7 8 9 103 6 9 14 18 23 28 36 40 – 434 9 18 25 35 – 41 49 – 61 56 – 84 73 – 115 92 – 1495 14 25 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 4426 18 35 – 41 58 – 87 102 – 165 113 – 298 127 – 495 169 – 780 179 – 11717 23 49 – 61 80 – 143 113 – 298 205 – 540 216 – 1031 233 – 1713 289 – 28268 28 56 – 84 101 – 216 127 – 495 216 – 1031 282 – 1870 317 – 3583 317 – 60909 36 73 – 115 125 – 316 169 – 780 233 – 1713 317 – 3583 565 – 6588 580 – 1267710 40 – 43 92 – 149 143 – 442 179 – 1171 289 – 2826 317 – 6090 580 – 12677 798 – 23556R(3,3,3)=17 R(3,3)等于6的证明证明：在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。任意选取一个端点P，它有5条边和其他端点相连。根据鸽巢原理，3条边的颜色至少有两条相同，不失一般性设这种颜色是红色。在这3条边除了P以外的3个端点，它们互相连结的边有3条。若这3条边中任何一条是红色，这条边的两个端点和P相连的2边便组成一个红色三角形。若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了一个蓝色三角形。而在K5内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理

拉姆齐二染色定理是什么

拉姆齐二染色定理是一个数学组合问题，其命题是这样的：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。这个证明有一个附图。－－－－－－－－－－－－－－－－－------------------------------在组合数学上，拉姆齐（Ramsey）定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。拉姆齐数的定义拉姆齐数，用图论的语言有两种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e1]中含有一个k阶子完全图，Kn[e2]含有一个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)的值，我们要尝试毁灭这班外星人了。”显然易见的公式： R(1,s)=1， R(2,s)=s， R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r)（将li的顺序改变并不改变拉姆齐的数值）。r,s 3 4 5 6 7 8 9 103 6 9 14 18 23 28 36 40 – 434 9 18 25 35 – 41 49 – 61 56 – 84 73 – 115 92 – 1495 14 25 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 4426 18 35 – 41 58 – 87 102 – 165 113 – 298 127 – 495 169 – 780 179 – 11717 23 49 – 61 80 – 143 113 – 298 205 – 540 216 – 1031 233 – 1713 289 – 28268 28 56 – 84 101 – 216 127 – 495 216 – 1031 282 – 1870 317 – 3583 317 – 60909 36 73 – 115 125 – 316 169 – 780 233 – 1713 317 – 3583 565 – 6588 580 – 1267710 40 – 43 92 – 149 143 – 442 179 – 1171 289 – 2826 317 – 6090 580 – 12677 798 – 23556R(3,3,3)=17更详尽的可见于www.combinatorics.org/Surveys/ds1/sur.pdfR(3,3)等于6的证明证明：在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。任意选取一个端点P，它有5条边和其他端点相连。根据鸽巢原理，3条边的颜色至少有两条相同，不失一般性设这种颜色是红色。在这3条边除了P以外的3个端点，它们互相连结的边有3条。若这3条边中任何一条是红色，这条边的两个端点和P相连的2边便组成一个红色三角形。若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了一个蓝色三角形。而在K5内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点 的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

拉姆齐法则是什么呢?

拉姆齐法则是经济学税收的法则，其含义为为了使税收的超额负担达到最小，税率的制定应能够使得每种商品需求量减少的百分比相等。也就是说，只要从某种商品征得的最后一单位税收引起的效率损失大于其他的商品，那么就还有可能通过改变征税办法降低效率损失，只要适当降低该商品税率，提高其他商品税率，就能够实现效率损失最小化。拉姆齐法则其他情况简介。拉姆齐法则对最优商品税问题提出了极有价值的理论见解，但这并不表示它是完美无缺的。主要的批评集中在它并没有完全解决前面已指出的效率损失研究中的各种遗憾。拉齐姆法则只考虑了结合不同商品的需求弹性确定最优税率的问题，仍然没有考虑商品之间可能具有替代或互补的关系；也没有专门处理闲暇这类商品的征税问题。

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的每条边着上红色、蓝色或绿色，那么或者存在一个红Kn1，或者存在一个蓝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数的值。