论文部分内容阅读
Ramsey定理是组合数学的一个基本结果,它指:阶数充分大的边染色完全图中一定有你需要的单色团.这结果的第一版本由英国数学家及哲学家F.P.Ramsey在1930年给出.由此开创了组合数学的一分支,现在称之为Ramsey理论.Ramsey理论叙述的是:完全的无序是不可能的.Ramsey理论中的问题常常以这样的方式提出:某结构中元素达到多大时能保证某特定的性质出现?Ramsey理论一直是组合数学的研究热点.除了组合学,Ramsey理论在众多其他数学分支的发展中也扮演重要角色,涉及代数学,集合论,逻辑学,概率论和几何学等等.其研究者包括Wolf奖得主P.Erdos,L.Lovasz,Fields奖得主T.Gowers,陶哲轩,Abel 奖得主 E.Szemeredi 等人.R.L.Graham,B.L.Rothschild和J.H.Spencer的著作Ramsey Theory是这一领域的经典教材.给定图G1,G2,,Gk,k≥ 2,色Ramsey数R（G1,G2,,Gk）指最小的整数N,满足对任意k-边染色的完全图KN,一定存在i ∈ {1,2,,k}使得KN包含i色的子图G,.如果一个kk-边染色的完全图满足对每个i ∈ {1,2,,k}它都不包含i色的子图Gi且其阶达到R（G1,G2,,Gk）-1,我们称之为（G1,G2,,Gk）-Ramsey图.对2-色情形,我们也可以用"补图"的语言定义Ramsey数和Ramsey图.给定图G1,G2,Ramsey数R（G1,G2）指最小的整数N,满足对任意N阶图G,要么G包含子图G1要么它的补图G包含子图G2.我们称自身不包含子图G1且其补图不包含子图G2的R（G1,G2）-1阶图为（G1,G2）-Ramsey图.设Gm为长度为m的圈,而K1,n和Wn分别为n+ 1阶星和轮.这篇论文,我们将关注与四圈,星及轮相关的多色Ramsey数.如果仅考虑2-色情形,我们有一些已知的结果.在1975年,Parsons[Transactions American Mathematical Society,209（1975）,33-44]为R（C4,K1,n）建立了一个紧的世界.定理A.对所有n≥2,R（C4,K1,n）≤n+「（?）」+ 2.而且,如果n=l2+1且 l ≥ 1,则 R（C4,K1,n）≤n+（?）+1.进一步,在该论文中,利用极图Gq,它的构造分别由Brown及由Erdos,Renyi和Sos在1966年独立完成,Parsons证明了:当g为素数幂而n = g2或g2+1时,R（4 K1,n）的值恰好取到定理A中的上界.换句话讲,他证明了:定理B.设g为素数幂.则R（C4,K1,q2+1）=g2+g+2和R(C4,K1,q2= g2+g+1.在 1989 年,Burr 等[Annals ofDiscrete Mathematics,41（1989）,79-89]给出R（C4,K1,n）的一个下界:定理C.如果n充分大,则R（C4,K1,n）>n+「（?）-6nα/2」,其中α为一个小于11/20的常数.在该论文中,他们还给出了下面猜想,为此,作者之一 Erdos悬赏$100征求该猜想的证明或否定.Burr猜想.对任意的常数c,总有无穷个n使得R(C4,K1<n+（?）-c.但是到目前为止,我们甚至找不到一个n使得R（（C4,K1,n）<n+（?）.也就是说,似乎Burr猜想没有事实根据的.由于K1,n是Wn的一个生成子图,故对任意的n,R（C4,K1,n）≤R（C4,Wn）.张闫博等发现当n≥6时所有已确定的Ramsey数R（C4,Wn）和R（C4,K1,n）都相等.在 2014 年,他们证明这一事实[Electronic Journal of Graph Theory and Applications,2（2014）,110-114]:定理D.对所有n ≥ 6,R（C4,K1,n）= R（C4,Wn）.基于对Burr猜想的兴趣和受上面四个定理的启发,我们开始研究与C4相关的一些Ramsey数,得到了一些关于四圈,星,轮的多色Ramsey数（包括2-色情况）的新结果,详细证明请阅读本文的第2章至第5章.1.Ramsey 数 R（C4,K1,n）也许因为（C4,K1,n）-Ramsey图的构造极其困难的缘故,至今Burr猜想尚未解决,事实上已确定的Ramsey数R（C4,K1,n）的值相当少.设g为素数幂.除定理 B 中 R（C4,K1,q2）和R（C4,K1,K1,q2+1）值,Parsons 也考虑R（C4 K1,q2-t）的值其中t为某给定范围的整数,并得到下面结果[Aequationes Mathematicae,14（1976）,167-189].定理E.设g为素数幂.如果g是偶数,1≤t≤q+1且t≠q,或g是奇数,0 ≤ t≤ 2 「q/4」且 t 是偶数,则R（C4,K1,q2-t）= q2 +q-（t-1）.注意到定理B和定理E中所有确定的Ramsey数的取值恰好是定理A所提供的上界,于是,我们知道这些值的获取主要工作在于Ramsey图的构造.而Parsons所需要的Ramsey图都是由极图Gq的子图提供的.在第2章,首先,我们将定理E推广至g为奇素数幂而t满足1≤t≤2「q/4]且t ≠ 2「q/4」-1的情形.我们的主要想法是基于对极图Gq的局部结构的分析进行构造所需Ramsey图.尤其,我们针对奇数t所构造的（C4,K1,q2-t）-Ramsey图并不是Gq的子图.下面定理是第2章的主要结果之一.定理1.设g为奇素数幂.如果1≤t≤2「q/4]且t≠2「q/4」-1,则R（C4,K1,q2-t））= q2 + q-（t-1）.值得注意的是,这些Ramsey数确定的n值都在一个素数幂附近.既然Burr猜想仍然是未解决的,我们好奇当n不在素数幂附近时R(C4,K1,n 的取值.当然,越多类型n的R（C4,K1,n）值确定,我们就越有可能接近R（C4,K1,n）的好的一般下界.于是,我们开始尝试去对其他类型的n研究R（C4,K1,n）的值.为此,我们在Galois域上的平面内构造了一个阶为q2-1的无四圈图Γq.基于对该类图的结构分析,我们获得几类（C4,K1,n）-Ramsey图.利用这些图,我们证明了下面两个定理,即第2章的另外两个主要定理.定理2.设q≥4为偶素数幂且t=1,0,-2.则R（C4,K1,（g-1）2+t）=（q-1）2 + q +t.定理3.设q≥5为奇素数幂且t=2,4,,2「q/4」.则R（C4,K1,q（q-1）t）=q2-t容易验证定理1,2和3中的Ramsey数的取值要么恰好为定理A中通常的上界n + 「（?）」+ 2或者与该界仅相差1.2.三色 Ramsey 数 R(（C4,C4,K1,n）Turan数ex（t,C4）指无四圈的t阶图能达到最大边数.设g为素数幂.有趣的是:不管对 Turan 数 ex（g2 + g + 1,C4）还是对 Ramsey 数 R（C4,K1,q2+1）,Gq都是一个极值图.显然,每个Kq2+q+1包含一个Gq的嵌入.一个自然的问题:Kg2+q+1至多能嵌入多少个边不交的Gq?这儿,我们没能给出确切的答案,但利用Singer差集我们发现每个Kq2+q+1至少能够包含两个边不交的Gq嵌入.基于这个发现,我们能够精巧地构造一类（C4,C4,K1 n）-Ramsey图.在第3章,我们仅考虑三色Ramsey数R(（C4,C4,K1,n）.首先,我们建立了一个R（C4,C4,K1,n）的上界：读者在该章也可以看到R(C4,C4,K1,5= 13,也就是说,当n = 5时该界取到,所以它是紧的.更进一步,我们证明了:如果l为素数幂,定理4中对n =l2-l的相应Ramsey数的上界 恰好取到.也就是说,我们确定无穷个R（C4,C4,K1,n）的值如下:定理5.对所有的素数幂3.三色 Ramsey 数R（C4,C4,Wn）由定理D,我们知道:当n≥6时,定理A中R（C4,K1,n）的上界也是R（C4,Wn）的上界.一个自然的问题:定理4中R（C4,C4,K1,n）的上界也是R（C4,G4,Wn）的上界吗?在第4章,我们关注三色Ramsey数R（C4,C4,K1,n）和R（C4,C4,Wn）的之间关系,获得关于三色Ramsey数R（C4,C4,Wn）的一个上界.取k = 1,2,我们将分别得到定理A和定理4.也就是说,定理8推广了定理A和定理4.进一步,对每个充分大的n,结合代数方法和概率方法,我们构造了一个阶数相当大的（k+1）-边染色完全图使得对任意1 ≤i≤k它不包含i-色C4也不包含（k+1）-色K1,n.利用这些（k+1）-边染色完全图,我们获得（k+1）-色Ramsey数R（C4,…,C4,K1,n）的一个通常下界:定理9.如果n充分大,则（?）>n+「k（?）-6knα/2」,其中α为一个小于11/20的常数.取k= 1,我们就得到定理C.也就是说,定理9推广了定理C.最后,我们关注（kk+1）-色Ramsey数R（C4,…,C4,K1,n）和R（C4,…,C4,Wn）之间关系.如果k=1,定理D叙述:对所有n≥6,R（C4,Wn）=R（C4,K1,n）.对于一般的k,由于K1,n是Wn的一个生成子图,显然,R（C4,…,C4,K1,n）至多为R（C4,,C4,Wn）.自然地,我们要问:是否存在整数N,使得当n≥N时R（C4,,C4,K1,n）和R（C4,,C4）相等?答案是肯定的,事实上,在定理8和9基础上,我们可以证明:定理10.对充分大的n,（?）