归纳步骤的证明 假设对正整数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数的性质