{"id":"d356378d-c696-44cb-9ec5-1fdd92d7ff0b","arxiv_id":"2411.19915","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every K_{r+1}-free graph partitions into at most (1/ε)^{C_r} parts of maximum degree at most ε|S_i|, for each r≥2.","lead":"The paper proves that every graph with no large clique can be cut into a small number of pieces, with each piece having very few edges per vertex. It answers an open question of Fox, Nguyen, Scott and Seymour about sparse partitions of graphs with bounded clique number.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The inductive extension step never proves that the leftover set \\tilde R is (ε/6)-dense to the new \\tilde S_i; the third bullet of the invariant is unsupported, so the contradiction of maximality of k does not go through.","rationale":"The reader's weakest-assumption analysis focused on Lemma 2.7 and found the proof structurally sound. I agree that Lemma 2.7 is defensible, but the actual load-bearing gap lies later, in the verification of the inductive invariant for the new partition. The proof states that the new partition satisfies the same three bullets, yet only the size part of the third bullet (Claim 7) is proved. The density part, '\\tilde R is (ε/6)-dense to \\tilde S_i', is essential: it is exactly what lets Claim 2 apply Lemma 2.6 when k+1 = r to produce a K_{r+1}. The construction gives that each v ∈ \\tilde R is (ε/3)-dense to Y_i, but \\tilde S_i is a part T'_i of Y_i, and no argument forces v's neighbours in Y_i to meet T'_i. The random choice in Lemma 2.8 was made to serve B_i, not \\tilde R, so this is not a matter of a typo but of a missing step in the main induction. Because the step is plausibly repairable by enlarging the random-partition argument, I would not reject the underlying claim outright, but the paper as written does not establish Theorem 2.1. Hence the verdict should move from ACCEPT to CONDITIONAL, pending a rigorous proof of the density of \\tilde R to each \\tilde S_i.","tokens_in":7638,"tokens_out":52427,"duration_ms":394991,"concrete_test":"Attempt to derive the missing density bound: for v ∈ \\tilde R and i ≤ k+1, the hypotheses give |N(v)∩Y_i| ≥ (ε/3)|Y_i| and |T'_i| ≥ |Y_i|/3, but these do not imply |N(v)∩T'_i| ≥ (ε/6)|T'_i|; a counterexample is to put N(v)∩Y_i entirely inside T_i, so the intersection with T'_i is empty. Check the manuscript after Claim 7 for any additional argument bounding |N(v)∩T'_i|; no such argument appears. If Lemma 2.8 is modified to also ensure, with high probability, that every vertex of \\tilde R has many neighbours in T'_i (using |\\tilde R| ≤ (ε/300)|Y_i| in a union bound), the gap may be repairable, but as written it is absent.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 2.1, the new partition is declared to satisfy the same three bullets as before, including '\\tilde R is (ε/6)-dense to \\tilde S_i' for each i. Claim 7 proves only the size bound |\\tilde R| ≤ (ε/100)|\\tilde S_i|; the density part is never shown. From the construction, a vertex v ∈ \\tilde R = R' \\(B_1∪...∪B_{k+1}) is not selected into any B_i, so for each i it is (ε/3)-dense to Y_i, i.e. |N(v)∩Y_i| ≥ (ε/3)|Y_i|. But \\tilde S_i is only the part T'_i of the partition Y_i = T_i ∪ T'_i produced by Lemma 2.8, and Lemma 2.8 only guarantees that B_i is (ε/6)-dense to T_i, not that \\tilde R is dense to T'_i. Nothing in the construction prevents all neighbours of v in Y_i from lying in T_i, in which case v has zero neighbours in \\tilde S_i, violating the required density. Since the third bullet is used when applying Claim 2 to the enlarged sequence (to force a K_{r+1} if k+1 = r), the maximality argument is incomplete. This is a genuine gap in the written proof, independent of the many smaller typos.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript proves Theorem 2.1: for each integer r ≥ 2 there is a constant C_r > 0 such that for every 0 < ε ≤ 1/2 and every K_{r+1}-free graph G, V(G) admits a partition into at most (1/ε)^{C_r} sets S_i with Δ(G[S_i]) ≤ ε|S_i|. This gives the strong polynomial Rödl property for complete graphs, a strengthening of the polynomial Rödl property for which complete graphs were the open case raised by Fox, Nguyen, Scott and Seymour (who had handled P_4-free graphs). The proof is self-contained: it maintains a partition invariant consisting of a 'full' sequence S_1,...,S_k together with a leftover set R that is tiny and (ε/6)-dense to each S_i. A maximality argument (Claim 2, using Lemma 2.6) shows k < r, and an extension step using the dense-pair extraction Lemma 2.7 and the random-subset Lemma 2.8 upgrades any valid partition with k < r to one with k+1 sets, contradicting maximality. The exponent bookkeeping is organized through explicitly constructed constants a_0,...,a_{r-1} and C_r. I verified the individual claims and the exponent arithmetic; the main problem is in the extension step, detailed in the major comments.","tokens_in":7951,"tokens_out":56010,"duration_ms":384033,"significance":"The result, once the proof is completed, is a significant and natural advance: it supplies the first infinite family of graphs H beyond cographs for which the strong polynomial Rödl property is known, and it resolves the concrete question about triangles raised in [FNSS23]. The proof technique is attractive and elementary, and the paper is refreshingly explicit: all constants are constructed rather than asserted non-effectively. The manuscript is concise and mostly well organized. My assessment is conditional: one load-bearing step of the extension argument is not proved as written (major comments 1 and 2), but the gap is local and admits a direct repair, so I do not doubt the theorem itself and recommend revision rather than rejection.","major_comments":[{"comment":"The third bullet of the partition invariant is never established for the new partition. For the enlarged partition, the invariant requires both |\\tilde R| ≤ (ε/100)|\\tilde S_i| and that \\tilde R is (ε/6)-dense to \\tilde S_i for every 1 ≤ i ≤ k+1. Claim 7 proves only the size bound; the density assertion is not proved anywhere. A vertex v ∈ \\tilde R is not selected into any B_i, so for each i it satisfies |N(v)∩Y_i| ≥ (ε/3)|Y_i|, but \\tilde S_i = T'_i is only the part of the partition Y_i = T_i ∪ T'_i delivered by Lemma 2.8, and nothing in Lemma 2.8 or in the construction relates the neighbourhood of v to T'_i: all neighbours of v in Y_i could lie in T_i, in which case v has no neighbours at all in \\tilde S_i. The density assertion is exactly what the Claim-2 argument would use when the enlarged sequence reaches length r, so the maximality contradiction does not go through. This is a genuine, load-bearing gap in the written proof.","section":"§2, proof of Theorem 2.1, the paragraph following Claim 7"},{"comment":"The invocation of Lemma 2.8 on the pair (Y_i, B_i) is not licensed by the hypotheses as written. Lemma 2.8 requires B to be α-dense to A, and its proof uses the lower bound |N(v)∩A| ≥ α|A| through Chernoff; but B_i was defined as the set of vertices in R'\\(B_1∪...∪B_{i-1}) that are (ε/3)-sparse to Y_i. The words 'sparse' and 'dense' are not interchangeable in this paper (they are defined at the start of Section 2), so as written the lemma cannot be applied. These two issues are jointly repairable in a local way: every vertex of \\tilde R is (ε/3)-dense to each Y_i, so one may apply Lemma 2.8 to (Y_i, \\tilde R) and take \\tilde S_i to be the part of the resulting partition of Y_i to which \\tilde R is (ε/6)-dense, absorbing the complementary part together with B_i into \\tilde A; Claims 3–7 still supply the needed size, sparsity and fullness bounds. I regard the gap as repairable within the manuscript's scope, but it must be addressed before the proof is complete.","section":"§2, proof of Theorem 2.1, application of Lemma 2.8"}],"minor_comments":[{"comment":"The inequality of Lemma 2.5 is used in Lemma 2.4 but is stated with 'the proof of which we omit'; a one-line proof (it is equivalent to ln(1−x) ≤ x² ln x for 0 < x < 1) or a reference should be supplied.","section":"§2, Lemma 2.5"},{"comment":"In the maximality argument, the failure of the third bullet is written with |X| ≥ α|A'|, but the fullness parameter is (α^ℓ, β, α/2), so this must be |X| ≥ α^ℓ|A'|; the next line, which uses the factor (1−α^ℓ), confirms that this is a typo and not a substantive error.","section":"§2, proof of Lemma 2.7"},{"comment":"In the statement of Lemma 2.8, the hypothesis is written as '|B| ≤ (α/100)|S|' with S undefined; it should be '|B| ≤ (α/100)|A|'.","section":"§2, Lemma 2.8"},{"comment":"The displayed recursion contains the typo 'Pr−1 i=j+1'; it should read Σ_{j=i+1}^{r-1}, and the text should state explicitly that a_i is chosen after a_{i+1},...,a_{r−1} have been fixed.","section":"§2, definition of a_i"},{"comment":"The variable g(ε) in the last display of Claim 6's proof should be h(ε), and the final exponent should be 8(r−k−1)+1 rather than 8(r−k+1)+1; as printed, the last inequality is false for k = 0, 1, although the claim itself is correct.","section":"§2, proof of Claim 6"},{"comment":"The displayed bound '2(e^{−54/100} + 54e^{−1/100})' is not < 1 and does not follow from the preceding line; the intended estimate, using |A| ≥ 100 and |B| ≤ (α/100)|A|, is 2(e^{−100/54} + (54/100)e^{−1}) < 1, so the argument is easily repaired.","section":"§2, proof of Lemma 2.8"},{"comment":"Typos: 'greedly' should be 'greedily' (proof of Lemma 2.4); 'Analogies' should be 'analogues' (Section 1); 'Jounal' should be 'Journal' (reference [CSSS23]).","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The reader's report recommended acceptance with soundness 8; I agree that the theorem is very likely true and that the paper is well written, but I could not verify the extension step: the density half of the third invariant bullet is simply not proved (major comment 1), and the application of Lemma 2.8 to (Y_i, B_i) contradicts the hypotheses (major comment 2). The repair I sketched (apply Lemma 2.8 to (Y_i, \\tilde R) and swap the roles of T_i and T'_i) is short and stays within the paper's framework, so I expect a revision to succeed; in the meantime the manuscript should not be accepted as is. I would also ask the editor to ensure that the proof of Lemma 2.5 is supplied, since it is a used lemma rather than a standard reference."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves that every complete graph has the strong polynomial Rödl property, resolving the open triangle case and generalizing the known P4 result. That is a real step forward, and the proof has interesting new machinery: Lemma 2.7, which converts density into fullness with explicit bounds, and the carefully chosen exponent sequence. The overall strategy is self-contained and mostly elementary, and the paper is clearly written aside from a few typos.\n\nThe problem is that the main theorem's proof does not close. In the induction step of Theorem 2.1, the new partition is declared to satisfy the same invariant as before, including the requirement that the leftover set \\tilde R is (ε/6)-dense to each new \\tilde S_i. Claim 7 only proves the size bound |\\tilde R| ≤ (ε/100)|\\tilde S_i|; the density half is never shown. A vertex in \\tilde R is known to be (ε/3)-dense to each Y_i, but the new set \\tilde S_i is only the part T'_i of a partition Y_i = T_i ∪ T'_i, and there is no control on where those neighbours lie. They could all be in T_i, leaving \\tilde R with zero neighbours in \\tilde S_i. Since the density condition is used in Claim 2 to force a K_{r+1} when k+1 = r, the maximality contradiction does not go through. This is not a cosmetic typo; it is a missing argument in the central inductive step.\n\nI checked the stress-test note against the text and it lands exactly. The reader's report gave soundness 8 and missed this, so treat that score as optimistic. The rest of the paper has minor issues worth noting: Lemma 2.5 is stated without proof (though elementary), and Lemmas 2.7 and 2.8 contain threshold typos (α vs α^l) that do not affect the surrounding argument. Those are fixable in revision.\n\nThe result is likely true and the proof structure may be repairable, perhaps by modifying the choice of T_i or adding a separate density argument. But as written, the main theorem is not proven.","headline":"A genuinely new result with a load-bearing proof gap: the inductive step never proves the density invariant that the maximality argument depends on.","tokens_in":8450,"tokens_out":4470,"would_cite":false,"duration_ms":35299,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C69","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph with clique number at most r can be partitioned into at most (1/ε)^{C_r} sets whose induced subgraphs are ε-sparse.","keywords":["sparse partitions","clique number","Rödl property","Erdős-Hajnal property","full pairs","epsilon-sparse"],"falsifier":"Compute, for all $0<\\alpha\\leq 1$ and $l\\geq 1$, whether the inequality $\\alpha/2 \\leq (1-\\alpha^l)^n$ can hold for some integer $n > (1/\\alpha)^{2l}$; if such an $n$ exists, the maximality argument in Lemma 2.7 fails, and the proof of Theorem 2.1 would need a different bound.","tokens_in":7420,"feed_emoji":"🧩","tokens_out":9286,"duration_ms":70427,"temperature":0.7,"pith_summary":"This paper establishes that for every integer r ≥ 2 there is a constant C_r such that any graph with clique number at most r can be partitioned into at most (1/ε)^{C_r} sets, each inducing a subgraph of maximum degree at most ε times its size, for any 0 < ε ≤ 1/2. This is the 'strong polynomial Rödl property' for complete graphs, a strengthening of the polynomial Rödl property that was previously known only for the four-vertex path P_4. The result answers a question posed by Fox, Nguyen, Scott and Seymour, who had asked whether such a polynomial bound could hold for any H beyond P_4, with the triangle as the first open case. A reader should care because it shows that extremely sparse regions can be made to cover all of a graph at once, with a number of pieces that degrades only polynomially in 1/ε.","feed_headline":"Bounded-clique graphs split into (1/ε)^{C_r} nearly empty parts","feed_subtitle":"For every r ≥ 2, any graph with clique number at most r partitions into at most (1/ε)^{C_r} ε-sparse sets.","key_machinery":"The argument rests on Lemma 2.7, a density-extraction lemma: if $B$ is $\\alpha$-dense to $A$, then one can find large subsets $A' \\subseteq A$ and $B' \\subseteq B$ such that the pair $(A',B')$ is $(\\alpha^l,\\beta,\\alpha/2)$-full, meaning that every sufficiently large subset of $A'$ has all but a $\\beta$-fraction of $B'$ being $\\alpha/2$-dense to it, with $|B'| \\geq \\beta^{(1/\\alpha)^{2l}} |B|$. This is combined with Lemma 2.6, which says that an appropriately full sequence of $r$ sets must contain a transversal $K_r$, and Lemma 2.8, which splits a large set while preserving density. The iterative proof uses these lemmas to increase the number $k$ of full sets one at a time, forcing a $K_{r+1}$ if $k$ reaches $r$.","core_discovery":"Theorem 2.1 states that for each integer $r \\geq 2$ there is a constant $C_r>0$ such that for every $0<\\varepsilon\\leq 1/2$ and every $K_{r+1}$-free graph $G$, the vertex set $V(G)$ can be partitioned into at most $(1/\\varepsilon)^{C_r}$ sets $S_1,\\dots,S_t$ with $\\Delta(G[S_i])\\leq \\varepsilon|S_i|$ for every $i$. In the terminology introduced by Fox, Nguyen, Scott and Seymour, this says that every complete graph has the strong polynomial Rödl property. The proof assumes a partition with a maximal number $k$ of 'full' sets and shows that $k$ can always be increased, forcing $k=r$ to produce a $K_{r+1}$ and contradicting the hypothesis; therefore no maximal $k<r$ can exist, and the desired partition must exist.","pith_inferences":["The method may generalize to any graph $H$ with the Erdős–Hajnal property: replace Lemma 2.6 with the analogue for $H$-free induced substructures, and the same iterative partition might yield a polynomial bound on the number of strongly $\\varepsilon$-restricted sets.","The constants $C_r$ are enormous, but the structure of the proof suggests the true minimum number of parts may be much smaller; testing small $r$ and $\\varepsilon$ computationally could reveal a sharper polynomial exponent.","The full-pair extraction lemma could have independent uses in other partitioning and density-theorem contexts, such as giving stronger discrepancy-type decompositions of graphs with forbidden induced subgraphs."],"forward_implications":["Complete graphs $K_r$ now join $P_4$ as graphs known to have the strong polynomial Rödl property, settling the first open case raised by Fox, Nguyen, Scott and Seymour.","Combined with the equivalence of the Erdős–Hajnal and polynomial Rödl properties, this gives a new class of graphs for which the polynomial Rödl property can be upgraded to the strong version.","The proof gives explicit, though large, constants $C_r$ through the recursively defined exponents $a_0,\\dots,a_{r-1}$.","The conjecture stated in the paper extends the same conclusion to every graph $H$ satisfying the Erdős–Hajnal property."],"supporting_citations":[{"why":"Raises the strong polynomial Rödl property question and proves it for $H=P_4$, the baseline this paper extends to complete graphs.","marker":"[FNSS23]"},{"why":"Establishes that $H$-free graphs partition into a bounded number of strongly $\\varepsilon$-restricted sets for every $H$, the qualitative result this paper makes quantitative.","marker":"[CSSS23]"},{"why":"Rödl's theorem supplies the original linear-sized weakly $\\varepsilon$-restricted set, the starting point for the polynomial Rödl property and its strong version.","marker":"[Rö86]"},{"why":"Conjectures the polynomial Rödl property, whose strong analogue is the property proved here for complete graphs.","marker":"[FS09]"},{"why":"The Erdős–Hajnal conjecture is the classical motivation; the polynomial Rödl property implies it, and the present paper proves the strong polynomial version for complete graphs.","marker":"[EH77]"}],"fun_headline_variants":["Bounded clique graphs have sparse partitions","Few sparse parts for any bounded-clique graph","Polynomial Rödl property for all clique-bounded graphs","Graphs with bounded clique split into sparse parts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that Lemma 2.7 remains valid when $\\beta$ is as small as $\\varepsilon^{(1/\\varepsilon)^{a_i}}$, with the maximal-$n$ argument and the inequality $n\\leq (1/\\alpha)^{2l}$ inside that lemma being the most delicate steps.","fun_headline_variants_meta":{"raw":{"variants":["Bounded clique graphs have sparse partitions","Few sparse parts for any bounded-clique graph","Polynomial Rödl property for all clique-bounded graphs","Graphs with bounded clique split into sparse parts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00018,"raw_usage":{"total_tokens":1268,"prompt_tokens":873,"completion_tokens":395,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":489,"completion_tokens_details":{"reasoning_tokens":336}},"tokens_in":489,"tokens_out":395,"duration_ms":3856,"temperature":1.0,"reasoning_tokens":336,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:43:20.341376+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for all $0<\\alpha\\leq 1$ and $l\\geq 1$, whether the inequality $\\alpha/2 \\leq (1-\\alpha^l)^n$ can hold for some integer $n > (1/\\alpha)^{2l}$; if such an $n$ exists, the maximality argument in Lemma 2.7 fails, and the proof of Theorem 2.1 would need a different bound.","supporting_citations":[],"review_version":1}