- - 首先吐槽一下这个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(nm) 证明Ramsey Number是非常复杂的 借用wiki上的话就是: 想像有队外星人军队在地球降落,要求取得R(55)的值,否则便会毁灭地球.在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值.若它们要求的是R(66)的值,我们要尝试毁灭这班外星人了 虽然证明一个不容易 但是通过一个不等式可以知道其大概的范围: 如果R(m-1n)和R(mn-1)不全是偶数: R(m [...]