拉姆齐理论
激励的例子
拉姆齐定理是拉姆齐理论最著名的例子,它概括了下面的脑筋急转弯。
证明任何一方至少有 一组由三个共同的朋友组成,或者由三个共同的非朋友组成。
解决方案:称这些人为A、B、C、D、E、f。A要么有三个朋友,要么有三个非朋友。在不丧失一般性的前提下,假设B、C、D都是A的朋友。那么,如果其中任意一对是彼此的朋友,那么这一对加上A就构成一个由三个共同的朋友组成的群体。如果他们中没有两个是朋友,那么他们就是三个共同的非朋友。
事实上, 是保证这个财产的最小的团队规模。考虑下面的图表:有 顶点,每个顶点代表一个人。好友由红边连接,非好友由蓝边连接。由三个共同的朋友组成的一组用红色三角形表示,由三个共同的非朋友组成的一组用蓝色三角形表示。但这两个都没有出现在图中,所以 是不够的。
拉姆齐定理和拉姆齐数
拉姆齐理论的起源是由英国数学家弗兰克·拉姆齐提出的一个定理,它推广了上面的例子。
修复正整数 .每一个足够大的队伍将包含一组 共同的朋友或一群 共同的敌人。
用的语言重申这个定理是很方便的图论,这将更容易概括。这需要一些定义:
一个完全图 是一张关于 每个顶点对都由一条边连接。一个集团图内部是一组顶点,它们彼此成对连接;换句话说,就是一个规模庞大的小集团 的拷贝 在图。
拉姆齐定理,重申一下,固定正整数 .每一个具有足够多顶点的完整图,其每条边都是蓝色或红色的,将包含一个红色的团 顶点或蓝色的团 顶点。(这里的“红色派系”意味着连接派系中两个顶点的每条边都是红色的。顶点没有着色;边。)
的拉姆齐数量 是保证一群人的最小聚会规模吗 共同的朋友或一群 共同的敌人。或者,它是一个完整图必须拥有的顶点的最小数量,如果每条边都是蓝色或红色的,则有一个红色的团 顶点或蓝色的团 顶点。
该定理推广到任意(有限)数量的颜色;有一个拉姆齐的号码 这保证了一个单色的小团体 顶点的颜色 在一个足够大的图上。
非常。(一个顶点的团没有着色要求。)
.这是因为 ,要么所有的边都是红色的,在这种情况下有一个红色的团 顶点;或者在某个地方有一条蓝色的边,在这种情况下,它连接的两个顶点是一个蓝色的团 顶点。换句话说,要么聚会上的每个人都是其他人的朋友,要么有两个人不是朋友。
.这是对引言中的例子的重述。
拉姆齐定理的证明
目的就是要证明这一点 的存在。上的感应 .如果 或 = ,我们就完成了。对于归纳假设,我们给出了一个完整的图 顶点满足问题的条件。
为了看到这一点,从图中取一个顶点。考虑到子集 和 分别由红边和蓝边连接到这个顶点的顶点。然后 ,所以要么 或 .在前一种情况下, 包含一个蓝色的团上 顶点,在这种情况下我们就完成了,或者一个红色的团 顶点;但是把这个团和原始顶点放在一起会产生一个红色的团 顶点。后一种情况类似。证明是通过归纳法完成的。
证明给出了一个不等式 注意,这马上就显示出来了 .定理的证明实际上是证明的推广 .
拉姆齐数的边界
的计算 是一个非常困难的问题,一般来说,即使是小的 和 .的不平等 看起来有点像帕斯卡的身份事实上,用帕斯卡恒等式的一个简单归纳就可以证明这一点 确切的值 为 只因为 .目前的研究只表明了这一点 为例。
更好的上界是很难得到的,因为在缺乏一个优雅的逻辑论证的情况下,它们需要枚举所有可能的颜色 并证明每种颜色都能形成一个大小合适的单色团。下界只需要一种特定的颜色,不允许这样的小团体(例如 在介绍中给出)。