拉姆齐数的定义

拉姆齐数，用图论的语言有两种描述：

对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；

在着色理论中是这样描述的：对于完全图Kn{\displaystyle K_{n}}的任意一个2边着色(e1,e2){\displaystyle (e_{1},e_{2})}，使得Kn[e1]{\displaystyle K_{n}[e_{1}]}中含有一个k阶子完全图，Kn[e2]{\displaystyle K_{n}[e_{2}]}含有一个l阶子完全图，则称满足这个条件的最小的n为一个拉姆齐数。（注意：Ki{\displaystyle K_{i}}按照图论的记法表示i阶完全图）

拉姆齐证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。

拉姆齐数亦可推广到多于两个数：

拉姆齐数的数值或上下界

已知的拉姆齐数非常少，保罗·艾狄胥曾以一个譬喻来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若他们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”

显然易见的公式： R(0,s)=0， R(1,s)=1， R(2,s)=s， R(l1,l2,l3,...,lr{\displaystyle l_{1},l_{2},l_{3},...,l_{r}})=R(l2,l1,l3,...,lr{\displaystyle l_{2},l_{1},l_{3},...,l_{r}})=R(l3,l1,l2,...,lr{\displaystyle l_{3},l_{1},l_{2},...,l_{r}})（将li{\displaystyle l_{i}}的顺序改变并不改变拉姆齐的数值）。

R(3,3,3)=17

更详尽的可见于[1]

R(3,3)等于6的证明

证明：在一个K6{\displaystyle K_{6}}的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。

任意选取一个端点P{\displaystyle P}，它有5条边和其他端点相连。

根据鸽巢原理，5条边的颜色至少有3条相同，不失一般性设这种颜色是红色。

在这3条边除了P{\displaystyle P}以外的3个端点，它们互相连结的边有3条。

而在K5{\displaystyle K_{5}}内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点 的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。