如果G没有大的团.pptVIP

Ramsey Theorem Ramsey定理 如果G没有大的团，是否有大的独立集？ Ramsey证明：对于任意正整数r,s, 存在一个最小整数R(r,s)使得任意具有R(r,s)个结点的图或者有一个r个结点的团或者有s个结点的独立集。 或者说：对于任意有R(r.s)个结点的完全图，用红、蓝两种颜色给边着色，必然存在一个红色的Kr或者一个蓝色的Ks 例如，R(1,s)=R(r,1)=1, R(2,s)=s, R(r,2)=r R(3,3) = 6 Ramsey数 Ramsey定理证明 对于r+s使用归纳法。 只需证明 [定理]对于任意正整数r?2,s?2, R(r,s)?R(r-1,s)+R(r,s-1). 如果R(r-1,s)和R(r,s-1)均是偶数，则不等号成立。 [证明] 设G是一个具有R(r,s-1)+R(r-1,s)个结点的图, v是一个结点. 将其他结点分为两组：S(与v不相邻的结点 )和T(与v相邻的结点)。 则有 R(r,s-1)+R(r-1,s) = |S|+|T|+1 根据抽屉原则, |S|?R(r,s-1) 或者 |T|?R(r-1,s), 即分两种情况 (1) v至少与R(r,s-1)个结点的集合S不邻接,或者 (2) v至少与R(r-1,s)个结点的集合T邻接; 否则, G的结点数R(r,s-1)+R(r-1,s). 对于(1), G[S]或者存在一个r个结点的团,或者存在一个s-1个结点的独立集, 故G[S+{v}]或者存在一个r个结点的团,或者存在一个s个结点的独立集, 定理成立. 对于(2), G[T]或者存在一个r-1个结点的团,或者存在一个s个结点的独立集, 故G[T+{v}]或者存在一个r个结点的团,或者存在一个s个结点的独立集, 定理成立. 当R(r,s-1)和R(r-1,s)均为偶数时, 一个具有R(r,s-1)+R(r-1,s)-1(奇数)个结点的图必有一个偶数度结点v. 以上两种情况仍然成立, 因为v不可能正好与R(r-1,s)-1个结点相邻. 故有R(r,s)=R(r,s-1)+R(r-1,s)-1. 例如， R(3,3)?R(2,3)+R(3,2)=6 R(3,3)5 Ramsey定理推广 R(3,3,3) = 17， 在17个（以上）的完全图中，用三种颜色给所有的边着色，则必存在同色的K3 可以推广到任意中颜色的情况：R(r1,r2,…,rk). * 25 18 36 28 23 18 14 9 6 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 s: 1 2 3 4 5 6 7 8 9 r 1 2 3 4 Current known Ramsey numbers R(3,3)5 R(3,4)R(2,4)+R(3,3)=10, R(3,4)8 R(3,4)8 (r,s）Ramsey图：具有R(r,s)-1个结点，不存在r-图，不存在s独立集