论文部分内容阅读
在对图或超图的极值问题研究中，图或超图的拉格朗日函数是一个非常有效的工具.1965年Motzkin和Straus提出图的拉格朗日函数的概念，将图的最大团问题与图的拉格朗日函数联系起来，并给出了Turán定理的一种新证明.拉格朗日函数与Turán密度的联系也可用于给出Erd(o)s-Stone-Simonovits定理的另一证明.这一联系引起了人们对拉格朗日函数的极大兴趣，在组合、优化、图谱理论、计算机图像处理和模式识别等理论中陆续出现了一些以图的拉格朗日函数为工具的结果. 然而，对超图的拉格朗日的估算却远远难于图的拉格朗日.1982年，Sós和Straus将拉格朗日的概念推广到一致超图中，而Motzkin-Straus关于图的拉格朗日的结果却并不能直接推广到超图，即一个超图的拉格朗日并不一定等于它的最大团的拉格朗日，事实上，有很多超图的拉格朗日不等于它的任何子图的拉格朗日.如果能在超图中得到类似Motzkin-Straus型的结果，必将带动一些极值问题的发展.近年来，Bulò和Pelillo给出了超图的最大团的另一种连续刻画，在此基础上得到了Motzkin-Straus型的结果在r-图中的一种推广.同时，对偏序集极值问题的研究推动了非一致超图的Turán密度的研究，Johston和Lu把Turán密度的概念推广到了非一致超图中.在本文中，我们致力于探索拉格朗日方法在非一致超图的Turán问题中的应用.我们对于非一致超图给出了拉格朗日函数的一种定义，得到了{1，2}-图的Motzkin-Straus型定理，并利用拉格朗日方法证明了{1，2}-图的Erd(o)s-Stone-Simonovits型定理.我们还对一般的超图给出了广义拉格朗日函数的一种定义，可以与一致超图的拉格朗日函数定义统一起来，在此基础上得到了{1，r}-图的Motzkin-Straus型结果. 关于一致超图的拉格朗日，Frankl和Füredi于1989年提出了一个猜想:在所有边数为m的r-图中，以colex序最小的m个元素为边的r-图具有最大的拉格朗日.Motzkin-Straus定理表明当r=2时Frankl-Füredi猜想是成立的.对r≥3的情况，Frankl-Füredi猜想的验证极其困难.近年来，Talbot、Tang、Peng、Zhao等得到了r=3的部分情况以及在某些限制条件下Frankl-Füredi猜想的部分结果.我们在本文中提出支撑Frankl-Füredi猜想的一个猜想，并证明对r=4的部分情形猜想成立.