圖的彩虹數(shù)和關(guān)聯(lián)著色.pdf

1、Ramsey理論在組合數(shù)學(xué)中是一個(gè)很大很有趣的研究領(lǐng)域,它表達(dá)了很深刻的數(shù)學(xué)思想,大大拓展了鴿籠原理的內(nèi)涵。Ramsey理論的結(jié)果不僅在圖論和組合數(shù)學(xué)中非常重要,在數(shù)論,集合論,邏輯學(xué),分析論,代數(shù)以及幾何學(xué)中也有著重要應(yīng)用。有很多著名的深刻的定理是通過運(yùn)用Ramsey理論的結(jié)果得到的,其中包括Erdos-Rado的典型定理,它將Ramsey原始定理擴(kuò)展到無限多著色；Shelah定理,它擴(kuò)展了Hales-Jewett定理(它本身是van

2、 derWaerden定理的推廣);Galvin,Prikry和Hindman關(guān)于無限序列Ramsey性質(zhì)的定理,以及Gowers的定理,它成功解決了Banach在1932年提出的猜想,即證明了可分的Hibert空間是唯一同構(gòu)于其所有無限維子空間的Banach空間。 Ramsey理論已向各個(gè)方向延伸發(fā)展,其中就包括Erdos,Simonovits和Sós在上個(gè)世紀(jì)七十年代提出的反Ramsey理論。反Ramsey理論研究了在邊任意

3、著色即相鄰的邊也可以有相同的顏色的情況下存在所有邊的顏色都不一樣的大子圖。同時(shí),反Pmmsey數(shù)和彩虹數(shù)的概念也得到了定義。 而為了研究二部圖的強(qiáng)鄰邊著色,Brualdi和Massey定義了圖的關(guān)聯(lián)著色數(shù)并用圖的最大度對(duì)其進(jìn)行了界定。一個(gè)圖的關(guān)聯(lián)著色數(shù)正好等于它的關(guān)聯(lián)二部圖的強(qiáng)鄰邊著色數(shù)。圖的強(qiáng)鄰邊著色即對(duì)圖的邊進(jìn)行著色以使得著同一顏色的邊為圖的導(dǎo)出匹配,即此匹配為圖的導(dǎo)出子圖。強(qiáng)鄰邊著色數(shù)為能使圖進(jìn)行強(qiáng)鄰邊著色的最小顏色數(shù)。

4、 本文分為兩個(gè)部分,第一部分主要考慮圖的彩虹數(shù)問題,第二部分主要考慮圖的關(guān)聯(lián)著色問題。 第一部分由第二和第三章組成。給定兩個(gè)圖G和H,我們用f(G,H)定義最大的顏色數(shù)c,可以用c種顏色對(duì)圖G進(jìn)行邊著色使得圖G的任意H子圖至少有兩邊著同一種顏色。也就是說,任意的用rb(G,H)=f(G,H)+1種顏色對(duì)圖G進(jìn)行邊著色都會(huì)包含一個(gè)圖G的彩虹子圖H。其中彩虹子圖為一個(gè)任意兩邊都有不同顏色的子圖。數(shù)rb(G,H)稱為H相對(duì)于G的

5、彩虹數(shù)。我們簡單的用f(n,H)和rb(n,H)分別去表示f(Kn,H)和rb(Kn,H)。數(shù)f(n,H)和rb(n,H)分別被簡稱為圖H的反Ramsey數(shù)和彩虹數(shù)。當(dāng)G為完全二部圖Km,n時(shí),數(shù)rb(G,H)被簡稱為圖H的二部彩虹數(shù)。 在第二和第三章,我們研究并得到了所有匹配的彩虹數(shù)rb(n,kk2)和二部彩虹數(shù)rb(Km,n,kK2),其中H=kK2為一個(gè)有k條邊的匹配M。我們得到如下結(jié)果。 1.定義ext(m,n,

6、H)為兩部各有m和n點(diǎn)的二部圖G(m,n)不包含同構(gòu)于H的子圖所能有的最大邊數(shù)。對(duì)于所有的m≥n≥k≥2,我們有： 2.定義ext(n,H)為n個(gè)點(diǎn)的圖G不包含同構(gòu)于H的子圖所能有的最大邊數(shù)。對(duì)于所有k≥2,我們有：在第四章,我們研究了圖的關(guān)聯(lián)著色。給定圖G(V,E),令I(lǐng)(G)={(v,e):v∈V, e∈E,且v與e相關(guān)聯(lián)}為G的關(guān)聯(lián)集。兩個(gè)關(guān)聯(lián)對(duì)(v,e)和(w,f)是相鄰的關(guān)聯(lián)對(duì),當(dāng)且僅當(dāng)下列三個(gè)條件之一成立：(1)v=