Hypergraph Lagrangians I: the Frankl-Füredi conjecture is false

Abstract

An old and well-known conjecture of Frankl and Füredi states that the Lagrangian of an $r$-uniform hypergraph with $m$ edges is maximised by an initial segment of colex. In this paper we disprove this conjecture by finding an infinite family of counterexamples for all $r\ge 4$. We also show that, for sufficiently large $t\in \mathbb{N}$, the conjecture is true in the range $\left(\genfrac{}{}{0ex}{}{t}{r}\right)\le m\le \left(\genfrac{}{}{0ex}{}{t+1}{r}\right)-\left(\genfrac{}{}{0ex}{}{t-1}{r-2}\right)$.

We split our original paper (arXiv:1807.00793v2) into two parts. This first part consists of 24 pages, including a one-page appendix. The second part appears in a new submission (arXiv:1907.09797)