Erdős–Sauer conjecture

For an rr-uniform hypergraph GG on nn vertices let K=Kr+1(r)K=K_{r+1}^{(r)} and let ν(G)\nu(G) denote the maximum number of edge-disjoint copies of KK. The smallest number of pieces in a partition of E(G)E(G) into copies of KK and single edges is

D(G)=|E(G)|−rν(G).D(G)=|E(G)|-r\nu(G).

The conjecture is D(G)≤exr(n,K)D(G)\le\operatorname{ex}_r(n,K) for every r≥2r\ge2 and every nn. The original paper places the conjecture immediately after the Erdős–Goodman–Pósa theorem, which gives r=2r=2. This is the hypergraph decomposition question in Section IV.3, p. 8. Erdős, Combinatorica 1981 · Erdős Problem 719 · Research issue

Searches by author, title, problem number and the packing and covering formulations found no proof of the exact unrestricted statement. The July 2026 working report proves a range near n=rn=r by complementing edges and identifies a connection to the Aharoni–Zerbib conjecture. Pikhurko and Sousa establish an asymptotic decomposition theorem for ordinary graphs with a fixed piece graph. The argument below obtains a hypergraph bound with a strict saving proportional to the clique packing number before the approximation error. Problem 719 working report · Pikhurko–Sousa · Parker on generalized Tuza

The asymptotic bound and stability

Theorem. Fix r≥3r\ge3. Define γ3=20/7\gamma_3=20/7 and γr=r−1\gamma_r=r-1 for r≥4r\ge4. Uniformly over nn-vertex rr-graphs,

D(G)≤exr(n,K)−(r−γr)ν(G)+o(nr).D(G)\ \le\ \operatorname{ex}_r(n,K)-(r-\gamma_r)\nu(G)+o(n^r).

Consequently the maximum decomposition number is exr(n,K)+o(nr)\operatorname{ex}_r(n,K)+o(n^r). Every sequence attaining that value to within o(nr)o(n^r) is within o(nr)o(n^r) edge deletions of a KK-free sequence with exr(n,K)−o(nr)\operatorname{ex}_r(n,K)-o(n^r) edges. For any fixed ϵ>0\epsilon\gt0, the exact conjectured bound holds for sufficiently large nn if |E(G)|≥exr(n,K)+ϵnr|E(G)|\ge\operatorname{ex}_r(n,K)+\epsilon n^r.

Let τK(G)\tau_K(G) denote the minimum number of edges whose removal makes GG KK-free. Write ν*(G)\nu^*(G) for the fractional packing number, which by linear programming duality equals the minimum total edge weight of a fractional KK-cover. Theorem 1.1 of Rödl, Schacht, Siggers and Tokushige gives ν*(G)−ν(G)=o(nr)\nu^*(G)-\nu(G)=o(n^r) uniformly. We show below that τK(G)≤γrν*(G)\tau_K(G)\le\gamma_r\nu^*(G). Since deleting a cover leaves at most exr(n,K)\operatorname{ex}_r(n,K) edges,

|E(G)|−rν(G)≤exr(n,K)+γrν*(G)−rν(G),|E(G)|-r\nu(G)\le\operatorname{ex}_r(n,K)+\gamma_r\nu^*(G)-r\nu(G),

which proves the estimate. An extremal KK-free graph supplies the matching leading-order lower bound. Near equality forces ν(G)=o(nr)\nu(G)=o(n^r), and deleting all the edges in a maximum packing makes the graph KK-free and deletes (r+1)ν(G)(r+1)\nu(G) edges. For the last assertion, the same deletion gives ν(G)≥ϵnr/(r+1)\nu(G)\ge\epsilon n^r/(r+1), and r−γr>0r-\gamma_r\gt0 absorbs the approximation error. Rödl–Schacht–Siggers–Tokushige, Theorem 1.1

Fractional covering with a saving

The following argument works for an arbitrary family ℱ\mathcal F of (r+1)(r+1)-sets, with integral and fractional covers by rr-sets and fractional matchings using capacity one at each rr-set. We adapt the support rounding of Basit, McGinnis, Simmons, Sinnwell and Zerbib to the complete rr-graph on r+1r+1 vertices with one edge removed. Basit et al., Theorem 1.10 and Section 4

Suppose there is a random rr-graph AA on the ground set such that every (r+1)(r+1)-set contains at most r−1r-1 edges of AA, and every rr-set belongs to AA with probability at least aa. Set

γ=max{r−1,(r+1)(1−a)}.\gamma=\max\{r-1,(r+1)(1-a)\}.

Take an optimal fractional cover xx with support UU and an optimal fractional matching yy. Every u∈Uu\in U has load ∑F⊃uyF=1\sum_{F\supset u}y_F=1 by complementary slackness. Counting incidences of UU with members of ℱ\mathcal F therefore gives |U|≤(r+1)∑FyF|U|\le(r+1)\sum_F y_F.

Use induction on |ℱ||\mathcal F|. If some xu≥1/γx_u\ge1/\gamma, put uu in the integral cover and remove all sets containing it. The remaining fractional cover costs at most ∑vxv−xu\sum_v x_v-x_u, so the induction bound pays for the edge just added. Otherwise every F∈ℱF\in\mathcal F contains at least rr supported rr-sets, because γ≥r−1\gamma\ge r-1 and the cover weights on FF sum to at least one. Thus U\AU\setminus A meets every FF. Its expected size is at most (1−a)|U|≤γ∑FyF(1-a)|U|\le\gamma\sum_F y_F. Some realization is an integral cover of the required size.

For r=3r=3, use the six-vertex 33-graph H6H_6 of the Frankl–Füredi construction. It consists of a cyclically ordered five-set and a sixth vertex, with five triples formed by the sixth vertex and two consecutive cycle vertices, and five triples of cycle vertices inducing exactly one cycle edge. Each four-set has at most two triples. Assign independent infinite sequences of uniform six-colour labels to the vertices. Include a triple if at its first nonconstant coordinate its three labels form a triple of H6H_6. For a four-set, inspect its first nonconstant coordinate. If there are four distinct labels, use the H6H_6 condition. With three distinct labels, at most the two triples with distinct labels can be selected. With two distinct labels, only a triple in a class of three can be selected later. The inclusion probability for each triple is (10⋅3!/63)/(1−6−2)=2/7(10\cdot 3!/6^3)/(1-6^{-2})=2/7. This gives γ3=20/7\gamma_3=20/7. Frankl–Füredi construction and H6H_6

For r≥4r\ge4, use independent infinite sequences of fair bits. Include an rr-set if its number of ones at the first nonconstant coordinate belongs to one fixed parity of {2,…,r−2}\{2,\ldots,r-2\}. On any (r+1)(r+1)-set, let jj be its number of ones at the first nonconstant coordinate. When j=1j=1 or j=rj=r, at most the single monochromatic rr-subset can be included later. For 2≤j≤r−12\le j\le r-1 the rr-subsets have counts j−1j-1 and jj, with multiplicities jj and r+1−jr+1-j. At most one of the counts is selected, so at most r−1r-1 subsets are included. The inclusion probability is the binomial mass of the chosen counts divided by 1−21−r1-2^{1-r}. For r=4r=4 use count two, giving a=3/7a=3/7. For r=5r=5 use count two, giving a=1/3a=1/3. For r≥6r\ge6 choose the parity with the larger mass, which even without the denominator gives a≥(1−2(r+1)2−r)/2≥25/64a\ge(1-2(r+1)2^{-r})/2\ge25/64. Thus a≥2/(r+1)a\ge2/(r+1) and γr=r−1\gamma_r=r-1 for every r≥4r\ge4.

Exact bound when each edge belongs to at most two cliques

Suppose r≥3r\ge3 and every edge of GG lies in at most two copies of KK. Form the graph JJ whose vertices are the copies and whose edges correspond to shared rr-edges. Then ν(G)=α(J)\nu(G)=\alpha(J) and Δ(J)≤r+1\Delta(J)\le r+1. A maximum matching of JJ gives a cover of the copies by the shared edges of its matching pairs and one arbitrary edge from each unmatched copy. There are at most α(J)\alpha(J) unmatched copies, since they form an independent set in JJ. Also |V(J)|≤(r+2)α(J)|V(J)|\le(r+2)\alpha(J) by greedy proper colouring. Hence

τK(G)≤|V(J)|+α(J)2≤r+32ν(G)≤rν(G).\tau_K(G)\le\frac{|V(J)|+\alpha(J)}{2} \le\frac{r+3}{2}\nu(G) \le r\nu(G).

This establishes D(G)≤exr(n,K)D(G)\le\operatorname{ex}_r(n,K) in this class, at every order. The general case close to the Turán threshold with unrestricted clique overlaps remains open.