{"id":"3c87a60f-1a13-4c2d-a0a7-0d601831d77b","arxiv_id":"2506.10478","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every n-vertex graph G, the 4-clique cover number of G is at most that of the Turán graph T_{n,4}, confirming the t=4 case of the Dau-Milenkovic-Puleo conjecture.","lead":"This paper proves a 2020 conjecture by Dau, Milenkovic, and Puleo for the case of 4-cliques: any n-vertex graph can have its 4-cliques covered by no more cliques than the balanced complete 4-partite graph. The result settles the first open case of the conjecture and introduces a greedy-partition plus hypergraph-counting technique that may generalize to larger clique sizes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix B's n=4k polynomial for h(n) is arithmetically inconsistent with its definition; the base-case verification is therefore not established as printed, though the corrected expression appears to still be positive on the required range.","rationale":"The reader's weakest assumption identifies exactly the load-bearing spot: the finite verification in Appendix B underpins the induction, and the printed polynomials are incorrect. I independently re-derived the n=4k case and found the displayed formula differs in both the k^2 and k terms, confirming the manuscript's base-case proof is not valid as written. However, the corrected polynomial is positive for all k appearing in the required range, and the other residue classes are consistent with the definition, so the flaw is arithmetic rather than conceptual. I do not see a more serious gap in the main induction or in Lemma 3.2: the greedy-partition construction and the hypergraph refinement are intricate but internally coherent, and no circularity or fitted parameters are present. Therefore the reader's CONDITIONAL verdict is appropriate, and no verdict change is needed.","tokens_in":21399,"tokens_out":44662,"duration_ms":502201,"concrete_test":"Evaluate h(n) exactly from its definition for every n in {6,...,104} \\ {97,101}, using k4(T_{n,4}) as the product of the balanced 4-part sizes and k4(T_{n-5,4}) computed the same way. In particular, for n=4k, check that h(4k)=(-3k^3+95k^2-125k+50)/25 is positive for 2 ≤ k ≤ 26, and repeat the exact positivity check for the other three residue classes on their actual intervals. This single recomputation settles whether the base case is valid; if every value is positive, the induction can be repaired by replacing the incorrect Appendix B polynomials with the correct ones.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The induction in §2.2 and §3 rests on the finite check that h(n)>0 for 6 ≤ n ≤ 104 with n not in {97,101}, where h(n)=k4(T_{n,4})-k4(T_{n-5,4})-1-(n-5)-(2/5)(n-5)^2-(2/25)(n-5)^3. In Appendix B the displayed residue-class polynomials do not match this definition. For n=4k, direct expansion gives k4(T_{n,4})=k^4 and k4(T_{n-5,4})=(k-1)^3(k-2), so h(4k)=(-3k^3+95k^2-125k+50)/25, not -1/25(3k^3-90k^2+75k-50) as printed. Thus the base-case verification is false as written. The stated ranges are also inconsistent with n ≤ 104 (for example, n=4k only reaches k ≤ 26, while the paper says k ≤ 29). Since Theorem 1.2 is proved by induction and the induction step only starts at n ≥ 105 plus n ∈ {97,101}, this finite base case is load-bearing. The corrected n=4k polynomial is still positive for 2 ≤ k ≤ 26, and the other residue-class formulas appear to match direct expansion, so the error is likely repairable; but the manuscript as submitted does not contain a correct proof of the base case.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21670,"tokens_out":30472,"duration_ms":328451,"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":[{"comment":"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.","section":"§3 and Appendix B"},{"comment":"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.","section":"§3 and Appendix B"}],"minor_comments":[{"comment":"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.","section":"§4.3"},{"comment":"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.","section":"§4.3"},{"comment":"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.","section":"§3"},{"comment":"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.","section":"§4.2"},{"comment":"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.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The main structural argument appears sound, and the confirmed arithmetic error in Appendix B is localized and repairable. I would encourage the authors to re-check all algebraic identities in the appendices, perhaps with symbolic computation, and to clarify the ordering of the base cases so that n=102 does not depend on n=97 before 97 is proved. The novelty and potential impact are appropriate for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the headline: this paper is the first exact confirmation of the Dau–Milenkovic–Puleo conjecture for t=4, with equality case. That is a real step beyond Dau et al.'s t=3 theorem and the asymptotic result for all t. The proof is not a routine extension; it introduces a greedy partition lemma with local adjustment operations, an auxiliary 3-uniform hypergraph, and a counting argument that actually uses the structure of Turan graphs. The main inductive framework is plausible, and I see no circularity or fitted parameters. The authors are honest about what they prove, and the references are appropriate.\n\nThe soft spot is exactly where the reader put it, and it is not cosmetic. Appendix B is load-bearing: the induction step only starts at n ≥ 105 plus n = 97, 101, so the finite check that h(n) > 0 for 6 ≤ n ≤ 104 must be correct. As printed, the residue-class polynomials do not match the definition of h. For n = 4k, the definition gives h(4k) = (-3k^3 + 95k^2 - 125k + 50)/25, but the paper prints (-3k^3 + 90k^2 - 75k + 50)/25, and the stated k-range (k ≤ 29) goes up to n = 116, not 104. This means the base case is not established in the submitted version. The corrected polynomial is still positive on the required range, and the other three residue classes appear consistent, so I suspect it is an arithmetic slip rather than a flaw in the method. But the manuscript as it stands does not contain a correct proof of the base case.\n\nI would also like a referee to press on the details of Lemma 3.2's auxiliary hypergraph counting, especially the claim that disjoint K_4^(3)'s give a 24-clique saving without overlapping. The counting is plausible but dense; that is a normal level of scrutiny for a paper of this scope. Nothing there feels broken to me on a first reading.\n\nWho is this for? Researchers in extremal graph theory, especially those working on clique covers and Turan-type problems. It deserves a serious referee, but only after the authors fix Appendix B. I would recommend: send to a journal with a request to repair the base-case verification and re-run the finite check; if that comes back clean, the main theorem is likely correct.","headline":"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.","tokens_in":22215,"tokens_out":4175,"would_cite":false,"duration_ms":44268,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B40","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Balanced 4-partite graph uniquely maximizes 4-clique cover","keywords":["4-clique cover","t-clique cover","Turán graph","balanced complete 4-partite graph","greedy partition","clique counting","K5-free graph","extremal graph theory"],"falsifier":"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.","tokens_in":21167,"feed_emoji":"🧩","tokens_out":10171,"duration_ms":98560,"temperature":0.7,"pith_summary":"The paper proves that for every n-vertex graph, the number of cliques required to cover all of its 4-cliques is at most the number required by the balanced complete 4-partite graph, and that this bound is attained only by that graph. This settles the t = 4 case of a conjecture generalizing the 1966 edge-cover theorem and its triangle-cover analog. The proof reduces any possible counterexample to a graph whose largest clique has exactly five vertices, then controls the neighborhood of a minimum-degree vertex with a greedy partition refined by a hypergraph argument. Small values of n are handled by a finite check in an appendix, and the induction covers all larger n.","feed_headline":"Balanced 4-partite graph uniquely maximizes 4-clique cover","feed_subtitle":"Every n-vertex graph needs at most the 4-clique cover of the balanced 4-partite graph, and only that graph hits the bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Formulates the conjecture for t ≥ 4 and proves the t = 3 case, providing the induction template.","marker":"[3]"},{"why":"Establishes the edge-cover theorem that motivates the problem.","marker":"[5]"},{"why":"Supplies the extremal edge bound used to restrict the minimum degree and clique number.","marker":"[12]"},{"why":"Introduces the greedy clique-partition technique that Section 4 generalizes.","marker":"[7]"},{"why":"Provides the extremal clique-counting formula used to bound subgraphs with bounded clique number.","marker":"[4]"},{"why":"Gives the ratio inequality used to count many complete hypergraph configurations in the refinement.","marker":"[8]"}],"fun_headline_variants":["4-clique cover max: balanced 4-partite graph","Extremal graph for 4-clique cover: balanced 4-partite","4-clique cover solved: balanced 4-partite is extremal","Max 4-clique cover achieved by balanced 4-partite graph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["4-clique cover max: balanced 4-partite graph","Extremal graph for 4-clique cover: balanced 4-partite","4-clique cover solved: balanced 4-partite is extremal","Max 4-clique cover achieved by balanced 4-partite graph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000683,"raw_usage":{"total_tokens":3123,"prompt_tokens":989,"completion_tokens":2134,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":2055}},"tokens_in":605,"tokens_out":2134,"duration_ms":14633,"temperature":1.0,"reasoning_tokens":2055,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:27:30.584617+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formulates the conjecture for t ≥ 4 and proves the t = 3 case, providing the induction template."},{"cited_title":"Erd˝ os, A","cited_arxiv_id":null,"evidence_quote":"Establishes the edge-cover theorem that motivates the problem."},{"cited_title":"Tur´ an, On an extremal problem in graph theory, Matematikai ´ es Fizikai Lapok, 48 (1941), 436–452","cited_arxiv_id":null,"evidence_quote":"Supplies the extremal edge bound used to restrict the minimum degree and clique number."},{"cited_title":"Lov´ asz, On covering of graphs,in: Theory of Graphs (Proc","cited_arxiv_id":null,"evidence_quote":"Introduces the greedy clique-partition technique that Section 4 generalizes."},{"cited_title":"Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magy","cited_arxiv_id":null,"evidence_quote":"Provides the extremal clique-counting formula used to bound subgraphs with bounded clique number."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the ratio inequality used to count many complete hypergraph configurations in the refinement."}],"review_version":1}