For an -uniform hypergraph on vertices let and let denote the maximum number of edge-disjoint copies of . The smallest number of pieces in a partition of into copies of and single edges is
The conjecture is for every and every . The original paper places the conjecture immediately after the Erdős–Goodman–Pósa theorem, which gives . 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 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 . Define and for . Uniformly over -vertex -graphs,
Consequently the maximum decomposition number is . Every sequence attaining that value to within is within edge deletions of a -free sequence with edges. For any fixed , the exact conjectured bound holds for sufficiently large if .
Let denote the minimum number of edges whose removal makes -free. Write for the fractional packing number, which by linear programming duality equals the minimum total edge weight of a fractional -cover. Theorem 1.1 of Rödl, Schacht, Siggers and Tokushige gives uniformly. We show below that . Since deleting a cover leaves at most edges,
which proves the estimate. An extremal -free graph supplies the matching leading-order lower bound. Near equality forces , and deleting all the edges in a maximum packing makes the graph -free and deletes edges. For the last assertion, the same deletion gives , and 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 of -sets, with integral and fractional covers by -sets and fractional matchings using capacity one at each -set. We adapt the support rounding of Basit, McGinnis, Simmons, Sinnwell and Zerbib to the complete -graph on vertices with one edge removed. Basit et al., Theorem 1.10 and Section 4
Suppose there is a random -graph on the ground set such that every -set contains at most edges of , and every -set belongs to with probability at least . Set
Take an optimal fractional cover with support and an optimal fractional matching . Every has load by complementary slackness. Counting incidences of with members of therefore gives .
Use induction on . If some , put in the integral cover and remove all sets containing it. The remaining fractional cover costs at most , so the induction bound pays for the edge just added. Otherwise every contains at least supported -sets, because and the cover weights on sum to at least one. Thus meets every . Its expected size is at most . Some realization is an integral cover of the required size.
For , use the six-vertex -graph 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 . For a four-set, inspect its first nonconstant coordinate. If there are four distinct labels, use the 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 . This gives . Frankl–Füredi construction and
For , use independent infinite sequences of fair bits. Include an -set if its number of ones at the first nonconstant coordinate belongs to one fixed parity of . On any -set, let be its number of ones at the first nonconstant coordinate. When or , at most the single monochromatic -subset can be included later. For the -subsets have counts and , with multiplicities and . At most one of the counts is selected, so at most subsets are included. The inclusion probability is the binomial mass of the chosen counts divided by . For use count two, giving . For use count two, giving . For choose the parity with the larger mass, which even without the denominator gives . Thus and for every .
Exact bound when each edge belongs to at most two cliques
Suppose and every edge of lies in at most two copies of . Form the graph whose vertices are the copies and whose edges correspond to shared -edges. Then and . A maximum matching of 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 unmatched copies, since they form an independent set in . Also by greedy proper colouring. Hence
This establishes in this class, at every order. The general case close to the Turán threshold with unrestricted clique overlaps remains open.