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

Mykhaylo Tyomkyn

doi:10.1112/jlms.12082

paper

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

arXiv:1703.04273 · doi:10.1112/jlms.12082

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 = (r t)$ their conjecture states that every $H \subseteq N^{(r)}$ of size $(r t)$ satisfies \begin{align*} \max \{\sum_{A \in H}\prod_{i\in A} y_i \ \colon \ y_1,y_2,\ldots \geq 0; \sum_{i\in \mathbb{N}} y_i=1 \}&\leq \frac{1}{t^r}\binom{t}{r}. \end{align*} We prove the above statement for all $r \geq 4$ and large values of $t$ (the case $r = 3$ was settled by Talbot in 2002). More generally, we show for any $r \geq 4$ that the Frankl-Füredi conjecture holds whenever $(r t - 1) \leq m \leq (r t) - γ_{r} t^{r - 2}$ for a constant $γ_{r} > 0$ , thereby verifying it for `most' $m \in N$ . Furthermore, for $r = 3$ we make an improvement on the results of Talbot~\cite{Tb} and Tang, Peng, Zhang and Zhao~\cite{TPZZ}.

14 pages

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

Abstract

Cited by in corpus (6)