拉姆齐二染色定理来源

Answer 1

拉姆齐二染色定理，由弗兰克·普伦普顿·拉姆齐在1930年的论文《形式逻辑上的一个问题》中提出，核心内容是关于图论中的拉姆齐数。拉姆齐数R(k,l)定义为对于任何N顶图，如果它包含k个顶点的团或l个顶点的独立集，那么具有这种性质的最小自然数N即为拉姆齐数。在着色理论中，这个定理表明在完全图Kn中，如果对每条边涂上两种颜色，至少存在一个颜色的子图是k阶完全图或另一个颜色的l阶完全图，那么满足这个条件的最小n值即为拉姆齐数。

拉姆齐证明了，对于任何给定的正整数k和l，拉姆齐数R(k,l)是唯一且有限的。比如，R(1,s)恒等于1，R(2,s)等于s，而R(l1,l2,l3,...,lr;r)的值会根据li的顺序改变而保持不变。对于更复杂的拉姆齐数，例如R(3,3)的值为6，其证明是通过构造一个K6的完全图，通过边的颜色区分，可以得出必然存在红色或蓝色的三角形，从而得证。

尽管拉姆齐数的数值或上下界在大多数情况下难以直接计算，但已知的几个值提供了一定的参考。例如，R(3,3,3)=17，证明过程展示了这个定理在实际问题中的应用，如友谊定理，即在一个完全图中，无论如何染色，总会存在一种颜色使得至少形成一个三角形。寻找更高阶的拉姆齐数是一个极具挑战性的数学问题，正如保罗·艾狄胥所比喻的外星人入侵地球的情景，R(5,5)和R(6,6)的值象征着不同的难度级别。