A mathematics preprint reports answers to two conjectures about decomposing and covering cliques in large finite graphs. It states that, once the number of vertices is sufficiently high, each problem has the proposed upper bound and identifies the graphs that attain equality. The work concerns the class of n-vertex graphs rather than an empirical sample.
To a non-specialist, a clique is a fully connected group of vertices, where every pair is linked. The first question concerns an exact edge-clique decomposition, which uses such groups to account for a graph’s edges. The paper assigns an i-vertex clique a cost of i minus one. The second question concerns a cover made from cliques of one fixed size t, with t at least 2, and compares that cost with the corresponding Turán graph T_n,t.
A bound tied to a balanced split
For the edge-decomposition problem, every sufficiently large n-vertex graph has an exact decomposition costing no more than the greatest integer no larger than n squared divided by four. Equality occurs exactly for graphs in the class E_n named by the manuscript. That makes E_n the theorem’s full equality classification, not merely one example that reaches the bound.
A separate construction describes what happens near a balanced bipartition, meaning a split into two roughly equal sides. If the split has a sufficiently small defect, measured by edges inside one side and missing connections between the sides, the construction produces an exact decomposition whose cost is the benchmark minus a nonnegative integer slack. When the slack is zero, the sides are balanced and all possible crossing connections are present, giving a complete crossing bipartition.
Under the hypotheses of that exact construction, every graph has a decomposition at or below the balanced-bipartite benchmark, while a graph outside E_n has a decomposition at most one cost unit below it. The supplied analysis does not spell out the internal definition of E_n, so the equality class is identified by name rather than described in structural detail here.
The Turán graph is the sole equality pattern
For the covering problem, the result is stated for every t at least 2 and sufficiently large n. The t-clique cover number of an n-vertex graph is no greater than the corresponding number for the Turán graph T_n,t. Equality is possible only when the graph is isomorphic to T_n,t, meaning it has the same structure after its vertices are relabelled.
The paper also gives the result a stability interpretation. For fixed t, a fractional t-clique cover number close to the Turán benchmark implies small edit distance from T_n,t. A fractional cover allows weighted contributions from cliques, while edit distance refers to the edge changes needed to turn one graph into another. The conclusion links a near-benchmark covering value with a graph that is structurally close to the Turán pattern.
The same edit-distance conclusion is reported for the integer t-clique cover number. In both versions, a graph that comes close to the benchmark must also look close to the graph that defines it, although the statements concern sufficiently large graphs and use constants whose numerical values are not supplied.
A proof built from several reductions
The work is theoretical rather than data-driven. Its proof combines linear-programming duality, the spanning-forest polytope, weighted Mantel stability, graph removal, generalized Turán stability, and exact decomposition or covering constructions.
On the covering side, a randomized symmetrization process terminates at a complete multipartite graph, does not lower the expected fractional cover value, and preserves every s-clique count in expectation. Another matching step constructs an injection that assigns distinct admissible transversals to all non-transversal copies of K_t.
What remains outside the claim
The main conclusions are asymptotic. Both headline theorems apply only when n is sufficiently large, and the supplied analysis gives no numerical cutoff for that phrase. Several auxiliary constants are likewise asserted to exist without explicit values, so the preprint does not say which individual finite graph sizes are covered.
The supplied manuscript is an arXiv version 1 preprint in math.CO. Its front page is dated August 27, 2026, while the arXiv line is dated 25 August 2026. Journal and peer-review status are not reported in the supplied material.
The manuscript discloses AI assistance in generating the central proof idea and drafting, and says the author independently checked and refined the outputs and accepts responsibility. The remaining questions include whether the bounds extend to all admissible n, whether the thresholds can be made explicit or reduced, and whether independent formal or peer verification confirms every step of the AI-assisted proof.
Paper data and sources
Original title: Clique decompositions and covers for large graphs
Authors: Wentao Zhang
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text