Ramsey定理

有六个人在一起，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都彼此不认识。

抽象的表示式为：

         K₆→K₃,K₃ （读为K₆箭指K₃,K₃）

一般对于这些有许多的元素，元素之间又互相依赖，互相联系的，用几何来表示能帮助我们理解问题的本质。K₁表示一个点，K₂表示一条线，即两个点相连；K₃表示一个三角形，即三个点相连。即说明K_n就表示有n个顶点，并且每两个顶点都互相连接。

上面的K₆,则C (2,6)=15,有15杀线段。把上图的第五个图形即六边形的每一条边都涂上蓝色或红色，哪条边选择哪种颜色都可以。结果你会发现无论你怎么样去选择颜色，都会找到一个三角形（即三条首尾相连的线段）具有同一种颜色，即这个三角形的三条边要不全是红色，要不全是蓝色。红色可以代表线段的两个端点是认识的，蓝色可以代表不认识的。所以上面的表达式可以简述为：总会找个一个单色的三角形。很显然上面的五边形不具有这样的性质。

由特推出一般，所以更一般的表达式为：

                   K_p→K_m,K_n；

即给定m和n，存在一个正整数P,使得如果K_p被涂成红色或蓝色，那么或者有一个红色的K_m，或者有一个蓝色的K_n.无论K_p的边如何着色，红色K_m或者蓝色的K_n的存在性是保证的。

Ramsey数r(m,n)是使得K_p→K_m,k_n成立的最小整数p. Ramsey定理断言数r(m, n)的存在性。

Ramesy定理可以推广到任意多种颜色。

什么是平凡的Ramsey数：如果r(m,n)中，n=2，且r(m,2)=m,那么符合这些条件的r就是平凡的Ramsey数；其它的就是非平凡的Ramsey数。关于如何确定r的值现在是没有什么好的办法的，只能通过一个个去试。