Ramsey定理 Ramsey定理的简单形式 两个简单命题 Ramsey定理 小 Ramsey数的有关结果 Ramsey数的性质 Ramsey定理的推广 Ramsey定理的一般形式 Ramsey定理 关于一般 Ramsey数的结果 Ramsey定理的应用
1 Ramsey定理 Ramsey定理的简单形式 两个简单命题 Ramsey定理 小Ramsey数的有关结果 Ramsey数的性质 Ramsey定理的推广 Ramsey定理的一般形式 Ramsey定理 关于一般Ramsey数的结果 Ramsey定理的应用
Ramsey定理的简单形式 两个简单的命题 命题1: 用红蓝两色涂色五6的边,则或有一个红色K3,或有 个蓝色K R(3,3)=6 命题2: 用红蓝两色涂色K的边,则或有一个红色K4,或 有一个蓝色K
2 两个简单的命题 命题 1： 用红蓝两色涂色 K6的边，则或有一个红色 K3, 或有 一个蓝色 K3 R(3,3)=6 命题 2： 用红蓝两色涂色 K9 的边，则或有一个红色 K4，或 有一个蓝色 K3. Ramsey定理的简单形式
命题2的证明 证:存在一个顶点关联4条蓝边或者6条红边 否则蓝边数<4,红边数<6,则蓝边总数至多 L3×9/213,红边总数至多L(5×9)2= 总共35条边,与五边数为36矛盾 设v关联4条蓝边,若对应4个顶点没有蓝边,则 构成红K;有1条蓝边,则构成兰K3
3 命题2的证明 证：存在一个顶点关联4条蓝边或者6条红边. 否则蓝边数<4, 红边数<6，则蓝边总数至多 ⎣(3×9)/2⎦=13，红边总数至多 ⎣(5×9)/2⎦=22， 总共35条边，与K9边数为36矛盾. 设v1关联4条蓝边，若对应4个顶点没有蓝边，则 构成红K4；有1条蓝边，则构成兰K3
命题2的证明 设v关联6条红边,对应6个顶点必有蓝K3或红K 对于K8,存在一种涂色方案, 既没有蓝色三角形,也没有红 色完全四边形 R(3,4)=9
4 命题2的证明 设v1关联6条红边，对应6个顶点必有蓝K3或红K3. 对于K8，存在一种涂色方案， 既没有蓝色三角形，也没有红 色完全四边形. R(3,4)=9
Ramsey定理 定理设,q为正整数,p,q≥2,则存在最小正整 数R(,q),使得当n≥R(D9)时,用红蓝两色涂 色Kn的边,则或存在一个蓝色的En,或存在 个红色的K矿 证明思路:归纳法 归纳假设R(D,2)≤,R2,q)≤, 归纳步骤R(p-1,q,R(q-1,p)存在 =R(P, sR(P-1,+R(q-1,p)
5 Ramsey定理 定理 设 p, q为正整数，p, q ≥ 2，则存在最小正整 数R(p, q)，使得当 n ≥ R(p,q) 时，用红蓝两色涂 色Kn 的边，则或存在一个蓝色的 Kp，或存在一 个红色的 Kq. 证明思路：归纳法 归纳假设 R(p, 2)≤p, R(2, q)≤q, 归纳步骤 R(p-1, q)，R(q-1, p)存在 ⇒ R(p,q) ≤ R(p-1, q) + R(q-1, p)