论文部分内容阅读
在组合数学史上,有一段丰富的研究历史是关于超图的图拉格朗日及其应用的。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猜想提供了更多的依据。