科普拉姆齐定理RamseyTheory-1

拉姆齐定理揭示了无序中必然出现有序的辩证统一。

Frank P. Ramsey弗兰克·拉姆齐，1903~1930，英国哲学家、数学家和经济学家。

是的，你没看错，拉姆齐生年仅到26岁便英年早逝。

拉姆齐在数学和逻辑方面的一个重要贡献就是1928年他提出的一个组合数学理论，即后来以他的名字命名的拉姆齐定理（拉姆齐理论）。

这是一个组合数学中的问题，拉姆齐定理，也称之为拉姆齐二染色定理。它的直观描述是：

在超过6人的群体中，必然有3个人互相都认识或者有3个人互相都不认识。

换个说法：

在平面上超过6个点组成的群体中，必然有3个点互相连接成为三角形或者3个点互不相连。

再换个说法：

在一个完整的6阶图中，即6个点且每个点都和其他所有点进行连线，如果连线有红蓝两种，那么必然有一个红色三角形或者蓝色三角形。

或者说：

使得n个人中至少有k个人互相认识或u个人互相不认识，即R(k,u)=n。如果k=3，u=3，那么n最小值是6。

如图咋知道R(3,3)=6,R(4,4)=18...

友谊定理是指：在一群人数不少于三的人群中，若任意两人都刚好只有一个***同认识的人，这群人中总有一人是所有人都认识的。

在图论的角度来说，一幅图，若每个顶点都跟另一个顶点刚好只有一个***同相邻的顶点，这幅图中有一个顶点和其他顶点都相邻。

如图，友谊定理的图表示也称为友谊图，或者风车图，或n-fan图，最左侧的蝴蝶结装造型也称为蝴蝶图。

拉姆齐定理还有几个推论，例如：范德瓦尔登定理、Hales-Jewett定理、舒尔定理、Rado定理等。

END