pith. machine review for the scientific record. sign in

arxiv: 1312.7529 · v1 · pith:BEXREC5Vnew · submitted 2013-12-29 · 🧮 math.CO

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

classification 🧮 math.CO
keywords hypergraphsuniformconnectioncliqueconjecturelagrangianmotzkinnumber
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.