晚宴上的客人与拉姆赛定理.doc

晚宴上的客人与拉姆赛定理
　　英国数学家弗朗克·拉姆赛证明了这样一条定理：对于充分大的元素集合（人、数或几何点），每一个它的成员的配对，比如，有联系的或者无联系的，总是原来的集合的一个有一种特殊性质的较大的子集。或者子集的所有成员将互相有联系，或者它的所有成员互相无联系。在较大的无序集合中，这一子集是有序的不可避免的小岛（在群岛中有许多有意义的小岛）；这就是说，垃圾足够多的话，免费午餐就能保证存在。
问题可以用晚宴上的客人来重新叙述。对于大小为3的有序小岛的拉姆赛问题是：
为使出席的客人中至少有3人互相认识或者至少有3人互相陌生，应该邀请的最少客人数是多少？（假定如果玛萨认识乔治，那么乔治也认识玛萨。）答案是6，这可以通过设想你是宴会上的一个客人来看到这点。由于你认识或不认识其他5位的每一位，你将或者至少认识他们中的3位，或者至少不认识他们中的3位。为什么？假设你认识其中的3个（如果你至少不认识3个，论证是一样的），并且考虑你的3个熟人之间是什么关系。如果任何2位互相认识，那么这2人与你就组成一个互相认识的3位宾客小组。另一方面，如果你的3位熟人互相都不认识，那么他们3人就构成互相不认识的3人小组。这样，6位客人就已足够。为看到5位客人不够，设想你在一个很小的宴会上，其中你刚好认识其他4位中的2位，而他们2位中的每一位又都只认识你所不认识的2位中的1位，并且2人认识的又不同。
对于大小为4的小岛，客人数必须为18，而对于5，则是在43到55之间。对于更大的数，分析就要复杂得多，拉姆赛类型的问题的答案仅对于很少的数是已知的。
自从1930年拉姆赛去世以来，已发展成整个小作坊来从事证明同样的一般形式的问题：
总存在某个具有规律性模式的给定大小的子集（即某种阶的小岛）的集合有多大？多产而周游世界的数学家保尔·爱尔多希发现许多这样的岛，其中有些非常优美。特殊的岛的细节是复杂的，但是一般来说，关于集合的必要大小的问题答案通常会落入狄阿可尼斯的格言：如果它足够大，几乎所有垃圾都会发生。