西安电子科技大学：《图论》课程教学课件（研讨课PPT）第八讲 Ramsey理论

Ramsey理论

Ramsey 理论

Ramsey定理1(1930)：给定正整数k和L,总存在一个最小正整数r(k,), 使得每个有(k,)个顶点的图，或者包含一个有k个点的团，或者包含一个有 (个点的独立集。 易见，r(1,)=r(k,1)=1r(2,)=((k,2)=2。 r(k,)称为 Ramsey数： 最小的正整数N,使得对完全图Kx的边任意红蓝二着色，总存在一个红色的 K或者存在一个蓝色的K

Ramsey 定理 1 (1930)： 给定正整数k和 ，总存在一个最小正整数r k( , )， 使得每个有r k( , )个顶点的图，或者包含一个有k个点的团，或者包含一个有 个点的独立集。 易见，r r k r r k (1, ) ( ,1) 1; (2, ) , ( ,2) 2 = = = = 。 r k( , )称为 Ramsey 数： 最小的正整数 N，使得对完全图KN 的边任意红蓝二着色，总存在一个红色的 Kk或者存在一个蓝色的K

定理r(3,3)≤6。 定理对任意的整数k和L,有(k,)≤(k,(-1)+(k-1,)。 并且若r(k,(-1)和（飞-1，）都是偶数，则上式中不等式是严格的。 Values known bounding ranges for Ramsey numbers R(r,s)(sequence A212954 in the OEIS) 2 3 6 9 10 1 1 1 2 1 1 1 2 3 6 7 9 10 6 9 14 18 23 28 36 40-42 4 18 25f101 36-41 49-61 5914184 73-115 92-149 43-48 58-87 80-143 101-216 133-316 149[149-442 6 102-165 115141-298134[141-495 183-780 204-1171 205-540 217-1031 252-1713 292-2826 282-1870 329-3583 343-6090 9 565-6588 581-12677 10 798-23556

定理 r(3,3) 6  。 定理 对任意的整数k和 ，有r k r k r k ( , ) ( , 1) ( 1, )  − + − 。 并且若r k( , 1) − 和r k( 1, ) − 都是偶数，则上式中不等式是严格的

(k,C)Ramsey图：是指r(k,)-1阶的图G,既不包含k个点的团， 也不包含个点的独立集。 r(3,3)≥6， r(3,4)≥9， r(3,5)≥14， a】 (b r(4,4)≥18。 r(3,3)=6, 13 r(3,4)≤r(2,4)+r(3,3)-1=9,o r(3,5)=14(为什么？) r(4,4)=18(为什么？) 9 (c) (d) 图7.2(a)(3,3)Rarnsey:b)(3,4)Ramsey图： (c)(3,5)Ramsey图；(d)(4,4)Ramsey图

( , ) k Ramsey 图：是指r k( , ) 1− 阶的图 G，既不包含k个点的团， 也不包含 个点的独立集。 r(3,3) 6  ， r(3,4) 9  ， r(3,5) 14  ， r(4,4) 18  。 r(3,3) 6 = ， r r r (3,4) (2,4) (3,3) 1 9  + − = ， r(3,5) 14 = （为什么？) r(4,4) 18 = （为什么？)

(3,5)Ramsey图是13个点图，即模13的域上的图，两个点有边 当且仅当它们的差是立方剩余（1,5,8,12)，其中 1=1(mod13),5=73(mod13), 8=23(mod13),12=43(mod13)

(3,5)Ramsey 图是 13 个点图，即模 13 的域上的图，两个点有边 当且仅当它们的差是立方剩余（1,5,8,12），其中 3 3 3 3 1 1 (mod13),5 7 (mod13), 8 2 (mod13),12 4 (mod13) = = = =

(4,4)Ramsey图是17个点图，即模17的域上的图，两个点有边 当且仅当它们的差是平方剩余(1,2,4,8,9,13,15,16)，其中 1=1(m0d17),2=62(mod17), 4=152(mod17),8=52(mod17), 9=142(mod17),13=82(mod17), 15=7(mod17),16=42(mod17) 猜测（化，）Ramsey图是自补图

(4,4)Ramsey 图是 17 个点图，即模 17 的域上的图，两个点有边 当且仅当它们的差是平方剩余（1,2,4,8,9,13,15,16），其中 2 2 2 2 2 2 2 2 1 1 (mod17),2 6 (mod17), 4 15 (mod17),8 5 (mod17), 9 14 (mod17),13 8 (mod17), 15 7 (mod17),16 4 (mod17). = = = = = = = = 猜测(k,k)Ramsey 图是自补图

定理对任应的整数和，有行女》 证明要点： (1)对k+归纳证明； (2)利用公式 a-aa）

定理 对任意的整数k和 ，有 2 ( , ) 1 k r k k   + −      − 。 证明要点： （1）对k + 归纳证明； （2）利用公式 1 1 1 n n n m m m       − − = +             −

定理 (Erdos1947)k,k)>k 证明：对K边随机的独立的进行红蓝二着色，每条边着红色 或者蓝色的概率都是=12，N待定。设S是k个点的集合， A表示S是单色k团的事件，则 pm4-2 UA、表示全体取遍k-元集的这样的事件，因此 prtU4s1s pri]

定理 (Erdos 1947) / 2 ( , ) 2 2 k k r k k e  。 证明：对KN 边随机的独立的进行红蓝二着色，每条边着红色 或者蓝色的概率都是 p=1/2，N 待定。设 S 是 k 个点的集合， AS 表示 S 是单色 k 团的事件，则 ( ) ( ) 2 1 1 2 [ ] 2 2 2 k k S pr A −   = =     ， AS表示全体取遍 k-元集的这样的事件，因此 ( ) 1 2 [ ] [ ] 2 k S S N pr A pr A k   −  =     

如果prUA]N。 因此，寻找满足pr[UA]<1最大的N。 由 ev2） √2πk k22 所以如果取N= 则pr[UA]<1。证毕。 注：Stirling公式 k=V2πk e2k+0),0<0<1. 1+o(11Y22i≤R,≤g6%/sg4

如果 pr A [ ] 1 S  ，则说明出现单色 k 团的概率小于 1， 因此存在一种着色，使得不含单色 k 团。所以r k k N ( , )  。 因此，寻找满足pr A [ ] 1 S  最大的 N。 由 ( ) ( ) 1 1 2 2 / 2 2 2 2 2 ! 2 2 k k k k k N N e N k k k k   − −             。 所以如果取 / 2 2 2 k k N e   =    ，则pr A [ ] 1 S  。证毕。 注：Stirling 公式 1/(12 ) ! 2 ,0 1. k k k k k e e      + =      

Ramsey定理2(1930)：给定两个图F和H,总存在一个最小正整数r(F,H), 使得对于每个有r(F,H)个顶点的完全图的任意红蓝二着色，总存在一个红色 的F或者存在一个蓝色的H。 定理r(K,K4)≥9 b) 图12.5既不含红K,也不含蓝K,的K,红-蓝着色

Ramsey 定理 2 (1930)：给定两个图F 和H ，总存在一个最小正整数r F H ( , )， 使得对于每个有r F H ( , )个顶点的完全图的任意红蓝二着色，总存在一个红色 的F或者存在一个蓝色的H 。 定理 3 4 r K K ( , ) 9 