– – 首先吐槽一下这个wiki的翻译, 看了一下是一个台湾人翻译的, 虽然语言很标准..但是读着不是很流畅. 我看Ramsey Number是看 Combinatorics Through Guided Discovery 的时候看到的. 里面第二章介绍Double Induction and Ramsey Number 说的非常详细, 而且很简洁. 这本书是免费的, 伯克利也在用, 强烈推荐. 下面介绍Ramsey Number: Ramsey Number可以从两个方面考虑: 一个是实际问题: 请多少的客人吃饭, 能正好让他们有至少m个互相认识或者n个都不认识. 这里有几点需要注意: 所求的值和条件都为至少 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, […]