An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications

详细信息    查看全文

• 作者：Yuejian Peng^a ; ^{ypeng1@hnu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Hao Peng^a ; ^{hpeng@hnu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Qingsong Tang^b ; ^{t_qsong@sina.com.cn" class="auth_mail" title="E-mail the corresponding author} ; Cheng Zhao^c ; ^{cheng.zhao@indstate.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Lagrangians of hypergraphs ; Tur&aacute ; n density ; Extremal problems
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 February 2016
• 年：2016
• 卷：200
• 期：Complete
• 页码：170-175
• 全文大小：368 K

文摘

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).