Lagrangians Of Hypergraphs

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal prob-lems. It has also been extensively used in domains such as optimization and pattern recognition.Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph in1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we provide some of Motzkin-Straus type reults for non-uniform hypergraphs and uniform hypergraphs. These results for3-graphs and r-graphs support a pair of conjectures introduced by Peng and Zhao (2012).Turan problem is the core of extremal graph theory. Using the Lagrangian, we obtain a weaker version of Turan type theorem for a class of3-uniform hypergraphs.In most applications, we need an upper bound for the Lagrangians of hypergraphs. 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. Talbot provided some evidence for Frankl and Furedi’s conjecture in2002. In this paper, we prove 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-uniform graphs on t vertices with m edges when m=(tr)-p where0≤p<t-r under some conditions. As an implication, we also prove that Frankl and Furedi’s conjecture holds for3-uniform graphs with m=(t3)-p edges where0≤p≤4. Seeing that Motzkin-Straus theorem cannot be generalized to hypergraphs, we de-velop a homogeneous multilinear function based on the structure of hypergraphs andtheir complements. Its maximum value (called generalized Lagranian) generalizes theLagrangian. Specifically, we establish a connection between the clique number and thegeneralized Lagrangians of3-uniform graphs, which supports three conjectures posedin this paper. We also explore some connections between the clique number and thegeneralized Lagrangians of some {2,r}-graphs({1,2,r}-graphs).