REVIEW 2 major objections 5 minor 12 references
On the $4$-clique cover number of graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Balanced 4-partite graph uniquely maximizes 4-clique cover
desk verdict Genuine first proof of the t=4 case, but the finite base-case verification in Appendix B is arithmetically wrong as printed and must be fixed before this is citable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is a greedy partition of a $K_5$-free graph: repeatedly take a largest clique in the remaining graph and delete its vertices, recording the part sizes as a non-increasing sequence. The partition has the structural property that every vertex in a later part has a non-neighbor in every earlier part, and the number of parts is at most $|V(H)| - \delta(H)$. The paper converts the task of covering all triangles in $H$ into an explicit function $f(A)$ of the greedy sequence, then applies three local adjustment operations that never decrease $f$, leading to a clean upper bound in terms of one parameter $q$. A second layer of improvement comes from an auxiliary 3-uniform hypergraph on the 4-cliques of the partition: a triple of parts that does not induce the balanced 12-vertex 4-partite graph needs only 11 cliques for its triangles, while complete four-vertex hypergraph configurations allow 24 cliques instead of the naive 48.
What would settle it
Check Appendix B by computing $h(n) = k_4(T_{n,4}) - k_4(T_{n-5,4}) - 1 - (n-5) - \frac{2}{5}(n-5)^2 - \frac{2}{25}(n-5)^3$ directly for every $6 \leq n \leq 104$ with $n \notin \{97,101\}$. If any value is $\leq 0$, or if the piecewise polynomial identities in the appendix do not reproduce these values, the base case fails and Theorem 1.2 is not established by this proof.
Extended reading notes
Core claim
The central result, Theorem 1.2, says that for n ≥ 4, $CC_4(G) \leq CC_4(T_{n,4})$ for every n-vertex graph $G$, with equality if and only if $G = T_{n,4}$, where $T_{n,4}$ is the balanced complete 4-partite graph. Because $CC_4(T_{n,4})$ equals the number of 4-cliques in $T_{n,4}$, the theorem gives an explicit extremal formula: the most evenly spread four-part partition is exactly the graph whose 4-cliques are hardest to cover. The proof eliminates graphs with clique number at least 6 by constructing a cover from a maximum clique, handles clique number at most 4 through a classical extremal clique-counting bound, and concentrates the hard case on graphs with clique number exactly 5. For those graphs, the neighborhood of a minimum-degree vertex is $K_5$-free, and the paper bounds its triangle-cover number by combining the greedy partition with a refinement based on an auxiliary 3-uniform hypergraph.
Load-bearing premise
The load-bearing premise is that the appendix's finite verification of $h(n) > 0$ for $6 \leq n \leq 104$ (excluding 97 and 101) is correct; if the polynomial formulas used there are wrong, the induction step for n ≥ 105 has no base.
Editorial extensions
If this is right
- For every $n \geq 4$, the 4-clique cover number of any n-vertex graph is at most the number of 4-cliques in the balanced complete 4-partite graph, which grows like $n^4/256$.
- The balanced complete 4-partite graph is the unique extremal graph: any other n-vertex graph covers its 4-cliques with strictly fewer cliques.
- The t = 4 case of the conjecture is resolved, so the remaining open problem is t ≥ 5 on the same conjecture.
- The strict inequality proved for every graph with a 5-clique means that equality can only occur for graphs with clique number at most 4, and among those only the balanced 4-partite graph attains it.
Reading between the lines
- The greedy-sequence adjustment operations and the hypergraph refinement are the parts most likely to generalize to t = 5, where the analog would classify 5-tuples of parts by whether they induce a balanced complete 5-partite graph.
- The finite check in Appendix B is the only step not derived in the text; a short script evaluating $h(n)$ directly for $6 \leq n \leq 104$ would settle whether the stated polynomial formulas are correct.
- The method suggests a stability statement: because any graph containing a 5-clique falls strictly below the bound, graphs close to the extremal value must be almost 4-partite, though the paper does not quantify such a statement.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves the t=4 case of the Dau–Milenkovic–Puleo conjecture: for every n-vertex graph G with n≥4, CC4(G)≤CC4(T_{n,4}), with equality only for the balanced complete 4-partite graph. The proof proceeds by induction on n, first reducing to the case ω(G)=5, then combining a greedy-partition bound for the 3-clique cover number of a neighborhood with counting arguments of Erdős and Moon–Moser, and finally verifying a finite list of base cases in the appendices.
Significance. If the proof is completed, this confirms a natural generalization of the Erdős–Goodman–Pósa theorem and the t=3 result of Dau, Milenkovic, and Puleo, and it identifies the Turán graph T_{n,4} as the unique extremal example. The inductive framework, the local adjustment operations, and the auxiliary hypergraph argument in Lemma 3.2 are genuinely new tools for this problem and are likely to be useful for larger t. The paper does not rely on machine-checked proofs, but it does provide explicit algebraic verifications in appendices, which is helpful for independent checking; however, one of those verifications is currently incorrect as printed.
major comments (2)
- [§3 and Appendix B] The formula for h(4k) is arithmetically inconsistent with the definition h(n)=k4(T_{n,4})−k4(T_{n−5,4})−1−(n−5)−(2/5)(n−5)^2−(2/25)(n−5)^3. Direct expansion gives h(4k)=(−3k^3+95k^2−125k+50)/25, not the printed value −(1/25)(3k^3−90k^2+75k−50). The stated range for n=4k is also inconsistent with n≤104: for n=4k one has k≤26, not k≤29. Because the induction step for n≥105 and for n∈{97,101} relies on the finite base check that h(n)>0 for 6≤n≤104 with n∉{97,101}, the base-case verification is not established as written. The corrected polynomial still appears to be positive on the required range, so the error is likely repairable, but it must be fixed before the proof is complete.
- [§3 and Appendix B] The base-case block is not self-contained as presented. The proof for n=102 in Appendix B invokes the induction hypothesis for G′ on n−5=97 vertices, but 97 is excluded from the base cases. Since the theorem for 97 is not yet proved at that point, the argument for n=102 has a circular dependency unless the proof order is specified. The authors should state explicitly that 97 (and 101) are first handled by the main argument, using only the already-proved values below 97 (respectively 101), and that 102 is then proved afterwards; alternatively, they should give a proof of 102 that does not use the theorem for 97.
minor comments (5)
- [§4.3] The notation for the complement hypergraph is garbled: the text reads “Let |E(H)|=E and |E(H)|=E” and then uses E both for hyperedges of H and for missing triples; these two quantities should be denoted distinctly, for example E and \bar E.
- [§4.3] In the dense case of Lemma 3.2, the step from the lower bound on disjoint K^{(3)}_4's to inequality (11) skips the identity 24·(1/108(a−1)^2(a−2)−1/144 a^2(a−1)) = 2/9(a−1)^2(a−2)−1/6 a^2(a−1); stating this identity would make the deduction transparent, especially for small a where the displayed lower bound is negative.
- [§3] The sentence “Since δ(G)=d=3k+1, we conclude that v is adjacent to all vertices of G′” should explain that every vertex of T_{4k,4} has degree 3k in G′ and therefore needs v as an extra neighbor to reach the minimum degree; as written the implication is abrupt.
- [§4.2] In Lemma 4.2, the definition “C = C1 ∪ C2 ∪ C3\D, where D = {V(H)∪E(H)}” is unclear; D should be described in words, since V(H) and E(H) are not cliques in the same sense as the members of C1∪C2∪C3.
- [Appendix B] The ranges for the residue classes n=4k and n=4k+3 extend beyond n≤104 (k≤29 and k≤27 respectively); this is harmless if the positivity claims are correct, but it is confusing and should be aligned with the stated base-case range.
Circularity Check
No circularity: the proof is an induction with explicit constructions and external extremal lemmas; the Appendix B arithmetic inconsistency is a correctness issue, not a circular-reasoning one.
full rationale
The derivation does not assume its target. Theorem 1.2 is proved by induction on n; Section 2.2 states, "We prove Theorem 1.2 by induction on n = |V(G)|," and the induction hypothesis is only used for graphs on fewer than n vertices. The main bound on CC3(H) is obtained by an explicit greedy-partition cover construction (Lemma 4.2), followed by algebraic maximization of the associated greedy sequence (Lemma 4.3) and structural refinements in Claims 4.7 and 4.8. No fitted parameter is renamed as a prediction, and no quantity is defined in terms of the result it is used to prove. External results by Erdős, Moon and Moser, Lovász, Turán, and Dau–Milenkovic–Puleo are cited as tools or benchmarks. The only self-citation is reference [1], which is mentioned as background and is not load-bearing for Theorem 1.2. The finite base-case check in Appendix B is a direct computation of h(n); even though the displayed n=4k polynomial is arithmetically inconsistent with its definition, that is a correctness risk, not circularity, because the positivity check is not equivalent to the theorem's input or conclusion. Therefore no circular step is exhibited.
Assumptions & free parameters
assumptions (6)
- standard math Turán's theorem: the maximum K_{r+1}-free graph on n vertices is T_{n,r}
- standard math Lemma 2.1 (Erdős): h(n,k,t) = k_t(T_{n,k-1})
- standard math Lemma 2.2 (Moon-Moser): ratio of clique counts bound
- standard math Proposition 3.1 (Lovász greedy partition property): p ≤ n - δ(H) and non-neighbor property
- standard math Dau et al. result for t=3: CC3(G) ≤ CC3(T_{n,3})
- standard math Identity k4(T_{n,4}) - k4(T_{n-1,4}) = k3(T_{floor(3n/4),3})
Cite this review
Pith. "Pith review of On the $4$-clique cover number of graphs." pith.science (2026). https://pith.science/paper/C72CKME3
@misc{pith2026250610478,
author = {Pith},
title = {Pith review of: On the $4$-clique cover number of graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/C72CKME3}},
note = {Machine review of arXiv:2506.10478}
}
abstract
In 1966, Erd\H{o}s, Goodman, and P\'osa proved that $\lfloor n^2/4 \rfloor$ cliques are sufficient to cover all edges in any $n$-vertex graph, with tightness achieved by the balanced complete bipartite graph. This result was generalized by Dau, Milenkovic, and Puleo, who showed that at most $\lfloor \frac n 3 \rfloor \lfloor \frac {n+1} 3 \rfloor \lfloor \frac {n+2} 3 \rfloor$ cliques are needed to cover all triangles in any $n$-vertex graph $G$, and the bound is best possible as witnessed by the balanced complete tripartite graph. They further conjectured that for $t \geq 4$, the $t$-clique cover number is maximized by the Tur\'an graph $T_{n,t}$. We confirm their conjecture for $t=4$ using novel techniques, including inductive frameworks, greedy partition method, local adjustments, and clique-counting lemmas by Erd\H{o}s and by Moon and Moser.
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
H. Dau, O. Milenkovic and G. J. Puleo, On the triangle clique cover and Kt clique cover problems, Discrete Math. 343, 2020
work page 2020
-
[4]
Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magy
P. Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magy. Tud. Akad. Mat. Kut. Int´ ez. K¨ ozl.7 (1962), 459–474
work page 1962
-
[5]
P. Erd˝ os, A. W. Goodman and L. P´ osa, The representation of a graph by set intersections, Canad. J. Math. 18 (1966), 106–112
work page 1966
-
[6]
J. Leskovec, K. J. Lang and M. W. Mahoney, Empirical comparison of algorithms for network community detection, in: Proceedings of the 19th International Conference on World Wide Web, in: WWW ’10 , 2010, pp. 631–640. 14
work page 2010
-
[7]
Lov´ asz, On covering of graphs,in: Theory of Graphs (Proc
L. Lov´ asz, On covering of graphs,in: Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 231–236
work page 1966
-
[8]
J. W. Moon and L. Moser, On a problem of Tur´ an, Magy. Tud. Akad. Mat. Kut. Int´ ez. K¨ ozl.7 (1962), 283–286
work page 1962
Show all 12 references
-
[9]
Palla, I
G. Palla, I. Der´ enyi, I. Farkas and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature 435 (2005), 814–818
2005
-
[10]
F. S. Roberts, Applications of edge coverings by cliques, Discrete Appl. Maths. , 10 (1) (1985), 93–109
1985
-
[11]
E. R. Scheinerman and A. N. Trenk, On the fractional intersection number, Graphs Combin. , 15 (3) (1999), 341–351
1999
-
[12]
Tur´ an, On an extremal problem in graph theory, Matematikai ´ es Fizikai Lapok, 48 (1941), 436–452
P. Tur´ an, On an extremal problem in graph theory, Matematikai ´ es Fizikai Lapok, 48 (1941), 436–452. Appendix A: Justification of the inequality (3) for 6 ≤ c ≤ 10 Let g(n, c) = (n−2)2(n+2)2 256 − n−c 4 4 + 1 + (n − c) + c 2 n−c c 2 + c 3 n−c c 3. Then, inequality (3) holds...
1941
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.