Original title: Clique covers and decompositions of cliques of graphs
József Balogh, Jialin He, Robert A. Krueger, The Van Nguyen +1 · September 2026
In graph theory, a graph is a network of dots connected by lines, called edges. A clique is a cluster of dots where every pair connects directly. Decades ago, mathematicians proved that you can cover all edges in an n-vertex graph using at most $\lfloor n^2/4 \rfloor$ cliques. Later, Paul Erdős suggested a harder puzzle: you can split every edge across cliques whose sizes, minus one, add up to at most $\lfloor n^2/4 \rfloor$. The researchers tackled this problem alongside a related puzzle by Dau, Milenkovic, and Puleo about covering clusters of t dots. They built a mathematical framework that blends three advanced tools to prove fractional versions and nearly exact, asymptotic solutions for both conjectures.
Imagine you have a pile of sticks, and you want to bundle them so that every stick is in exactly one bundle, and each bundle must have all its sticks touching each other at one end. You pay a fee for each bundle, and the fee is one less than the number of sticks in it. You want to minimize the total fee. The old rule said you might pay up to twice the minimum possible, but this paper shows you can always get close to the minimum, even if you also want to cover not just sticks but larger groups of sticks that all touch each other.
This work tightens a classic bound on how to break a graph into cliques, which matters for problems in network design and data compression. The new results also cover cliques of any size, not just edges, and the framework could apply to other optimization problems on graphs.
The results are asymptotic, meaning they hold for large graphs but may not be exact for small ones. The paper proves fractional relaxations and asymptotically optimal versions, not the exact integer versions of the conjectures. It does not provide explicit algorithms for finding the decompositions, only existence proofs.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Clique covers and decompositions of cliques of graphs — József Balogh, Jialin He, Robert A. Krueger et al. — Advances in Combinatorics — doi:10.19086/aic.2026.9
Abstract licence: CC BY
Explanation generated by Synthesis from the abstract — it is not the original paper.