【摘要】：Ramsey理論一直是組合數(shù)學(xué)的研究熱點(diǎn).它是對充分大的結(jié)構(gòu)進(jìn)行劃分的研究,印證了完全的無序是不可能的Ramsey理論有四個彼此獨(dú)立的源頭.1892年D. Hilbert為了研究整系數(shù)有理函數(shù)的不可約性,證明了希爾伯特立方體引理：如果全體正整數(shù)任意劃分為有限類,則其中必有一類包含任意維的仿射立方體.1916年,I. Schur為了得到歐拉猜想的一個同余形式的定理,證明了如下引理：如果全體正整數(shù)任意劃分為有限類,則其中必有一類包含x,y,z滿足x+y=z.1927年,B.L. van der Waerde n證明了,如果全體正整數(shù)任意劃分為有限類,則其中必有一類包含任意長的等差數(shù)列.1930年,為了研究命題邏輯的決策過程,F.P. Ramsey證明了,如果一個圖包含足夠多的頂點(diǎn)(依賴于k),那么它一定包含k個點(diǎn)的團(tuán)集或獨(dú)立集.Ramsey理論的主要數(shù)學(xué)思想為,無論多么龐大和復(fù)雜的系統(tǒng)S,我們都能找到足夠大的包含S的超級系統(tǒng)Q,使得若把Q任意劃分為有限類,則其中必有一類包含S. Ramsey理論的思想和方法在集合論、組合數(shù)論、幾何學(xué)、邏輯學(xué)、概率論和理論計(jì)算機(jī)科學(xué)等眾多領(lǐng)域有著廣泛應(yīng)用.其研究者包括Wolf獎得主P. Erdos, L. Lovasz, Fields獎得主T. Gowers,陶哲軒,Abel獎得主E. Szemeredi等人R.L. Graham, B.L. Rothschild口J.H. Spencer的著作Ramsey Theory是這一領(lǐng)域的經(jīng)典專著.廣義Ramsey數(shù)的研究是Ramsey理論的重要方向.對于兩個圖F和H,廣義Ramsey數(shù)R(F,H)指的是最小的正整數(shù)N,使得對每一個N階圖G,要么G包含F(xiàn),要么G的補(bǔ)圖包含H. Ramsey數(shù)的作用在于量化Ramsey理論中的一些存在性定理.長期以來,Ramsey數(shù)的漸近階的研究取得了長足發(fā)展.最近三十年來,Ramsey數(shù)的準(zhǔn)確值的研究突飛猛進(jìn).本論文旨在進(jìn)一步推進(jìn)Ramsey數(shù)的準(zhǔn)確值計(jì)算.本論文在圖Ramsey理論的六個方面取得了新的進(jìn)展,分別是輪-輪Ramsey數(shù),圈-輪Ramsey數(shù),樹-扇Ramsey數(shù),星-輪Ramsey數(shù),星臨界Ramsey數(shù)和誘導(dǎo)Ramsey數(shù).后兩者并不是通常意義下的Ramsey數(shù)而是它的變式.前人研究了各種不同的Ramsey數(shù)的變式,目的在于更深刻地刻畫Ramsey數(shù),并得到一些更有意義的結(jié)論.1.輪-輪Ramsey數(shù)輪由圈和一個額外點(diǎn)構(gòu)成,其中額外點(diǎn)與圈上的每一個點(diǎn)均相連.輪對輪的Ramsey數(shù),目前只知道六個小值,即3≤m≤n≤5時, R(Wn,Wm)的值.并且除了R(W3,W3)和R(W3,W4),其它四個值的計(jì)算都需要借助計(jì)算機(jī).它們的值如下：我們將已知的輪對輪的Ramsey數(shù)擴(kuò)展為無限多個,證明了下面的定理.定理1.2.圈-輪Ramsey數(shù)圈是圖論中最常研究的結(jié)構(gòu)之一.由于圈和輪的基本性質(zhì),圈-輪Ramsey數(shù)問題很早就引起了數(shù)學(xué)家們的興趣.令Cm表示m階圈,Wn表示n+1階輪.1983年S.A.Burr和P. Erdos率先研究了圈-輪Ramsey數(shù),他們證明了：對n≥5,R(C3,Wn)=2n+1.surahmat等人和史靈生得到了大圈對小輪的Ramsey數(shù)的一系列結(jié)果.最終陳耀俊等人證明了,當(dāng)n是奇數(shù),m≥n≥3且(m,n)≠(3,3)時,R(Cm,Wn)=3m-2；當(dāng)n是偶數(shù),m≥3n/2+1時,R(Cm,Wn):2m-1.大輪對小圈的Ramsey數(shù)一直以來沒有新的進(jìn)展.我們注意到圖與補(bǔ)圖的邊數(shù)和弱泛圈性的聯(lián)系,結(jié)合S.Brandt的兩個弱泛圈定理,G.A.Dirac,P Erdos和T.Gallai,R.J.Faudree等人的幾個長圈定理,得到了關(guān)于大輪對小圈的Ramsey數(shù)的系列結(jié)果.定理2.R(Cm,Wn)=2n+1對m為奇數(shù),n≥3(m一1)/2且(m,n)≠(3,3),(3,4)成立.定理3.R(Cm,Wn)=3m-2對m,n為奇數(shù)且mn3(m-1)/2成立.定理4.R(Cm,Wn)=3m-2對n為奇數(shù),m為偶數(shù)且mn3m/2成立.以上定理縮小了未知的圈-輪Ramsey數(shù)的范圍,并為其它涉及圈或輪的Ramsey數(shù)提供了新的工具.3.樹-扇Ramsey數(shù)涉及任意樹的Ramsey數(shù),目前只有很少的幾個結(jié)果.V.Chvatal得到了樹對完全圖的Ramsey數(shù).S.A.Burr等人證明了R(Tn,Cm)=2n-1對奇數(shù)m≥3和n≥756m10成立P Erd6s等人證明了R(Tn,Bm)=2n-1對n≥3m-3成立.我們充分考慮任意樹在圖中的嵌入形式,采用分類討論、由簡到繁的方法,證明對正整數(shù)n≥3m2-2m-1,Tn是Fm-good的,即：定理5.R(Tn,Fm)=2n-1對正整數(shù)n≥3m2-2m-1都成立.4.星-輪Ramsey數(shù)階數(shù)為n+1的星和輪分別表示為K1,m和Wn.關(guān)于星-輪Ramsey數(shù)已經(jīng)有數(shù)篇論文發(fā)表,唯一未解決的情況是當(dāng)m為偶數(shù)且10≤m≤n+1時R(Wm,K1,n)的值.我們將利用Erdos-Simonovits穩(wěn)定性定理,部分地解決這一問題.穩(wěn)定性定理是說,對于任意的ε0和禁止子圖類L,存在δ0和n0使得若G是nn。個點(diǎn)、不含￡的圖,且e(G)≥(1—1/p)(2n)-δn2,那么可以通過更改(增加或刪除)至多εn2條邊得到完全p-部圖.把這一定理作為引理,我們證明了如下結(jié)論.定理6.對于每個給定的偶數(shù)m≥6和充分大的n,都有R(Wm,K1,n)= 2n+m/2μ,其中當(dāng)m/2和n均為偶數(shù)時μ=1,否則μ=0.5.星臨界Ramsey數(shù)我們從更一般的觀點(diǎn)看Ramsey數(shù).圖G稱作(F.H)-Ramsey,表為G→(只H),如果對圖G邊集的任意紅藍(lán)著色,存在紅色F或者藍(lán)色H.進(jìn)-步,如果G是(F.H)-Ramsey的但G的每個真子圖均不是(F.H)-Ramsey的,那么我們說G是(F.H)-minimal的.我們把所有(F.H)-minimal的圖類表示為M(F,H).顯然極小Ramsey圖的最小階數(shù)就是Ramsey數(shù),即R(只H)=minG∈M(F.H)|V(G)|最近幾年,一些學(xué)者研究了另外兩個自然的參數(shù),即極小Ramsey圖的最小邊數(shù)ninG∈M(F,H)|E(G)|和最小度數(shù)minG∈M(F,H)δ|(G).不過這些遠(yuǎn)未完全解決.Hook口Isaak引入了星臨界Ramsey數(shù)的概念.令Kτ-1(?)K1,k表示由Kr-1和額外點(diǎn)v得到的圖,其中v與Kr-1中k個點(diǎn)相鄰.星臨界Ramsey數(shù)r*(G1,G2)指的是最小的正整數(shù)k,使得對于Kr-1 (?) K1，，k的任意紅藍(lán)二邊染色,一定有紅色的G1或者藍(lán)色的G2,這里r表示Ramsey數(shù)R(G1,G2).在此之前,Erdos和Faudree研究了兩個相關(guān)概念：上邊Ramsey數(shù)和下邊Ramsey數(shù),上邊R amsey數(shù)u(G1,G2)是最小的正整數(shù)q,使得任意滿足G(?)Kr和e(G)≥q的圖G的任意紅藍(lán)二邊染色,一定有紅色的G1或者藍(lán)色的G2,這里r表示Ramsey數(shù)R(G1,G2).下邊Ramsey數(shù)l(G1,G2)是最小的正整數(shù)p,使得存在滿足G(?)Kr和至少p條邊的圖G,對于它的任意紅藍(lán)二邊染色,一定有紅色的G1或者藍(lán)色的G2,這里r表示Ramsey數(shù)R(G1,G2).我們研究了這些定義問的關(guān)系.我們注意到星臨界Ramsey數(shù)有兩個子類：當(dāng)r*(G1,G2)=R(G1,G2)1時,稱這一對圖(G1,G2)是Ramsey-full的；當(dāng)r*(G1,G2)與R(G1,G2)的值通過Ramsey good建立聯(lián)系時,我們建立 sizeRamsey good的概念.令G2是G1-good的至少兩個頂點(diǎn)的連通圖.令V1,V2…,Vχ(G1)是G1的使用χ(G1)種顏色的正常頂點(diǎn)著色的色組,并且假設(shè)|V1|≤|V2|≤…≤|Vχ(G1)|.選擇一種著色方案使得|V1|盡可能小,并用σ(G1)表示|V1|.在所有|V1|=σ(G1)的正常頂點(diǎn)著色中,令丁(G1)=min{|E(v,Vi)|| v∈V1,2≤i≤χ(G1)},即V1中某個頂點(diǎn)在某個M中的最小度數(shù),這里2≤i≤χ(G1).如果σ(G1)=1,或者δ(G2)=1,或者K(G2)≥2,我們有r*(G1,G2)≥(x(G1)-2)(|V(G2)|-1)+σ(G1)+δ(G2)+τ(G1)-2如果上式等式成立,我們稱G2是G1-size good的.我們還得到了下面的兩個定理.定理7.設(shè)正整數(shù)k,l≥3,若m和n充分大,那么r*(mKk,nKl)=(k-1)m+(l-1)n+max{m,n}+R(Kk-1,Kl-1)-3定理8.對奇數(shù)m和nm≥3,有u(Cn,Cm)=2(n-1)2+2.對奇數(shù)m,n≥m≥3和(m,n)≠(3,3),有r*(Cn,Cm)=n+1.6.誘導(dǎo)Ramsey數(shù)給定圖G1和G2,誘導(dǎo)Ramsey數(shù)IR(G1,G2)指的是最小的正整數(shù)N,使得存在N階圖G,對于G的任意紅藍(lán)二邊染色,要么G包含G1作為誘導(dǎo)子圖,其所有邊均染紅色；要么G包含G2作為誘導(dǎo)子圖,其所有邊均染藍(lán)色.因?yàn)橥耆訄D一定是誘導(dǎo)子圖,所以完全圖的誘導(dǎo)Rams ey數(shù)和廣義Ramsey數(shù)是完全一致的.我們研究了涉及匹配、星、完全圖、完全多部圖和四圈等圖類的誘導(dǎo)Ramsey數(shù)的準(zhǔn)確值,并得到下面五個定理.定理9.對于n1≥n2≥…≥nl≥2,有IR(kK2,Kn1∪Kn2∪…∪Knl)= kn1+n2+…+nl.定理10.IR(kK2,Kn-e)=kn對奇數(shù)n≥3成立,且當(dāng)k=1,2,3時,對偶數(shù)n≥4成立.定理11.IR(2Km,Kn)=2R(Km,Kn)對m,n≥2成立.定理12.IR(K1,k,Kn-1+lK1)=(K-1)n(n-1)/2+n+l-1對k≥l+1且n≥2成立.定理13.IR(C4,K1,k)≤min{[3t/2+k/t+k+1/2]|t∈(?)+1}},等式對于1≤k≤5成立.
[Abstract]:......
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王殿軍;完全圖圈分解的一種新方法[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);1993年04期

2 鄧覲超,佟玉鳳;有關(guān)完全圖的算法及實(shí)現(xiàn)技術(shù)[J];煙臺大學(xué)學(xué)報(bào)(自然科學(xué)與工程版);1997年03期

3 張文軍;;完全圖的最小6-圈覆蓋和8-圈覆蓋[J];山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年04期

4 O賜蜢

本文編號：2369245