Answers are grounded in this paper and cite their sources.
In 1966, Erdős, Goodman, and Pósa showed that if G is an n-vertex graph, then at most n²/4 cliques of G are needed to cover the edges of G, and the bound is best possible as witnessed by the balanced complete bipartite graph. This was generalized independently by Győri--Kostochka, Kahn, and Chung, who showed that every n-vertex graph admits an edge-decomposition into cliques of total `cost' at most 2 n²/4, where an i-vertex clique has cost i. Erdős suggested the following strengthening: every n-vertex graph admits an edge-decomposition into cliques of total cost at most n²/4, where now an i-vertex clique has cost $i-1$. We prove fractional relaxations and asymptotically optimal versions of both this conjecture and a conjecture of Dau, Milenkovic, and Puleo on covering the t-vertex cliques of a graph instead of the edges. Our proofs introduce a general framework for these problems using Zykov symmetrization, the Frankl-Rödl nibble method, and the Szemerédi Regularity Lemma.
No takes yet. Share an insight, caveat, or question.
Balogh et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: