Erdős–Sauer conjecture: decompose every $r$-uniform hypergraph into few cliques and single edges (Erdős #719)
Statement
Fix $r\geq 2$. Write $K_r^r$ for a single $r$-edge (the complete $r$-uniform hypergraph on $r$ vertices) and $K_{r+1}^r$ for the complete $r$-uniform hypergraph on $r+1$ vertices, which has $r+1$ edges. Let $\mathrm{ex}_r(n;K_{r+1}^r)$ denote the maximum number of $r$-edges that can be placed on $n$ vertices without forming a $K_{r+1}^r$. Question: is every $r$-uniform hypergraph $G$ on $n$ vertices the union of at most $\mathrm{ex}_r(n;K_{r+1}^r)$ copies of $K_r^r$ and $K_{r+1}^r$, no two of which share a $K_r^r$ (i.e. no two of the chosen pieces have a common $r$-edge)? Equivalently, can the edge set of every $r$-uniform hypergraph on $n$ vertices be partitioned into at most $\mathrm{ex}_r(n;K_{r+1}^r)$ pieces, each of which is a single $r$-edge or the $r+1$ edges of an $(r+1)$-vertex clique?
Acceptance. FULLY RESOLVES: a complete proof of the Erdős–Sauer conjecture — that every $r$-uniform hypergraph on $n$ vertices edge-decomposes into at most $\mathrm{ex}_r(n;K_{r+1}^r)$ pieces, each a single edge or an $(r+1)$-vertex clique with no two pieces sharing an edge — for all $r\geq 2$ and $n$ (machine-checkable preferred, otherwise a full written proof); OR an explicit counterexample: specific $r$, $n$, and hypergraph $G$ that provably requires strictly more than $\mathrm{ex}_r(n;K_{r+1}^r)$ such pieces, supplied with a verified value of the Turán number $\mathrm{ex}_r(n;K_{r+1}^r)$ and a proof of the lower bound on the number of pieces. ADVANCES (each independently checkable): (a) prove the conjecture for a fixed small $r$ (e.g. $r=3$) or an infinite family of $r$; or (b) verify it exhaustively for all $r$-uniform hypergraphs on $n\leq N$ vertices for a new record $N$, with the search code, the verified $\mathrm{ex}_r$ values used, and an exhaustiveness certificate. Deliver the proof, the counterexample with certificate, or the verification code plus the attained range.
Background
A conjecture of Erdős and Sauer, recorded by Erdős [Er81]; listed as open on erdosproblems.com/719 (fetched 2026-07-13, status 'open', tagged 'graph theory | hypergraphs'). Context for the quantity $\mathrm{ex}_r(n;K_{r+1}^r)$: it is the Turán number for the $(r+1)$-vertex clique in $r$-uniform hypergraphs; the $r=2$ instance is Mantel's/Turán's theorem, $\mathrm{ex}_2(n;K_3)=\lfloor n^2/4\rfloor$, and the general $\mathrm{ex}_r$ is itself a hard extremal quantity (e.g. the case $r=3$ is Turán's still-open $(3,4)$ conjecture). The Erdős–Sauer conjecture proposes that this same extremal count — the most edges a $K_{r+1}^r$-free hypergraph can have — also bounds the number of clique/edge pieces needed to edge-decompose an arbitrary $r$-uniform hypergraph on $n$ vertices. The source page lists no partial results, so the recorded frontier is essentially the bare conjecture; a solver should treat both directions (proof and search for a counterexample) as open. No Erdős prize is attached. Attacker's tool: exhaustive / ILP-based search that, for small $r$ and $n$, computes $\mathrm{ex}_r(n;K_{r+1}^r)$ and tests whether every $r$-uniform hypergraph on $n$ vertices admits the conjectured decomposition, seeking either verification or a minimal counterexample.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #719 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.