论文部分内容阅读
Ramsey理论研究的是在一个充分大的系统中某些事先给定的子系统的存在性.Ramsey数是Ramsey理论中的一个重要分支，它研究的是系统规模的一种临界状态，即一个大的系统究竟要大到什么程度才会包含某个给定的子系统.对于给定的两个图G1和G2，图Ramsey数R(G1，G2)就是最小的正整数n，使得任一n阶图，要么G含有G1，要么图G的补图G含有G2.一般说来，要求出图Ramsey数的准确值是非常困难的。对于圈-轮型Ramsey数R(Cn，Wm)，Surahmat等人在[The Ramsey numbers oflarge cycles versus wheels，Discrete Mathematics，306(2006)，3334-3337]一文中证明：当m是偶数且n≥5m/2-1时，R(Cn，Wm)=2n-1；同时他们猜想：当m是奇数，n≥m≥3且(n，m)≠(3，3)时，R(Cn，Wm)=3n-2.对于较小的m和个别n的值，已经确定了具体的值。对于一般的m，n，尚不知道该猜想是否成立。
本文将要证明猜想对所有的n≥20都成立，亦即：对所有的奇数m≥3，n≥m且n≥20，我们有R(Cn，Wm)=3n-2.论文的主要结论已发表在European Journal of Combinatorics[详见http：//www.elsevier.com/locate/ejc]。全文共分三章：第一章介绍了图论的若干基本概念，Ramsey理论的历史，一些重要方法和定理。第二章主要介绍图Ramsey数的若干结果及其最新进展。第三章中我们将证明Surahmat等人有关圈对偶阶数轮Ramsey数的猜想。