Lagrangians of hypergraphs: The Frankl-Füredi conjecture holds almost everywhere

Frankl and Füredi conjectured in 1989 that the maximum Lagrangian of all r-uniform hypergraphs of fixed size m is realised by the initial segment of the colexicographic order. In particular, in the principal case m=(tr) that every H⊆N(r)of size (tr) satisfies max⁡{∑A∈H∏i∈Ayi:y1,y2,…≥0;∑i∈Nyi=1}≤[Formula presented](tr). We prove the above statement for all r≥4 and large values of t (the case r = 3 was settled by Talbot in 2002). More generally, we show for any r≥4 that the Frankl-Füredi conjecture holds whenever (t−1r)≤m≤(tr)−γrtr−2for a constant γr>0, thereby verifying it for ‘most’ m∈N. Furthermore, for r = 3 we make an improvement on the results of Talbot [Talbot, J., Lagrangians of hypergraphs Combin., Probab. Comput 11 (2002), 199–216] and Tang, Peng, Zhang and Zhao [Tang, Q., Y. Peng, X. Zhang and C. Zhao, Connection between the clique number and the Lagrangian of 3-uniform hypergraphs, Optimization Letters (2016) 10(4), 685–697]