Lagrangians of hypergraphs: The Frankl-Füredi conjecture holds almost everywhere
| Autor: | Mykhaylo Tyomkyn |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematics::Combinatorics
Conjecture Mathematics::Number Theory General Mathematics 010102 general mathematics Order (ring theory) 0102 computer and information sciences 01 natural sciences Combinatorics symbols.namesake 010201 computation theory & mathematics symbols Almost everywhere 0101 mathematics Lagrangian Initial segment Mathematics |
| Zdroj: | Journal of the London Mathematical Society. 96:584-600 |
| ISSN: | 0024-6107 |
| DOI: | 10.1112/jlms.12082 |
| Popis: | Frankl and Furedi 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=\binom{t}{r}$ their conjecture states that every $H\subseteq \mathbb{N}^{(r)}$ of size $\binom{t}{r}$ 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-Furedi conjecture holds whenever $\binom{t-1}{r} \leq m \leq \binom{t}{r}- \gamma_r t^{r-2}$ for a constant $\gamma_r>0$, thereby verifying it for `most' $m\in \mathbb{N}$. Furthermore, for $r=3$ we make an improvement on the results of Talbot~\cite{Tb} and Tang, Peng, Zhang and Zhao~\cite{TPZZ}. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text