3—致超图的拉格朗日和最大团之间的关系的研究

来源 :湖南大学 | 被引量 : 0次 | 上传用户:dffg21f
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在组合数学史上,有一段丰富的研究历史是关于超图的图拉格朗日及其应用的。1941年,Turán回答了下面的问题:一个有n个顶点的图,它不包含阶为t(t给定)的完全子图的最大边数是多少?这就是著名的Turán定理。1965年,Motzkin和Straus在一个图的图拉格朗日和其最大团的阶之间建立了一个显著的联系。它也提供了一个新的证明Turán定理的方法。这个新的证明方法激起了对r一致超图的图拉格朗日的研究兴趣。  在很多应用中,需要用到超图的图拉格朗日的一个上限。在估计一些超图的Turán密度的过程中,Frankl和Füredi提出了下面的问题:给定r≥3,m∈N,一个有m条边的r图的图拉格朗日最大能有多大?他们猜想在所有的有m条边的r图中,Cr,m(由N的r子集的集合的colex序中的前m个集合所形成的m条边的r图)有最大的图拉格朗日,也就是说,r-致超图G的图拉格朗日小于等于Cr,m的图拉格朗日。本文证明了Frankl和Füredi的猜想在某些条件下成立。  Moztkin和Straus的结果暗含着以上猜想对于r=2是对的。对于r≥3,这个猜想非常具有挑战性。Talbot首先在某些情况下证实了这个猜想。随后,Peng,Zhao,Tang等在更多的情况下证实了这个猜想。  Motzkin和Straus的结果不能直接推广到r一致超图,所以Peng和Zhao试图探索当边数在一定范围内,一个超图的图拉格朗日和超图的最大团数之间的关系,并提出了与之相关的两个猜想。这两个猜想细化了当边数在这个范围内的Frankl-Füredi猜想。他们还证明了猜想中的一个关于3一致超图的,即当边数在某个范围内时,3一致超图的图拉格朗日是它的最大团的图拉格朗日。本文证明了当边数在那个范围内时,如果一个3一致超图不包含这样的阶的一个团,那么在某些条件下,这个3一致超图的图拉格朗日严格地小于这样的阶的一个完全3一致超图的图拉格朗日。这也为以上猜测提供了一些依据。  基于已有的结果,本文继续对3一致超图G的图拉格朗日与C3,m的图拉格朗日之间的关系进行研究。由于直接得出它们之间的联系比较困难,所以附加了一些条件,如在满足G的边与C3,m的边的对称差的个数小于等于某个具体数值的情况下,或者在满足边数等于某个与t有关的式子的情况下,来探讨它们之间的联系。在满足左压缩的前提下,灵活替换,证明出了3一致超图的图拉格朗日小于等于C3,m的图拉格朗日,改进了研究结果。  接着研究了在一些条件下,3一致超图的图拉格朗日和最大团之间的关系。本文是在m在某个范围内,G不包含t-1阶团,且同时包含顶点t-1和t的边数不大于某个具体数值的情况下研究的。通过运用迭代法和替换法,得出了G的图拉格朗日严格地小于t-1阶的完全3图的图拉格朗日。  本文继续探索了3一致超图的图拉格朗日和最大团之间的关系。在研究的过程中加入了一些条件,如从t-1阶的团中移去了指定的p条边,t大于等于一个p的多项式,获得了G的图拉格朗日严格地小于t-1阶的完全3图的图拉格朗日。这里由于p的任意性,所以结论有较好的一般性,以及较广的覆盖面。  基于已有的研究成果,只要证明了左压缩3一致超图,也就证明了3一致超图。这大大降低了计算复杂度。在此基础上,令G是在顶点集[t]上有m条边的一个左压缩3图,如果从t-1阶的团中移去p条边,t大于等于p的一个一次多项式,那么G的图拉格朗日严格地小于t-1阶的完全3图的图拉格朗日。这在计算复杂度和一般性上改进了以往的研究结果,并且部分地验证了Peng-Zhao提出的猜想。  总之,通过对具体情况的研究,起初的目的是证明Frankl-Füredi猜想。但是目前的方法有一定的局限性。由于有很多种情况,每种情况的替换方法又不一样,所以总结出来比较困难。然而,如果可以克服一些困难,那么本文的方法可能得到推广,Frankl-Füredi猜想也许能够得到证明。本文为Frankl-Füredi猜想提供了更多的依据。
其他文献
图像修复是图像处理中的重要组成部分。2000年M.Bertalmio,G.Sapiro,V.Cadelles和C.Balle.ster联合发表的Image Inpainting,首次把图像的Inpainting,即图像的对残缺部分的填
Ringel首先引入了单点扩张代数的概念[1].作为推广,Auslander,Reiten和Smalo引入并研究了二级三角矩阵代数及其模范畴[2].史美华将二级三角矩阵环的概念进一步推广,引入了三级三角
第一章中,我们回顾一下图C*-代数和交叉乘积的历史和发展过程,并简单介绍一下论文的主要结果。   第二章中,我们介绍一下关于Hilbert C*-模,C*-对应,OX和交叉乘积的一些基本概
学位
探讨了经济新闻在报道流程中大众化术语“变译”的范式,分析了网络时代里信息技术在辅助其新闻专业术语“变译”方面的功能、使用方法和技巧,从而让更广大的读者群能更容易、
在当前社会形势下,社会对于高技术专业人才的需求量日益加大,但是很多职业院校毕业生却找不到工作。这种情况的根本原因在于职业院校学生的实践技能相对不高的缘故,针对于此,
Breeding high-yielding and nutrient-efficient cultivars is one strategy to simultaneously resolve the problems of food security,resource shortage,and environmen
小波分析是新兴的数学分支,它作为一种新的分析方法,是调和分析几十年来工作的结晶。现在,小波分析已成为科学研究和工程技术应用中涉及面极其广泛的一个热门话题。在数学领
随着网络技术的不断发展,网络资源呈爆炸性增长。如何在网络中最快、最准地找到有效信息已经成为信息检索技术面临的新的难题。面对这一挑战,数据挖掘和知识发现技术应运而生
本文在纳什讨价还价模型和鲁宾斯坦讨价还价模型的基础上,讨论了讨价还价拓展模型及其应用.首先,介绍了纳什讨价还价模型和鲁宾斯坦讨价还价模型及其均衡解.其次,文章针对讨