拉姆齐理论

拉姆齐理论对以下类型问题的研究是否给出了a组合结构(例如图或者整数的子集)，多大的结构必须保证具有给定属性的某些子结构(例如子图，子集)的存在?该理论在通信网络设计和其他纯图理论环境中有应用，也适用于基础知识中有趣的问题数论．

拉姆齐理论最著名的例子是拉姆齐定理，它概括了下面的难题。

表明任何一方至少有 $6$人们可以分为三个共同的朋友或三个共同的非朋友。

---

解决方案:称这些人为A、B、C、D、E、f。A要么有三个朋友，要么有三个非朋友。在不失一般性的前提下，假设B、C、D都是A的朋友，那么如果他们中的任何一对是彼此的朋友，那么这对加上A就组成了三个共同的朋友。如果他们中没有两个人是朋友，那么他们就是三个共同的非朋友。 $\广场$

事实上, $N = 6$是保证这个财产的最小人数。请看下面的图表:有 $5$顶点，每个顶点代表一个人。朋友用红色边连接，非朋友用蓝色边连接。一个由三个共同的朋友组成的小组用红色三角形表示，一个由三个共同的非朋友组成的小组用蓝色三角形表示。但这两个在图中都不存在，所以 $N = 5$是不够的。

拉姆齐理论的起源是由英国数学家弗兰克·拉姆齐提出的一个定理，它概括了上面的例子。

固定正整数 $m, n$．每一个足够大的队伍将包含一组 $米$共同的朋友或一群 $n$共同的敌人。

用的语言重申这个定理是很方便的图论，这样更容易概括。这需要一些定义:

一个完全图 $K_n$是关于 $n$顶点，其中每对顶点由一条边连接。

一个集团在图的内部是一组相互成对连接的顶点;换句话说，就是一个小集团 $n$在图中是一个副本 $K_n$在图里面。

拉姆齐定理，重申一下，就是固定正整数 $m, n$．每个有足够多顶点的完整图，每条边都是蓝色或红色的，将包含一个红色的团 $米$顶点还是一个蓝色的团 $n$顶点。(这里的“红色派系”意味着在派系中连接两个顶点的每条边都是红色的。顶点是没有颜色的;边缘是。)

的拉姆齐数量 $R (m, n)$保证一组的最小派对规模 $米$共同的朋友或一群 $n$共同的敌人。或者，它是一个完整图必须具有的最小顶点数，如果每条边都是蓝色或红色，则有一个红色的团 $米$顶点还是一个蓝色的团 $n$顶点。

该定理推广到任意(有限)数量的颜色;有一个拉姆齐数字 $R (n_1、甲烷、\ ldots n_k)$这保证了一个单一的派系 $n_k$带颜色的顶点 $k$在一个足够大的图上。

$R(m,1) = R(1,m) = 1$非常。(有一个顶点的团没有着色要求。)

$R(m,2) = R(2,m) = m$．这是因为 $K_m$，要么所有的边都是红色的，在这种情况下，就有一个红色的团 $米$顶点;或者在某个地方有一条蓝色边，在这种情况下，它连接的两个顶点是一个蓝色的团 $2$顶点。换句话说，要么派对上的所有人都是朋友，要么有两个人不是朋友。

$R(3,3) = 6$．这是对引言中例子的重述。

我们的目标就是要证明这一点 $R (m, n)$的存在。上的感应 $m + n$．如果 $米$或 $n$= $1$，我们完成了。对于归纳假设，我们证明了一个完整的图 $R(m-1,n) + R(m,n-1)$顶点满足问题的条件。
为了看到这一点，从图中取一个顶点。考虑子集 $V_r$而且 $V_b$分别由红边和蓝边连接到这个顶点的顶点。然后 $|V_r| + |V_b| = R(m-1,n)+R(m,n-1)-1$，所以 $|V_r| \ge R(m-1,n)$或 $|V_b| \ge R(m,n-1)$．在前一种情况下， $V_r$包含一个蓝色的团上 $n$顶点，在这种情况下我们完成了，或者一个红色的团 $m - 1$顶点;但是把这个团和原来的顶点放在一起会产生一个红色的团 $米$顶点。后一种情况类似。用归纳法证明是完整的。 $\广场$

证明给出了一个不等式 $R(m,n) \le R(m-1,n) + R(m,n-1)。$注意，这立即显示出来 $R(3,3) \le R(3,2) + R(2,3) = 3+3 = 6$．这个定理的证明实际上是对那个证明的推广 $R(3,3) = 6$．

的计算 $R (m, n)$是一个非常困难的问题在一般情况下，即使小 $米$而且 $n$．的不平等 $R (m, n)$看起来有点像帕斯卡的身份事实上，用帕斯卡恒等的简单归纳就能证明这一点 $R(m,n) \le \binom{m+n-2}{m-1}。$的确切值 $R (m, n)$为 $3 \le m \le n$只以 $(m,n) = (3,3)，(3,4)，\ldots，(3,9)，(4,4)，(4,5)$．目前的研究只表明了这一点 $43 \le R(5,5) \le 49$例如。

更好的上界是很难得到的，因为在没有一个优雅的逻辑论证的情况下，它们需要枚举的所有可能的颜色 $K_n$并证明每种颜色都有一个大小合适的单色团。下界只需要一种特定的颜色，不允许这样的派系(例如 $R(3,3) \ge 6$在介绍中给出)。