The Motzkin-Straus Theorem And Frankl-F(u|")redi’s Conjecture Of Hypergraphs

The Lagrangian of a graph (hypergraph) has been a very useful tool in ex-tremal graph (hypergraph) theory. In 1965, Motzkin and Straus established a re-markable connection between the order of a maximum clique and the Lagrangian of a graph and provided a new proof of Turan’s theorem using this connection. The connection of Lagrangians and Turan densities can be also used to prove the fun-damental theorem of Erdos-Stone-Simonovits on Turan densities of graphs. This type of connection aroused interests in the study of Lagrangians, more and more applications of Lagrangians can be found in optimization, graph spectral theory, computer image processing and pattern recognition.However, estimating Lagrangians of hypergraphs is much more harder. In 1982, Sos and Straus generalized the Lagrangian of hypergraphs, but the obvious generalization of Motzkin and Straus’result to hypergraphs is false, i.e., the La-grangian of a hypergraph is not always the same as the Lagrangian of its maximum cliques. In fact, there are many examples of hypergraphs that do not achieve their Lagrangian on any proper subhypergraph. A Motzkin and Straus type result will provide applications in hypergraph extremal problems. Rencently, Bulo and Pelil-lo generalized the Motzkin and Straus’theorem to uniform hypergraphs in some way by using a continuous characterization of maximal cliques other than La-grangians of hypergraphs. Meanwhile, the study of Turan densities of non-uniform hypergraphs have been motivated by the study of extremal poset problems. A generalization of the concept of Turan density to a non-uniform hypergraph was given by Johnston and Lu. In this paper, we attempt to explore the application-s of Lagrangian method in the Turan problem 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{1,2}-graphs. Applying it, we give an extension of the Erdos-Stone-Simonovits theorem to{1,2}-graphs. Also, we define a generalized Lagrangian of a hypergraph which is consistent with the La-grangian of a uniform hypergraph. Applying generalized Lagrangian, we give a Motzkin-Straus type result for{l,r}-graphs.In 1989, Frankl and Furedi conjectured that the r-graph with m edges formed by taking the first m sets in the colex ordering of N(r) has the largest Lagrangian of all r-graphs with m edges. This conjecture is true when r= 2 by the Motzkin and Straus’theorem. For the cases r> 3, it turns out this natural conjecture seems to be very challenging to verify. Talbot, Tang, Peng, Zhao, et al. made some progress on verifying this conjecture under some conditions. In this paper, we introduce a conjecture which supports Frankl and Fiiredi’s conjecture and prove this conjecture holds for 4-uniform hypergraphs under some conditions.