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

Abstract

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 = t r their conjecture states that the maximum is attained on the clique of order t. We prove the latter 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 − 1 r ⩽ m ⩽ t r − γ r t r − 2 for a constant γ r > 0 , thereby verifying it for ‘most’ m ∈ N . Furthermore, for r = 3 we make an improvement on the results of Talbot and of Tang, Peng, Zhang and Zhao.