Ramsey Theorem 拉姆齐定理

– – 首先吐槽一下这个wiki的翻译, 看了一下是一个台湾人翻译的, 虽然语言很标准..但是读着不是很流畅.

我看Ramsey Number是看 Combinatorics Through Guided Discovery 的时候看到的. 里面第二章介绍Double Induction and Ramsey Number 说的非常详细, 而且很简洁. 这本书是免费的, 伯克利也在用, 强烈推荐.

下面介绍Ramsey Number:

Ramsey Number可以从两个方面考虑:

一个是实际问题: 请多少的客人吃饭, 能正好让他们有至少m个互相认识或者n个都不认识. 这里有几点需要注意:

1. 所求的值和条件都为至少
2. m和n是或者的关系

另一个描述是从图论出发: 一个无向完全图中,最少多少个顶点, 有m大小的Clique或者n大小Independent Set. Clique的定义是:一个顶点的集合,其中任意两点都有边. Independent Set的定义是: 一个顶点的集合, 其中任意两点都没有边.

通过定义, 我们可以很清楚的看出, Ramsey Number是对称的, 即: R(m.n) = R(n,m)

证明Ramsey Number是非常复杂的, 借用wiki上的话就是:

想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了

虽然证明一个不容易, 但是通过一个不等式,可以知道其大概的范围:

如果R(m-1,n)和R(m,n-1)不全是偶数: R(m, n) ≤ R(m-1, n) + R(m, n-1)

如果R(m-1,n)和R(m,n-1)全是偶数: R(m, n) ≤ R(m-1, n) + R(m, n-1) – 1

所以通过上面的不等式, 我们缩小范围后进行排除, 就可以解一下数字很小的Ramsey Number, 比如下面的R(4,3): http://www.cut-the-knot.org/arithmetic/combinatorics/Ramsey43.shtml

其实,无论是拉姆齐定理, 还是知名的友谊定理, 都是鸽巢定理的应用.证明的时候, 都可以用染色模型来进行推到. 上面书中的推导就是用类似的方法. 当然, 拉姆齐定理还有一本专门的书: http://www.amazon.com/exec/obidos/ASIN/0471500461/ref=nosim/weisstein-20 这价格就呵呵了.