论文部分内容阅读
Ramsey理论一直是组合数学的研究热点.它是对充分大的结构进行划分的研究,印证了完全的无序是不可能的Ramsey理论有四个彼此独立的源头.1892年D. Hilbert为了研究整系数有理函数的不可约性,证明了希尔伯特立方体引理：如果全体正整数任意划分为有限类,则其中必有一类包含任意维的仿射立方体.1916年,I. Schur为了得到欧拉猜想的一个同余形式的定理,证明了如下引理：如果全体正整数任意划分为有限类,则其中必有一类包含x,y,z满足x+y=z.1927年,B.L. van der Waerde n证明了,如果全体正整数任意划分为有限类,则其中必有一类包含任意长的等差数列.1930年,为了研究命题逻辑的决策过程,F.P. Ramsey证明了,如果一个图包含足够多的顶点(依赖于k),那么它一定包含k个点的团集或独立集.Ramsey理论的主要数学思想为,无论多么庞大和复杂的系统S,我们都能找到足够大的包含S的超级系统Q,使得若把Q任意划分为有限类,则其中必有一类包含S. Ramsey理论的思想和方法在集合论、组合数论、几何学、逻辑学、概率论和理论计算机科学等众多领域有着广泛应用.其研究者包括Wolf奖得主P. Erdos, L. Lovasz, Fields奖得主T. Gowers,陶哲轩,Abel奖得主E. Szemeredi等人R.L. Graham, B.L. Rothschild口J.H. Spencer的著作Ramsey Theory是这一领域的经典专著.广义Ramsey数的研究是Ramsey理论的重要方向.对于两个图F和H,广义Ramsey数R(F,H)指的是最小的正整数N,使得对每一个N阶图G,要么G包含F,要么G的补图包含H. Ramsey数的作用在于量化Ramsey理论中的一些存在性定理.长期以来,Ramsey数的渐近阶的研究取得了长足发展.最近三十年来,Ramsey数的准确值的研究突飞猛进.本论文旨在进一步推进Ramsey数的准确值计算.本论文在图Ramsey理论的六个方面取得了新的进展,分别是轮-轮Ramsey数,圈-轮Ramsey数,树-扇Ramsey数,星-轮Ramsey数,星临界Ramsey数和诱导Ramsey数.后两者并不是通常意义下的Ramsey数而是它的变式.前人研究了各种不同的Ramsey数的变式,目的在于更深刻地刻画Ramsey数,并得到一些更有意义的结论.1.轮-轮Ramsey数轮由圈和一个额外点构成,其中额外点与圈上的每一个点均相连.轮对轮的Ramsey数,目前只知道六个小值,即3≤m≤n≤5时, R(Wn,Wm)的值.并且除了R(W3,W3)和R(W3,W4),其它四个值的计算都需要借助计算机.它们的值如下：我们将已知的轮对轮的Ramsey数扩展为无限多个,证明了下面的定理.定理1.2.圈-轮Ramsey数圈是图论中最常研究的结构之一.由于圈和轮的基本性质,圈-轮Ramsey数问题很早就引起了数学家们的兴趣.令Cm表示m阶圈,Wn表示n+1阶轮.1983年S.A.Burr和P. Erdos率先研究了圈-轮Ramsey数,他们证明了：对n≥5,R(C3,Wn)=2n+1.surahmat等人和史灵生得到了大圈对小轮的Ramsey数的一系列结果.最终陈耀俊等人证明了,当n是奇数,m≥n≥3且(m,n)≠(3,3)时,R(Cm,Wn)=3m-2；当n是偶数,m≥3n/2+1时,R(Cm,Wn):2m-1.大轮对小圈的Ramsey数一直以来没有新的进展.我们注意到图与补图的边数和弱泛圈性的联系,结合S.Brandt的两个弱泛圈定理,G.A.Dirac,P Erdos和T.Gallai,R.J.Faudree等人的几个长圈定理,得到了关于大轮对小圈的Ramsey数的系列结果.定理2.R(Cm,Wn)=2n+1对m为奇数,n≥3(m一1)/2且(m,n)≠(3,3),(3,4)成立.定理3.R(Cm,Wn)=3m-2对m,n为奇数且m<n<3(m-1)/2成立.定理4.R(Cm,Wn)=3m-2对n为奇数,m为偶数且m<n<3m/2成立.以上定理缩小了未知的圈-轮Ramsey数的范围,并为其它涉及圈或轮的Ramsey数提供了新的工具.3.树-扇Ramsey数涉及任意树的Ramsey数,目前只有很少的几个结果.V.Chvatal得到了树对完全图的Ramsey数.S.A.Burr等人证明了R(Tn,Cm)=2n-1对奇数m≥3和n≥756m10成立P Erd6s等人证明了R(Tn,Bm)=2n-1对n≥3m-3成立.我们充分考虑任意树在图中的嵌入形式,采用分类讨论、由简到繁的方法,证明对正整数n≥3m2-2m-1,Tn是Fm-good的,即：定理5.R(Tn,Fm)=2n-1对正整数n≥3m2-2m-1都成立.4.星-轮Ramsey数阶数为n+1的星和轮分别表示为K1,m和Wn.关于星-轮Ramsey数已经有数篇论文发表,唯一未解决的情况是当m为偶数且10≤m≤n+1时R(Wm,K1,n)的值.我们将利用Erdos-Simonovits稳定性定理,部分地解决这一问题.稳定性定理是说,对于任意的ε>0和禁止子图类L,存在δ>0和n0使得若G是n>n。个点、不含￡的图,且e(G)≥(1—1/p)(2n)-δn2,那么可以通过更改(增加或删除)至多εn2条边得到完全p-部图.把这一定理作为引理,我们证明了如下结论.定理6.对于每个给定的偶数m≥6和充分大的n,都有R(Wm,K1,n)= 2n+m/2μ,其中当m/2和n均为偶数时μ=1,否则μ=0.5.星临界Ramsey数我们从更一般的观点看Ramsey数.图G称作(F.H)-Ramsey,表为G→(只H),如果对图G边集的任意红蓝着色,存在红色F或者蓝色H.进-步,如果G是(F.H)-Ramsey的但G的每个真子图均不是(F.H)-Ramsey的,那么我们说G是(F.H)-minimal的.我们把所有(F.H)-minimal的图类表示为M(F,H).显然极小Ramsey图的最小阶数就是Ramsey数,即R(只H)=minG∈M(F.H)|V(G)|最近几年,一些学者研究了另外两个自然的参数,即极小Ramsey图的最小边数ninG∈M(F,H)|E(G)|和最小度数minG∈M(F,H)δ|(G).不过这些远未完全解决.Hook口Isaak引入了星临界Ramsey数的概念.令Kτ-1(?)K1,k表示由Kr-1和额外点v得到的图,其中v与Kr-1中k个点相邻.星临界Ramsey数r*(G1,G2)指的是最小的正整数k,使得对于Kr-1 (?) K1，k的任意红蓝二边染色,一定有红色的G1或者蓝色的G2,这里r表示Ramsey数R(G1,G2).在此之前,Erdos和Faudree研究了两个相关概念：上边Ramsey数和下边Ramsey数,上边R amsey数u(G1,G2)是最小的正整数q,使得任意满足G(?)Kr和e(G)≥q的图G的任意红蓝二边染色,一定有红色的G1或者蓝色的G2,这里r表示Ramsey数R(G1,G2).下边Ramsey数l(G1,G2)是最小的正整数p,使得存在满足G(?)Kr和至少p条边的图G,对于它的任意红蓝二边染色,一定有红色的G1或者蓝色的G2,这里r表示Ramsey数R(G1,G2).我们研究了这些定义问的关系.我们注意到星临界Ramsey数有两个子类：当r*(G1,G2)=R(G1,G2)1时,称这一对图(G1,G2)是Ramsey-full的；当r*(G1,G2)与R(G1,G2)的值通过Ramsey good建立联系时,我们建立 sizeRamsey good的概念.令G2是G1-good的至少两个顶点的连通图.令V1,V2…,Vχ(G1)是G1的使用χ(G1)种颜色的正常顶点着色的色组,并且假设|V1|≤|V2|≤…≤|Vχ(G1)|.选择一种着色方案使得|V1|尽可能小,并用σ(G1)表示|V1|.在所有|V1|=σ(G1)的正常顶点着色中,令丁(G1)=min{|E(v,Vi)|| v∈V1,2≤i≤χ(G1)},即V1中某个顶点在某个M中的最小度数,这里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.设正整数k,l≥3,若m和n充分大,那么r*(mKk,nKl)=(k-1)m+(l-1)n+max{m,n}+R(Kk-1,Kl-1)-3定理8.对奇数m和n>m≥3,有u(Cn,Cm)=2(n-1)2+2.对奇数m,n≥m≥3和(m,n)≠(3,3),有r*(Cn,Cm)=n+1.6.诱导Ramsey数给定图G1和G2,诱导Ramsey数IR(G1,G2)指的是最小的正整数N,使得存在N阶图G,对于G的任意红蓝二边染色,要么G包含G1作为诱导子图,其所有边均染红色；要么G包含G2作为诱导子图,其所有边均染蓝色.因为完全子图一定是诱导子图,所以完全图的诱导Rams ey数和广义Ramsey数是完全一致的.我们研究了涉及匹配、星、完全图、完全多部图和四圈等图类的诱导Ramsey数的准确值,并得到下面五个定理.定理9.对于n1≥n2≥…≥nl≥2,有IR(kK2,Kn1∪Kn2∪…∪Knl)= kn1+n2+…+nl.定理10.IR(kK2,Kn-e)=kn对奇数n≥3成立,且当k=1,2,3时,对偶数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成立.