论文部分内容阅读
自1928年Ramsey提出了著名的Ramsey定理之后,引起了对Ramsey类型问题的广泛研究.Ramsey数是其中一个非常重要的问题,但是Ramsey数的研究进展非常缓慢。人们应用各种各样的方法也只得到了Ramsey数有限的几个值.所以Ramsey数成为了组合数学、离散数学、图论、算法研究领域的著名难题和热门课题.学者们都试图找到求Ramsey数的一个通用方法,而不是一个一个的求出Ramsey数的值,但是到目前为止,仍然没有找到一种合理的方法来求出Ramsey的所有值.本文一共采用了三种方法来求不同类型的Ramsey数的上界.第一种方法是：抽屉原理.利用抽屉原理证明了Erdos和Szekeres(1935)以及Greenwood和Gleason(1955)提出的Ramsey数定理及其推广,同时由抽屉原理还得到了两类Ramsey的上界公式：Rn-1(k;k+1)≤n(Rn(k)-1)+2与Rn-1(k;l+1)≤n(Rn-1(k;l)-1)+2.第二种方法是：将整数集合的S-F-S分拆进行推广,并对其进行了仔细的研究,然后说明其在求Ramsey数R(3,q)上界中的作用.第三种方法是：循环图.应用循环图求经典多色Ramsey数Rn-1(3；q)的上、下界.首先提出了计算Ramsey数Rn-1(3；q)下界的一种方法,然后根据根据这种方法得到了计算Ramsey数Rn-1(3；q)上界的一种新方法,并利用所提出的方法得到了R(3,3,4)=30.