Back to Search
Start Over
Hypergraph Lagrangians I: the Frankl-F\'uredi conjecture is false
- Publication Year :
- 2018
-
Abstract
- An old and well-known conjecture of Frankl and F\"{u}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 $\binom{t}{r} \le m \le \binom{t+1}{r} - \binom{t-1}{r-2}$.<br />Comment: 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)
- Subjects :
- Mathematics - Combinatorics
05C65, 05C35
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1807.00793
- Document Type :
- Working Paper