【科普】拉姆齐定理RamseyTheory

2019-05-08 本文已影响14人 zhyuzh3d

欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】

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

拉姆齐

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。

任意取6个点中的一个点P，对于一个完整图，它应该和其他5点相连。相连有两种可能，即认识或者不认识，认识标红色，不认识标蓝色。那么5条连线中至少有3条颜色是一样的，我么假设是3条红色认识。但这时并没有形成三角形，也不满足3个点互相都认识或都不认识。

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

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

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

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

欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】

如果您发现文章错误，请不吝留言指正；
如果您觉得有用，请点喜欢；
如果您觉得很有用，欢迎转载~

END