← All problems

Frankl–Füredi conjecture on hypergraph Lagrangians

14 years old · documented by

For a set XX, let X(r)X^{(r)} denote the family of all subsets of XX of size rr. An rr-graph is a family G⊆N(r)G\subseteq\mathbb{N}^{(r)}, and its Lagrangian is

λ(G):=max⁡{∑e∈E(G)∏x∈ew(x):w(x)≥0 for all x∈N, ∑x∈Nw(x)=1}.\lambda(G):=\max\left\{\sum_{e\in E(G)}\prod_{x\in e}w(x): w(x)\geq 0\text{ for all }x\in\mathbb{N},\ \sum_{x\in\mathbb{N}}w(x)=1\right\}.

Let C(m,r)\mathcal{C}(m,r) be the family consisting of the first mm members of the colexicographic order on N(r)\mathbb{N}^{(r)}, where A<BA<B if and only if ∑i∈A2i<∑i∈B2i\sum_{i\in A}2^i<\sum_{i\in B}2^i.

Frankl–Füredi conjecture. If GG is an rr-graph with mm edges, then

λ(G)≤λ(C(m,r)).\lambda(G)\leq\lambda(\mathcal{C}(m,r)).

This conjecture asks which rr-graph with a prescribed number of edges maximizes the Lagrangian. It is a central problem in extremal combinatorics and is false in general, as indicated by the paper's title; the conjecture is therefore refuted, although particular cases may still hold.

References

12 papers in this index state this conjecture (2011–2018). The statement above is taken from the most recent of them; the others are arXiv:1806.11259, arXiv:1806.10846, arXiv:1501.01913, arXiv:1405.2855, arXiv:1312.3034, arXiv:1311.1409, arXiv:1311.1062, arXiv:1212.2795, arXiv:1211.7057, arXiv:1211.6508, arXiv:1110.1623.

Source: Vytautas Gruslys, Shoham Letzter and Natasha Morrison, “Hypergraph Lagrangians I: the Frankl-Füredi conjecture is false”, arXiv:1807.00793 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.