论文部分内容阅读
Ramsey定理的出现最早可追溯到1930年,由英国数学家及哲学家E.P.Ramsey提出,并且至今依然让图论和组合方面的很多学者为之着迷.它研究的是一个充分大的结构里给定子结构的存在性问题,它印证了完全无序是不可能的.Ramsey理论的思想和方法在代数学、信息论、逻辑学、和计算机科学等众多领域都有着广泛应用.很多诸如N.Alon,P.Erdos,J.H.Spencer和E.Szemeredi这样优秀的数学家专注其中,使得这一领域迅猛发展.这表现在各种类型Ramsey数的近似界的不断改进及一些图类的Ramsey型问题的准确值的确定上.对于依然存在于该领域的大量未解决问题,结构方法、概率方法和计算机方法等都是比较有效的工具.Ramsey数是将Ramsey理论中的存在性定理进行量化.给定图H1,H2,,Hk,k≥ 2,k-色Ramsey数月（H1,H2,,Hk）指最小的整数N满足对完全图KN的边用k种颜色任意去染,一定存在i∈ {1,2,,k}使得KN包含i色的子图Hi.若H=H1=H2=…=Hk,我们简记月（H1,H2,,Hk）:=Rk（H）.如果一个k-边染色的完全图满足对每个i∈ {1,2,,k}都不包含i色的子图Hi且其阶达到月（H1,H2,,Hk）-1,我们称之为（H1,H2,,Hk）-Ramsey图.设Cl和Pl分别为l个点的圈和路,K1,l和Wl分别为l+1个点的星和轮.这篇论文,我们将关注与圈、路、星及轮相关的多色Ramsey数.第1章,我们将介绍本文要用到的一些基本概念和符号,然后对本文涉及到的问题背景,进展以及已知结果给出一个全面的描述.第2-6章将具体介绍我们得到的新结果,分别是有关C4的三色Ramsey数,一些图类的Gallai-Ramsey数和超图中的一些Ramsey数.Gallai-Ramsey数和超图中的Ramsey数都是经典Ramsey数的一种变式,前者是染色方式发生了变化,后者是对图类做了变化.研究各种不同的Ramsey数的变式,能够深刻的了解一些图类的性质,使得Ramsey理论有更广泛的应用.1.Ramsey 数 R（C4,K1,m,Pn）在 1975 年,Parsons[Transactions American Mathematical Society,209（1975）33-44]为月（C4,K1,m）建立了一个紧的上界.定理A.对所有的m≥2,R（C4,K1,m）≤m+（?）+1.而且,如果m=l2+1且l≥1,则 R（C4,K1,m）≤m+（?）.由于（C4,K1,m）-Ramsey图的构造极其困难,已知的月（C4,K1,m）的确定值相当少,并且已知的这些值所需要的Ramsey图都是由极图Gq的子图以及对极图Gq的局部结构进行分析构造所得.基于对Gq图结构的兴趣以及受定理A的启发,我们研究月（C4,K1,m,P）的值,首先,我们对月（C4,K1,m,P）建立了 一个上界.该上界的获得主要基于我们对C4的一个Turan数的改进.定理 1.对所有的m,n≥2,R(C4,K1,m,Pn(≤m+n-1+（?）.而且,如果 m+n=l2+3 和l≥1,则R(C4,K1,m,Pn(≤m+n-2+（?）.在定理1中取n=2,就得到了定理A,即定理1推广了定理A.然后,我们通过对Gq图进一步分析,对Gq图的点进行了划分,从而构造出了一些（C4,K1,m,Pn）-Ramsey图,进而确定了C4对星对路的一些准确Ramsey值,这些值恰好取到定理1中的上界,这说明该上界是紧的.我们证明了下面的定理.定理2.设q为素数幂.除t=q+1且q是奇数时,如果q≡0（modl）或q+1≡0（mod t）,则R（C4,K1,q2-l+1,Pt+1）=q2+q+1.定理3.设q为素数幂,如果q+1≡0（mod t）且t≠q+1,则R（C4,K1,q2t+2,Pt+1）=q2+q+2.定理4.设q为素数幂,且q≡0（modt）及t≠q.如果1≤s≤[q-1/2]且s≠2[q/4]-1,则R（C4,K1,q2-t-s+1,Pt|1）=q2+q-s+1.定理5.如果q为偶素数幂且q-1≡0（mod l）则R（C4,K1,q（q-1）-t,Pt+1）=q2.结合定理2和3,并取t=1,可以得到Parsons的结论[Transactions American Mathematical Society,209（1975）33-44]:定理 B.设 q 为素数幂,则R（C4,K1,q2+1）=q2+q+2 和R（C4,K1,q2）=q2+q+1.另外,在定理4和5中取t=1,我们可以得到下面的结果,其中q是奇数的情况由 Zhang,Chen 和 Edwin Cheng 证明[Discrete Mathematics,340（2017）655-660],q 是偶数的情况由 Parsons 证明[Aequationes Mathematicae,14（1976）167-189].定理C.设q为素数幂.如果q是奇数,1≤s≤2[q/4]且s≠2[q/4]-1,或者q是偶数,1≤s≤q/2且s=q+1,则R（C4,K1,q2-s）=q2+q-（s-1）.2.Gallai-Ramsey 数 GRk（Cl）我们称完全图的一种边染色为Gallai-染色,如果这种染色没有彩虹三角形（三角形的三条边染不同的颜色）.至多k种颜色的Gallai-染色称为Gallai k-染色.给定图H1,H2,,Hk,k≥2,k-色Gallai-Ramsey数GR（H1,H2,,Hk）指最小的整数N满足完全图KN的任意Gallai k-染色均存在i∈{1,2,,k}使得KN包含一个i色的子图Hi.当H=H1=H2=…=Hk时,我们简写为GRk（H）.因为Gallai-染色是完全图的一种特殊的边染色方式,因此,对所有的k≥1,有GRk（H）≤Rk（H）.对于奇圈的多色 Ramsey 数,Bondy 和 Erdos[Journal of Combinatorial Theory,Series B,14（1973）46-54]猜想,对所有的k≥1和n≥2和n ≥ 2,Rk（C2n-1）=n·2k+1.Day 和 Johnson[Journal of Combinatorial Theory,Series B,124（2017）56-63]通过构造了一个反例证明了当n固定k充分大时该猜想是错误的.而最近Jenssen和Skokan[arXiv:1608.05705.]利用正则引理的方法证明了对于固定的k,当n充分大时上述猜想是正确的.第3章,我们将研究圈的Gallai-Ramsey数,我们证明了Bondy-Erdos猜想在Gallai-染色下对所有的k≥1和n≥2均成立.定理 6.对所有的k≥1和n≥2,GRk（C2n+1）=n·2k+1.其实关于圈的Gallai-Ramsey数已有很多学者进行过研究,也建立了一些上下界,但大都对奇圈与偶圈分别进行研究所得.我们发现若将偶圈的结果应用到奇圈的证明中,能很大程度上改进已有的界.基于这个想法,为了确定奇圈的准确Gallai-Ramsey数,我们首先对偶圈的Gallai-Ramsey数的界进行了一些改进,并发现用此界即可得到所有奇圈的准确Gallai-Ramsey数[arXiv:1809.00227].考虑了奇圈的情况后,我们依然对偶圈的情况很好奇.但偶圈与奇圈的多色Ramsey数表现很不相同,因为偶圈是二部图而奇圈不是.而且偶圈的多色Ramsey数的研究似乎更加困难.关于偶圈的多色Ramsey数,已知对所有的k≥2和n≥2,Rk（C2n）≥（n-1）k+n+k-1.除了这个一般性的下界,其他关于偶圈的多色Ramsey数一般性的结果很少.我们利用结构分析得到了一些二部图中圈存在条件的一些结果,从而确定了 Gallai-染色下所有偶圈的多色Ramsey值.该结果也使得第3章中奇圈Gallai-Ramsey数的证明更加简洁.定理7.对所有的k≥ 2和n≥2,#12值得注意的是,当k≥ 3时,定理7中给出的偶圈的Gallai-Ramsey值GRk（C2n）是比其Ramsey值Rk（C2n）严格小的.另外,由偶圈的Gallai-Ramsey值可以比较容易的得到所有路的准确Gallai-Ramsey数.至此,我们完全确定了所有圈和路的准确Gallai-Ramsey值.3.Gallai Ramsey 数 GRk（W2n）第4章,我们将关注轮的Ramsey数.对于2色的情形,我们仅知道R2（W3）=18,R2（W4）=15和R2（W5）=17,对于轮的一般的多色Ramsey值却一无所知.这里我们研究了偶轮的Gallai-Ramsey值.我们首先构造了所有偶轮的一个一般性的下界:性质1.对所有的n≥2和k≥2,然后我们得到了所有GRk（W4）的值,该值就等于性质1中的下界.定理8.对所有的k≥2,4.Gallai-Ramsey 数GR（t1K3,t2K3,,tkK3）涉及完全图的Ramsey数,目前只有很少的几个结果.K3是最小的非平凡完全图,所以考虑与其有关的Ramsey变式问题已被很多学者研究.Burr,Erdos和 Spencer[Transactions American Mathematical Society,209（1975）87-99]研究了多个K3不交并的2色Ramsey数,他们证明了对m≥n≥2,R（m K3,nK3）=3m+2n.第5章,我们将此研究拓展至Gallai-染色下,我们考虑多个K3不交并的Gallai-Ramsey数.首先,我们对GR（t1K3,t2K3,,tkK3）建立了一个上下界:定理9.对所有的整数k≥2和t1≥t2≥≥tk≥1,而且,注意到,当k是奇数且tk-1=tk=1时,定理9中的上下界是相等的,即此时我们可以得到GR（t1K3,,tkK3）的准确值.进一步,我们得到了对所有的2≥t1≥t2≥…≥tk≥1,GR（t1K3,,tkK3）的值.在下面的定理中,当t1=…=ts=2及ts+1==tk=1时我们把GR（t1K3,…,tkK3）简记为GRk（s;k-s）.定理10.令k≥2且k≥s≥0为整数.如果k是偶数,则GRk（s;k-s）=5k/2+2s+1.如果k是奇数,则5.Ramsey 数R（Pm3,Sm3）超图H是一个集合组（V,E）,其中V是H的点集,E是V非空子集族,称为H的边.如果H的每条边都是V的r元子集,我们称H为r-一致超图.Rnr表示n个点的完全r一致超图,它的边由所有的r元子集构成.对给定的r-一致超图H和G,Ramsey数R（H,G）是指最小的正整数N满足完全r-一致超图RNT的任意红蓝边染色或者包含一个红色的H或者包含一个蓝色的G.超图中l条边的k-一致松弛路、圈和星分别表示为Plr,Clr和Slr.3-一致超图中圈和路的Ramsey数被很多学者研究,并被Omidi和Shahsiah[Journal of Combinatorial Theory,SeriesA,121（2014）64-73]完全确定.受他们的方法以及一般图路对星的Ramsey数的启发,第6章,我们研究3-一致超图中的路对星Ramsey数,得到了如下结果:定理11.对所有的n≥2m≥2,R（Pm3,Sn3）=2m+1+[m-1/2],并且,对所有的m≤[1/4n]≥2,R（Pm3,Sn3）=2m+1.