在《鸽子展开的组合原理》中，留下了拉姆齐数的问题，这个问题是离散数学中著名的难题。

拉姆齐数最早的证明应用于6个聚会上的人必有3人相互认识或3人素不相识而被广泛应用于人脉关系，并由此分析出一个普遍的规律：世界上任意的6个或以上的人，都有与上面类似的结论。其被表示为R(3,3)=6。

聚会上人的认识问题是其最初的应用

后来拉姆齐数被抽象到图论，R(x,y)=n被用来描述用2种不同的颜色对一个Kn完全图染色，求其中必然存在完全为一种颜色的Kx完全图或完全为另一种颜色的Ky完全图的最小的n值。下面将对此问题进行基于抽象的分析。

类似的思想在《开拓最短的航线》中提及过，可以看作是航线图的一个推广

某种与人类共生的智慧生物在地球上开辟了若干个聚落，为了方便它们不同聚落之间的通讯，它们发射了两组不互通的通讯卫星（标记为α组和β组卫星）。规定，只要有3个聚落能连接α组或β组通讯卫星，即为α组网或β组网。证明，当聚落数量大于6个时，必然能组网。而聚落数量少于6个时，可能出现α组和β组都不能组网的情况。并定义与α组卫星组网的为图上的红色边，与β组卫星组网的为图上的蓝色边。以下是证明过程。

假设智慧生物聚落之间的信息交换依靠类似4G形式的网络进行

当聚落个数为5个时，如果聚落之间通讯频率如下：（α组卫星通讯频率为2310MHz，β组卫星通讯频率为2345MHz，下同）

R(3,3)>5的证明图

那么没有任意3个聚落之间能以相同频率通讯，都无法组网。

当聚落数量为6个时，根据鸽巢原理，任意一个聚落必和其他至少3个聚落以相同频率通讯，假如聚落1与聚落2、3、4以2310MHz通讯，若2与3、2和4、3和4都以2345MHz通讯，则组成3个聚落之间β组网的情况。若这三组中的一组以2310MHz通讯，则组成3个聚落之间α组网的情况。对于其他聚落或频率调换，有同样的结果。因此总能有一方能够组网。

R(3,3)=6的证明图

以下对问题进行推广。定义n-α组网或n-β组网为有n个聚落能连接α组卫星或β组卫星。

聚落个数不少于9个时，对于任意一个聚落，其至少和4个其他聚落能以某一种频率通讯，若这4个聚落以另一种频率通讯，则形成4-β组网或4-α组网，若其中2个聚落能以前述相同频率通讯，则形成3-α组网或3-β组网的情形。

而由于当聚落个数为8时，若其通讯频率为下表：

R(3,4)>8的证明图

则没有任意的一组卫星3-组网或另一组卫星4-组网，证明了R(3,4)>8，也证明了R(3,4)=9。

R(3,4)=9的证明图

而在以此为背景证明R(4,4)=18之前，需要引出下面四个定理：

1、R(x,y)=R(y,x)

2、R(2,x)=R(x,2)=x

3、R(1,x)=R(x,1)=1

4、R(x,y)<=R(x-1,y)+R(x,y-1)

前三个证明都很简单。K1完全图就是图上的点自身，因此只要图的阶数大于1，必然有一种颜色的K1完全图或另一种颜色的Kx完全图。K2完全图是图上的一条边，因此对于一个x阶完全图，必然有一种颜色的K2完全图或整个图都是一种颜色的Kx完全图。由于颜色可以互换，因此R(x,y)=R(y,x)。

第4个证明是因为对于n阶完全图上的任意一个点，其连接其他n-1个点的边是红色的条数x和蓝色的条数y分别对应有Kx完全图或K(y-1)完全图的情况或K(x-1)完全图或Ky完全图的情况。因此有x+y+1=R(x,y-1)+R(x-1,y)。

但如果x<R(x-1,y)即y>=R(x,y-1)，可以推出被蓝色连接的点组成的完全图有x阶或n-1阶完全子图。由此推出由这些点和开始的点组成的完全图中必有蓝色的y阶完全子图。反之亦然。由此证明R(x,y)<=R(x,y-1)+R(x-1,y)。

在以上的几个定理之后，可以通过递推+证明的方式证明R(4,4)=18。

由上一部分的第4个定理可得R(4,4)<=R(3,4)+R(4,3)=18，因此只需证明R(4,4)>17，即K17完全图里面可能没有一种颜色的K4完全图或另一种颜色的K4完全图。

R(4,4)>17的证明图

于是可以令聚落的序号为0至16，求它们的平方除以17的余数。然后，若两个聚落的序号之差为所有平方数除以17可能的余数（包括0、1、2、4、8、9、13、15、16），则边的颜色为红色，否则为蓝色。

在此对与0号聚落相邻的边作分析，对于0号聚落与a,b,c号聚落相连的边，若要形成同色的K4完全图，需要确保a,b,c,a-b,a-c,b-c的绝对值都是或都不是所有平方数除以17可能的余数。但已经经过证明，不存在这样的a,b,c使得这个命题成立，则K17完全图内不存在同色的K4完全图，因此R(4,4)>17，进而R(4,4)=18。

R(4,4)=18的证明图

目前已知的拉姆齐数有9个，其他都只能给出一个上限值和下限值。其到目前还没有一个稳定的解法。

拉姆齐数需要对每条边的染色进行计算，因此其时间复杂度高达O(2^(n^2))，这也是其成为离散数学难题的原因。目前已经有多种关于拉姆齐数的算法，但没有能改变其NP难问题的性质。即使小如R(5,5)、R(3,10)等拉姆齐数直到2021年还只有上限值和下限值。

运动场上的朋友与对手关系也是这样复杂，即使对于很少的人

由拉姆齐数的性质可以再次看到有序性寓于无序性之中，无序性现于有序性之中的道理。在其证明中可以看到，即使是K18完全图这种已经很复杂的图内部，依然有小规模的规律性。由此可以推广到关系的构建上，即使是无比错综复杂的关系网络，也有其内部井井有条的一面。

有序和无序的统一，也在于这座城市，再纷繁复杂的外表都有井井有条的内里

参考资料

https://www.whitman.edu/Documents/Academics/Mathematics/2016/Barton.pdf

https://www.zhihu.com/question/263833856/answer/273575673

《离散数学及其应用》Kenneth H. Rosen著，徐六通、杨娟、吴斌译，机械工业出版社