Connection between the clique number and the Lagrangian of $3$-uniform hypergraphs

Qingsong Tang, Yuejian Peng, Xiangde Zhang, Cheng Zhao

Published 2013-12-29Version 1

There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus in 1965. It is useful in practice if similar results hold for hypergraphs. However the obvious generalization of Motzkin and Straus' result to hypergraphs is false. Frankl and F\"{u}redi conjectured that the $r$-uniform hypergraph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${\mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-uniform hypergraphs with $m$ edges. For $r=2$, Motzkin and Straus' theorem confirms this conjecture. For $r=3$, it is shown by Talbot that this conjecture is true when $m$ is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for $3$-uniform hypergraphs. As an application of this connection, we confirm that Frankl and F\"{u}redi's conjecture holds for bigger ranges of $m$ when $r$=3. We also obtain two weaker versions of Tur\'{a}n type theorem for left-compressed $3$-uniform hypergraphs.