浅谈“拉姆齐理论”

                               浅谈“拉姆齐理论”

    一、网友的问题：

    上世纪初，匈牙利数学竞赛中有一道“六人相识问题”：试证，在任何六人中，总可以找到3个彼此认识或彼此不认识的人。这个问题也是网友曾经贴出的一道题。

    这个问题既有趣，又蕴涵了一个重要的，尚未完全解决的、或说在本质上还没有形成理论系统的、充满了重重未解之迷的数学领域难题。现在这个理论是归属于《图论》体系的内容。这个理论，就是著名的“拉姆齐理论”。

    弗朗克.普鲁姆泼顿.拉姆齐（1903——1930）是英国数理逻辑学家。1928年，拉姆齐在伦敦数学会上宣读了论文“论形式逻辑中的一个问题”，从中表达了这一理论概念。

    二、二色的拉姆齐问题和拉姆齐数：

    上面所列举的就是拉姆齐问题的最基础的一个问题。两色的拉姆齐问题是最简单的，已经有部分研究成果的研究领域。这个问题的一般形式是：规定在平面上有n个顶点，并且所有的顶点之间都有连线，这样的图称之为完全图，用Kn表示，一般的，n不小于6。为什么？继续了解以下介绍就知道了。在按照以下规定对所有的连线染色以后，一定会存在a个顶点之间的连线都是红色或b个顶点之间的连线都是兰色。染的方法规定是“任意的”。这就是问题的普遍性所在。（这里，a、b是任意给定的正整数）。一般在讨论时，a不小于3，b不小于3。实际上就是在研究，当n取到什么数值时，完全图Kn中必然含有相同染色的Ka、Kb这样的完全图？

    在图论中，规定了以下的表示法：
    Kn——n个顶点的完全图。
    Ka——a个顶点的包含于Kn中的子完全图。
    Kb——b个顶点的包含于Kn中的子完全图。

    满足一定出现红色 Ka或者兰色 Kb的具有最少顶点数的完全图Kn，其顶点数n记为R（a，b）。

    由于R（a，b）=R（b，a），所以，一般只讨论a小于等于b的R（a，b）的情况即可。

    寻找拉姆齐数R（a，b）在实际操作中是公认较困难的事。因此，曾经有这样一个有趣的故事：据传，匈牙利数学家爱尔特希经常挂在嘴上一句话，他说，如果有一个妖怪对人类说：“告诉我R（5，5）是多少，否则我将毁灭人类！”那么最好的办法也许是集合全世界的计算机与计算机专家全力以赴的去求解。如果妖怪要问R（6，6）是多少，那么我们别无它法，只有拼命去干掉妖怪了。这个故事告诉我们，求解R（5，5）、R（6，6）是一件多么困难的事情！关于R（a，b）的传统计算方法，由于专业性较强，这里就不再介绍了。

    也许这样倒好，不至于束缚网友们的思考，或许会产生一位数学天才，自我发现一种简洁、高效的解决办法也未可知。

    三、拉姆齐数的已知成果：
    据笔者所知，现有的已经完全确定的拉姆齐数仅有8个。

    1、R（3，3）=6
    2、R（3，4）=9
    3、R（3，5）=14
    4、R（3，6）=18
    5、R（4，4）=18
    6、R（3，7）=23
    7、R（3，8）=28
    8、R（3，9）=36。

    此外还有一些拉姆齐数的取值范围：
    1、40≤R（3，10）≤43。
    2、43≤R（5，5）≤53，
    3、102≤R（6，6）≤169。……。

    从这些现成的成果，我们可以知道，如果有9个人在一起，必然有3人认识，或4人不认识；4人认识，或三人不认识。在169人中，必然可以找到6人相互认识，或者可以找到有6人相互不认识……。

    四、进一步，更难的是多色的拉姆齐数的问题，已知现有的三色拉姆齐数（表为r3）的值只有一个：r3=17。

    第六届国际奥赛题中有一题就是求证r3=17的，现将此题展示如下：

    17个科学家，每一个都与其他科学家通信。在他们的书信往来中仅仅讨论三个题目（可理解为染三种颜色）。而每两个科学家之间仅讨论一个题目，证明，至少有三个科学家，他们讨论同一个题目。

    用图论表达就是：在完全图K17中，在任意对所有连线染上三色之一以后，必然有一个同色的K3存在。