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

摘要

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 Turan's theorem using the connection.,The connection of Lagrangians and Turan densities can be also used to prove the fundamental theorem of Erdos-Stone-Simonovits on Turan densities of graphs. Very recently, the study of Turan 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 Turan 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 Erdos-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). (C) 2015 Elsevier B.V. All rights reserved.