关于图size Ramsey数若干问题的研究

来源 :同济大学理学部数学系 同济大学 | 被引量 : 0次 | 上传用户:liongliong583
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论是一门年轻而又发展极为迅速的学科,现代图论最显著的特征是许多现代方法的出现,如代数、几何、概率、分析方法等。图的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数
其他文献
本文主要是基于全变差的方法对图像进行处理。首先针对空间域图像的修复问题,本文提出了一种基于TV模型的自适应的快速修复算法。该算法根据图像自身的特点设置邻域相关信息
在这篇论义中,我们主要考虑两部分内容:一是讨论分式布朗运动和双分式布朗运动的各种类型的局部时间题:二是研究由分式噪声驱动的高阶随机热方程的性质,其中包括Cahn-Hilliarld型
学位
作为运筹学和管理科学研究的一个分支,排队理论(存储理论)经历了一百多年的发展.扩散逼近作为处理复杂系统的一种有效的方法,能够帮助我们得到一些近似结果.这种方法在排队理论中
学位
在二十一世纪,有关生物数学的研究显得越发重要,生物数学与其他学科的交叉领域将成为主要的研究对象.与确定性生物数学模型相比较,在现实生活中种群生态系统经常会遇到环境白噪声
自20世纪70年代开始,由于鞅论自身拥有丰富的理论和较高的应用价值,鞅论逐渐成为很多学者的研究中心。在其发展过程中,鞅论和Banach空间理论,泛函分析理论相互结合,逐渐发展成为一
灰色系统理论的研究对象是“少数据、贫信息”的不确定性问题,主要通过对部分已知信息的挖掘和开发,获取有用的信息,对系统的运行规律进行正确地描述和有效地控制。在灰色系统理
矩阵几何是华罗庚于上世纪40年代开创的一个数学研究方向,有6类矩阵群上的矩阵几何先后被研究,即长方矩阵几何、对称矩阵几何、交错矩阵几何、Hermitian矩阵几何、斜Hermitian