论文部分内容阅读
Tur′an问题是极值组合中的重要问题。对图的情形, Erd?os-Stone-Simonovits的经典结果给出了非二部图Tur′an数的渐近值。但对超图,已知的结果相对较少。本文得到了几类超图的Tur′an数：Hefetz和Keevash[29]中给出了关于3一致超图中长度为2的匹配的扩张的Tur′an数,并提出了r一致超图中长度为2的匹配的扩张的Tur′an数猜想,本文证明了这一猜想对于4一致超图成立。本文也分别给出了3一致超图中长度为3、长度为4的线性路及长度为2的线性路与任意长度匹配的不交并的拉格朗日密度及这些3一致超图的扩张的Tur′an数,并证明了极图的唯一性。 拉格朗日方法是解决Tur′an问题的重要工具。19世纪80年代, Sidorenko证明了r一致超图F的Tur′an密度,记作π(F),是r!乘以所有F-hom-free r一致超图的拉格朗日的上界。在将超图的拉格朗日方法应用到求超图F的Tur′an密度中时,有两个关键问题,一是对‘dense’ F-hom-free的刻画,二是对超图的拉格朗日的估算。当r=2时, Motzkin-Straus证明了,一个图是dense当且仅当它为完全图。然而,当r≥3时,由于确定r一致超图的拉格朗日非常困难,因此刻画dense r一致超图更加困难。我们给出了一些拥有给定结构的3一致超图成为dense的充要或者充分条件。例如,若G是一个顶点集为[t]、边数为m的3一致超图,且含有[t?1](3)作为子图,则G为dense当且仅当m≥(t?13)+(t?22)+1.我们同样给出一些含有大完全子图的减去一条或者两条边的3一致超图是否dense的充分条件。 1965年, Motzkin-Straus建立了简单图的拉格朗日与其最大完全子图的关系。然而,图的拉格朗日与其最大完全子图之间的关系不能推广到超图。2009年, Rota Bul`o-Pelillo定义了一个由给定的r一致超图决定的、度为r的齐次多项式,且给出了这个齐次多项式的最优解与该给定的r一致超图的最大完全子图之间的关系。我们确定了一个非齐次多项式的全局（局部）最优解与该给定的非一致超图的最大（极大）完全子图之间的关系。这个联系可以用来得到{r?1, r}-型完全超图的Tur′an密度的非平凡界。