An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications
An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications
复制标题
DOI：
10.1016/j.dam.2015.06.037
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
Yuejian Peng;Hao Peng;Qingsong Tang;Cheng Zhao
中科院分区：
文献类型：
--
作者：
Yuejian Peng;Hao Peng;Qingsong Tang;Cheng Zhao
1965年，Motzkin和Straus建立了极大团的阶数与图的拉格朗日量之间的显著联系，并利用这种联系提供了Turán定理的新证明。拉格朗日密度与Turán密度的联系也可用来证明Erdős-Stone-Simonovits关于Turán图密度的基本定理。最近，对Turán非均匀超图密度的研究是由极端偏置问题推动的，由Johnston和Lu提出。在本文中，我们尝试探索拉格朗日方法在确定非均匀超图Turán密度中的应用。首先给出了非均匀超图的拉格朗日的定义，然后将莫兹金-斯特劳斯定理推广到边包含1个顶点或2个顶点的非均匀超图。应用它，我们给出了Erdős-Stone-Simonovits定理在边包含1或2个顶点的非一致超图上的推广。我们的方法遵循Keevash的论文Keevash（2011）中的方法。
In 1965, Motzkin and Straus established a remarkable connection between the order of a maximum clique and the Lagrangian of a graph and provided a new proof of Turán’s theorem using the connection. The connection of Lagrangians and Turán densities can be also used to prove the fundamental theorem of Erdős–Stone–Simonovits on Turán densities of graphs. Very recently, the study of Turán densities of non-uniform hypergraphs has been motivated by extremal poset problems and suggested by Johnston and Lu. In this paper, we attempt to explore the applications of Lagrangian method in determining Turán densities of non-uniform hypergraphs. We first give a definition of the Lagrangian of a non-uniform hypergraph, then give an extension of the Motzkin–Straus theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Applying it, we give an extension of the Erdős–Stone–Simonovits theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Our approach follows from the approach in Keevash’s paper Keevash (2011).