论文部分内容阅读
图论是一门年轻而又发展极为迅速的学科,现代图论最显著的特征是许多现代方法的出现,如代数、几何、概率、分析方法等。图的Ramsey理论作为图论的一个极具吸引力的研究分支,同时也是组合数学中一个庞大而丰富的领域,它起源于1930年英国数学家Frank Ramsey的文章《On a Problem of FormalLogic》[73]。在这篇文章里Frank Ramsey讨论了在某种条件下无论对集合如何划分都能够产生人们预期想要得到的子集的现象。后来人们在他工作的基础上不断扩充,确定了Ramsey理论的研究内容为:在某种条件下,无论对一个大系统(结构)如何进行分割,总是能够得到人们预期想要得到的子系统(结构),这种大系统的最小阶便称之为Ramsey数。这里的系统即由相互关联的事物所组成,要研究这种系统可以通过很多种方式进行探讨,其中“图”是表达这种系统的最佳工具,所以图论理所当然地成为研究Ramsey理论的一个最重要的表达工具。
自从Ramsey理论诞生以来,经历了70余年的研究历程,进展相当缓慢。在Frank Ramsey发表论文25年之后,人们才得到第一个非平凡的Ramsey结果[59],在它的研究领域中,悬而未解的问题及猜想相当多,因此Ramsey理论成为当今图论工作者的研究热点之一。人们引入了各种标尺来刻划它,产生了很多研究分支,如一般的Ramsey数,二部Ramsey数,Size Ramsey数等等;并且它的研究成果已经广泛地应用于集合论、几何、数论、逻辑学、计算机理论研究等多个领域,见文献[17,77]。
本文第一章和第二章分别介绍了这个领域的相关定义、研究背景、研究方法、研究进展和研究分支。第三章中首先对二部Ramsey数作进一步的研究和推广,提出了Size Bipartite Ramsey数的概念,
(br)(B1,B2)=min{e(B):B是二部图,且B→(B1,B2)},
并将它和Bipartite Ramsey数进行比较,推广了Erd(o)s和Rousseau[24]关于对称二部图的“计数引理”,得到结果如下:
定理0.0.1.设n≥m≥1是两个整数,二部图B有q条边,q≥m2,则B包含至多个子图Km,n。
特别地,B包含至多个子图Kn,n。
针对星图、对称二部图、一般的完全二部图,本章给出了它们Size BipartiteRamsey数的上下界。
定理0.0.2.设m和n是两个正整数,则
定理0.0.3.对固定的m≥1和充分大的n,有
定理0.0.4.对充分大的n,有
第四章中通过计算边数确定的母图中子图为完全m-部图Km(n)的个数,给出了Km(n)的size Ramsey数[25]的上下界。主要结论有:
定理0.0.5.设自然数n≥2,一个含有q条边的m-部图中至多可以诱导出A(m,n,q)个完全m-部图Km(n)作为子图,其中
定理0.0.6.设m、n是两个整数,m≥2固定,n→∞,那么完全m-部图Km(n)的size Ramsey数