涉及四圈的多色Ramsey数

发布时间：2018-03-19 08:33

  本文选题：Ramsey数　切入点：多色Ramsey数　出处：《南京大学》2017年博士论文　论文类型：学位论文

【摘要】：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,K1n+(?)-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,(?)
[Abstract]:The Ramsey theorem is a basic result, it refers to the combination of Mathematics: the order of sufficiently large edge colored complete graphs must have you need monochromatic group. First version of this result by the British mathematician and philosopher F.P.Ramsey in 1930. This was the beginning of a given branch of combinatorial mathematics, now known as the Ramsey.Ramsey narrative theory the theory is: complete disorder is not possible in.Ramsey theory often put forward in such a way that the element of a structure to achieve much when you can guarantee a certain property? Ramsey theory has been a hot research topic in combinatorial mathematics. Besides combinatorics, Ramsey theory in the development of many other mathematical branches in play an important role in involving algebra, set theory, logic, probability and geometry and so on. The researchers including Wolf L.Lovasz, Fields P.Erdos award winner, Tao Zhe prize winner T.Gowers Abel prize, Hennessy 涓，

本文编号：1633480