On hypergraph Lagrangians

Abstract

It is conjectured by Frankl and Füredi 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 in \cite{FF}. Motzkin and Straus' theorem confirms this conjecture when $r=2$. For $r=3$, it is shown by Talbot in \cite{T} 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 $r$-uniform hypergraphs. As an implication of this connection, we prove 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 graphs with $t$ vertices and $m$ edges satisfying $\left(\genfrac{}{}{0ex}{}{t-1}{r}\right)\le m\le \left(\genfrac{}{}{0ex}{}{t-1}{r}\right)+\left(\genfrac{}{}{0ex}{}{t-2}{r-1}\right)-[(2r-6)\times 2^{r-1}+2^{r-3}+(r-4)(2r-7)-1]((\genfrac{}{}{0ex}{}{t-2}{r-2})-1)$ for $r\ge 4.$

10 pages. arXiv admin note: substantial text overlap with arXiv:1312.7529, arXiv:1211.7057, arXiv:1211.6508, arXiv:1311.1409