论文部分内容阅读
Ramsey理论是一个非常重要的数学分支，其重要性在于它揭示了一个重要哲理：完全无序是不可能的!Ramsey数R(G1，G2)是满足以下性质的最小的整数n：对任意一个有n个顶点的图G，或者G1是G的子图，或者G2是G的补图的子图。自从Ramsey理论诞生以来，经历了70余年的研究历程，进展相当缓慢。至今为止，只有9个经典Ramsey数被确定下来。在该领域中，有许多悬而未解的问题。正因为此，Ramsey理论一直是数学界研究的热点问题，并且它的研究成果已经广泛地应用于计算机理论等其他学科领域。
圈—完全图型Ramsey数首先由P． Erd(o)s等人开始研究的[Journal of GraphTheory 2(1978)53-64]。在该文中，Erd(o)s等提出了如下问题：对于给定的n，确定最小整数f(n)使得对任意的m，当m≥f(n)时总有R(Cm，Kn)=(m-1)(n-1)+1，并猜想R(Cm，Kn)=(m-1)(n-1)+1当m≥n且(m，n)≠(3，3)时成立。该猜想已被证实当3≤n≤7时成立。对于m≤n-1时R(Cm，Kn)的值，目前已知的只有14个，其中还包括6个经典Ramsey数。本文将证明R(C6，K8)=36。这是目前已知在m≤n-1时R(Cm，Kn)的第15个值。这个结果同时也说明了f(8)≤6，结合其他结果可以知道5≤f(8)≤6。
全文共分三章。第一章介绍了本文涉及到的一些图论方面的基本概念及记号，以及关于Ramsey理论和ramsey数的一些背景知识及重要结果。第二章着重介绍了圈—完全图型Ramsey数并给出了本文主要结果的证明。第三章提出了几个更深入的问题。