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)
归纳步骤的证明 假设对正整数pq,p乎,q≤,p+qpq为真, 则R(P1,q),RQ,g-1)存在令 n≥R(p-1,q)+R(D,-1) 用蓝红两色涂色Kn的边,则 case 1n关联R(p-1,.条蓝边, case V1 关联R(q-1)条红边 对于 casel,如为蓝色Kn1,构成蓝色Kn;如为 红色K,则满足要求对于cae2可以类似分析 R(p, sR(P-1, 0)+r(g-lp)
6 归纳步骤的证明 假设对正整数 p’, q’, p ’ ≤p, q ’ ≤ q, p’+ q’<p + q 为真， 则 R (p-1, q), R (p , q-1) 存在. 令 n ≥ R (p-1, q) + R (p , q-1)， 用蓝红两色涂色 Kn的边，则 case1 v 1关联 R (p-1, q )条蓝边， case2 v 1关联 R (p , q-1)条红边 . 对于case1，如为蓝色 Kp-1 ,构成蓝色 Kp；如为 红色 Kq，则满足要求. 对于case2可以类似分析 . R (p,q) ≤ R (p-1, q) + R ( q-1,p )
小 Ramsey数的值 (from Mathworld) 3456789101112131415 3691418232836404652596673 43|5159697888 4 1825354956698096128133141153 416184115149191238|291349417 43588095121141153181193221242 4987143216316442 102111127153177253262278292374 1652984957801171 20521677 322|416511 540103117132826 2828316 635 703 187035836090 565580 658812677 798 23556
7 q p 3 4 5 6 7 8 9 10 11 12 13 14 15 3 6 9 14 18 23 28 36 40 43 46 51 52 59 59 69 66 78 73 88 4 18 25 35 41 49 61 56 84 69 115 80 149 96 191 128 238 133 291 141 349 153 417 5 43 49 58 87 80 143 95 216 121 316 141 442 153 181 193 221 242 6 102 165 111 298 127 495 153 780 177 1171 253 262 278 292 374 7 205 540 216 1031 7 1713 7 2826 322 416 511 8 282 1870 8 3583 316 6090 635 703 9 565 6588 580 12677 10 798 23556 小Ramsey数的值 （from Mathworld）
Ramsey数的性质 (1)R(a1b)=R(b,a),R(a,2)=R(2, (2)R(b)≤R(a-1,b)+R(nb-1) 性质(2)给出上界 9=R(3,4)≤R(2,4)+R(3,3)=4+6=10 18=R(4,4)≤R(3,4)+R(4,3)=9+9=18 25=R(4,5)≤R3,5)+R(4,4)=14+18=32 R(3,10)≤R2,10)+R(3,9)=10+36=46 R(3,10)≤43
8 (1) R(a,b)=R(b,a), R(a,2) = R(2,a)=a (2) R(a,b) ≤ R(a-1,b) + R(a,b-1) 性质 (2) 给出上界 9 = R(3,4) ≤ R(2,4) + R(3,3) = 4 + 6 = 10 18 = R(4,4) ≤ R(3,4) + R(4,3) = 9 + 9 = 18 25 = R(4,5) ≤ R(3,5) + R(4,4) = 14 + 18 = 32 R(3,10) ≤ R(2,10) + R(3,9) = 10 + 36 = 46 R(3,10) ≤ 43 Ramsey数的性质
Ramsey定理的推广 (1)R(,q的图表示R(的集合表述: Kn的顶点集V 集合S Kn的边集E S的2元子集的集合T 用2色涂色Kn的边将T划分成E,E2 存在蓝色完全p边形存在S的p子集其所有2元子集∈E1 存在红色完全q边形存在S的q子集其所有2元子集∈E2 集合表述具有更强的表达能力 (2)将2元子集推广到r元子集 (3)将T划分成E,E2,…,Ek
9 (1) R(p,q)的图表示 R(p,q)的集合表述： Kn的顶点集 V 集合 S Kn的边集 E S 的 2 元子集的集合 T 用 2 色涂色 Kn的边 将 T 划分成 E1,E2 存在蓝色完全 p 边形 存在 S 的 p 子集其所有 2 元子集∈E1 存在红色完全 q 边形 存在 S 的 q 子集其所有 2 元子集∈E2 集合表述具有更强的表达能力. (2) 将 2 元子集推广到 r 元子集 (3) 将 T 划分成 E1, E2, … , Ek Ramsey定理的推广
推广的 Ramsy定理 定理2 对于任意给定的正整数pr,(￠≥)存在一个最 小的正整数R(q;)使得当集合S的元素数大于 等于R(pq;r)时,将S的r子集族任意划分成 E,E2,则或者S有p子集A,A的所有r元子集 属于E或者存在子集B,B的所有r元子集属 于E2
10 推广的Ramsy定理 定理2 对于任意给定的正整数 p,q,r, (p,q≥r) 存在一个最 小的正整数 R(p,q;r)使得当集合 S 的元素数大于 等于R(p,q;r) 时，将 S 的 r 子集族任意划分成 E1, E2，则或者 S 有 p子集A，A 的所有 r 元子集 属于E1, 或者存在q子集 B，B 的所有 r 元子集属 于E2