離散數(shù)學(xué)代數(shù)系統(tǒng)chapter

Ramsey定理Ramsey定理的簡(jiǎn)單形式 兩個(gè)簡(jiǎn)單命題

Ramsey定理小Ramsey數(shù)的有關(guān)結(jié)果

Ramsey數(shù)的性質(zhì)

Ramsey定理的推廣Ramsey定理的一般形式

Ramsey定理關(guān)于一般Ramsey數(shù)的結(jié)果Ramsey定理的應(yīng)用兩個(gè)簡(jiǎn)單的命題命題1：用紅藍(lán)兩色涂色

K6

的邊，則或有一個(gè)紅色

K3,

或有一個(gè)藍(lán)色

K3R(3,3)=6命題2：用紅藍(lán)兩色涂色K9

的邊，則或有一個(gè)紅色K4，或有一個(gè)藍(lán)色K3.Ramsey定理的簡(jiǎn)單形式命題2的證明定理

設(shè)

p,q

為正整數(shù)，p,q?2，則存在最小正整數(shù)

R(p,q)，

使得當(dāng)

n?R(p,q)時(shí)，用紅藍(lán)兩色涂色

Kn

的邊，則或存在一個(gè)藍(lán)色的

Kp，或存在一個(gè)紅色的

Kq.證明：R(p,2)￡p,R(2,q)￡q,假設(shè)對(duì)正整數(shù)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)，用藍(lán)紅兩色涂色Kn

的邊，則case1case2v1

關(guān)聯(lián)R(p-1,q)條藍(lán)邊，

v1

關(guān)聯(lián)R(p,q-1)條紅邊.對(duì)于case1，如為藍(lán)色Kp-1,構(gòu)成藍(lán)色Kp；如為紅色Kq，則滿足要求.對(duì)于case2

可以類似分析.R(p,q)￡R(p-1,q)+R(q-1,p)Ramsey定理qp34567891011121314153691418232836404346515259596966787388418253541496156846911580149961911282381332911413491534175434958878014395216121316442153181193221242610216511129812749515378017711712532622782923747205540216103117132826322416511828218703583316609063570395656588580126771079823556小Ramsey數(shù)的值（from

Mathworld）R(a,b)=R(b,a), R(a,2)

=

R(2,a)=aR(a,b)

￡

R(a-1,b)

+

R(a,b-1)性質(zhì)(2)給出上界9

=

R(3,4)

￡

R(2,4)

+

R(3,3)

=

4

+

6

=

1018

=

R(4,4)

￡

R(3,4)

+

R(4,3)

=

9

+

9

=

1825

=

R(4,5)

￡

R(3,5)

+

R(4,4)

=

14

+

18

=

32R(3,10)

=

R(2,10)

+

R(3,9)

=

10

+

36=

46R(3,10)

￡

43Ramsey數(shù)的性質(zhì)(1)

R(p,q)的集合表述：

Kn

的頂點(diǎn)集VKn

的邊集E用2

色涂色Kn

的邊存在藍(lán)色完全p

邊形存在紅色完全q

邊形集合SS

的2

元子集的集合T將T

劃分成E1,E2存在S

的p

子集，其所有2

元子集?

E1存在S

的q

子集，其所有2

元子集?

E2集合表述具有更強(qiáng)的表達(dá)能力.將2

元子集推廣到r

元子集將T

劃分成E1,E2,…,Ek簡(jiǎn)單Ramsey定理的推廣定理2.對(duì)于任意給定的正整數(shù)p,q,r,(p,q?r)存在一個(gè)最小的正整數(shù)R(p,q;r)使得當(dāng)集合S

的元素?cái)?shù)大于等于R(p,q;r)時(shí)將S

的r

子集族任意劃分成E1,E2，則或者S

有p

子集A，A

的所有r

元子集屬于E1,或者存在q

子集B，B的所有r

元子集屬于E2.定理3

設(shè)r,k?1,qi?r,i=1,2,…,k,是給定正整數(shù)，則存在一個(gè)最小的正整數(shù)R(q1,q2,…,qk;r)，使得當(dāng)n?R(q1,q2,…,qk;r)時(shí)，當(dāng)

n

元集S

的所有r

元子集劃分成k

個(gè)子集族T1,T2,…,Tk，那么存在S

的q1

元子集A1,其所有的r

元子集屬于T1,或者存在S的q2

元子集A2，A2

的所有r

元子集屬于T2,…,或者存在S

的qk

元子集Ak,其所有的r

元子集屬于Tk.Ramsy定理的一般情況證明R(p,q;r)存在：多重歸納法證明歸納基礎(chǔ)R(p,r;r)=p，R(r,q;r)=q，R(p,q;1)=p+q-1.歸納步驟假設(shè)R(p’,q’;r’)存在，r’=r-1,p’=p1,q’=q1,p1,q1

任意p’=p-1,

q’=q,

r’=rp’=p,

q’=q-1,

r’=r令n=R(p1,q1;r-1)+1=R(R(p-1,q;r),R(p,q-1,r);r-1)+1R(p,q,r)的存在性證明R(q1,q2,…,qk;r)條件：r,k?1,qi?r,i=1,2,…,k,都是給定正整數(shù)當(dāng)r=2

時(shí)，可以簡(jiǎn)記為R(q1,q2,…,qk)Ramsey

定理斷定Ramsey

數(shù)的存在性. Ramsey

數(shù)的確定是一個(gè)很困難的問題.r=1,是鴿巢原理，R(q1,q2,…,qk;1)=q1+q2+…+qk-k+1 r=2,k=2,是簡(jiǎn)單的Ramsey

定理.結(jié)果：9

個(gè)Ramsey

數(shù)的精確值，部分上界、下界r=2,k=3,只有一個(gè)精確值R(3,3,3)=17關(guān)于一般性Ramsey數(shù)的說明51

￡

R(3,3,3,3)

￡

6265fi

62162

￡

R(3,3,3,3,3)

￡

307322fi

307538

￡

R(3

3

3

3

3

3)

￡

1838500fi

53830

￡

R(3,3,4)

￡

3132fi

3145

￡

R(3,3,5)

￡

5759fi

5755

￡

R(3,4,4)

￡

7981fi

7993

￡

R(3,3,3,4)

￡

15384fi

93,159fi

153128

￡

R(4,4,4)

￡

236242fi

236一般性Ramsey數(shù)的上下界Ramsey定理的應(yīng)用引理1的證明引理2的證明證 不妨設(shè)

m>3，令

n?

R(5,m;4)，S為

n個(gè)點(diǎn)的集合.將

S

的所有的

4

元子集劃分成兩個(gè)子集族.

如果構(gòu)成凹

4

邊形，放到

T1,

如果構(gòu)成凸

4

邊形，則放到

T2.根據(jù)Ramsey數(shù)定義，或有5個(gè)點(diǎn)，其所有4元子集都構(gòu)成凹4

邊形；或有m

個(gè)點(diǎn)，其所有的4

子集都構(gòu)成凸4

邊形.若為前者，與引理

1

矛盾.

若為后者，根據(jù)引理

2，這

m

個(gè)點(diǎn)構(gòu)成凸

m

邊形的頂點(diǎn).命題證明例

11

最少連接纜線問題條件：15

臺(tái)工作站和10

臺(tái)服務(wù)器.每個(gè)工作站可以用一條電纜直接連到某個(gè)服務(wù)器.同一時(shí)刻每個(gè)服務(wù)器只能接受一個(gè)工作站的訪問.目標(biāo)：任何時(shí)刻,任意選一組工作站w1,w2,…,wk,k￡10.保證這組工作站可以同時(shí)訪問不同的服務(wù)器.問題：達(dá)到這個(gè)目標(biāo)需要的最少纜線數(shù)目N是多少？方案1：每個(gè)工作站都連到每個(gè)服務(wù)器，需要10·15=150根纜線，N

￡

150.用組合存在性定理解決實(shí)際問題例11的解決方案滿足目標(biāo)要求：任取10

個(gè)工作站.如果恰好為W1,W2,…,W10，Wi

訪問Si，i=1,…10,滿足要求;如果W1-W10

中只選中k

個(gè)工作站，不妨設(shè)為W1--Wk,剩下的10-k

個(gè)選自W11-W15.那么Wi

訪問Si，i=1,…,k.還剩下10-k

個(gè)服務(wù)器空閑，恰好分配給10-k

個(gè)工作站.結(jié)論：N￡60.證明N?60.假設(shè)在工作站和服務(wù)器之間纜線至多59

條.那么某個(gè)服務(wù)器將至多連接59/10

=5

工作站.如果選擇剩下的10

個(gè)工作站作為一組，那么只有9

個(gè)空閑的服務(wù)器，必有2個(gè)工作站連接同一服務(wù)器.與題目要求矛盾.方案的最優(yōu)性例

12

通信噪音干擾混淆圖G=<V,E>，V

為有窮字符集，{u,v}?

E u

和v

易混淆.

b0(G)：點(diǎn)獨(dú)立數(shù)，最大不混淆字符集大小編碼是字符串的集合xy

與uv

混淆x

與u

混淆且y

與v

混淆x=u

且y

與v

混淆x

與u

混淆且y=vV1·V2

的混淆圖是兩個(gè)混淆圖G

與