REVIEW 2 major objections 7 minor 7 references
Sparse Partitions of Graphs with Bounded Clique Number
T0 review · 2 major / 7 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Every graph with clique number at most r can be partitioned into at most (1/ε)^{C_r} sets whose induced subgraphs are ε-sparse.
desk verdict A genuinely new result with a load-bearing proof gap: the inductive step never proves the density invariant that the maximality argument depends on. 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 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$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [§2, proof of Theorem 2.1, the paragraph following Claim 7] 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.
- [§2, proof of Theorem 2.1, application of Lemma 2.8] 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.
minor comments (7)
- [§2, Lemma 2.5] 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.
- [§2, proof of Lemma 2.7] 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.
- [§2, Lemma 2.8] In the statement of Lemma 2.8, the hypothesis is written as '|B| ≤ (α/100)|S|' with S undefined; it should be '|B| ≤ (α/100)|A|'.
- [§2, definition of a_i] 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.
- [§2, proof of Claim 6] 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.
- [§2, proof of Lemma 2.8] 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.
- [Throughout] Typos: 'greedly' should be 'greedily' (proof of Lemma 2.4); 'Analogies' should be 'analogues' (Section 1); 'Jounal' should be 'Journal' (reference [CSSS23]).
Circularity Check
No circularity: the paper proves its theorem from scratch using explicit constants, Chernoff bounds, and elementary induction, without assuming the conclusion or fitting parameters to data.
full rationale
The paper's central claim, Theorem 2.1, is derived from first principles via a sequence of self-contained lemmas (Lemmas 2.2–2.8). The proof does not invoke any prior result that already contains the conclusion; the earlier results of Fox, Nguyen, Scott and Seymour and of Chudnovsky et al. are mentioned only as motivation and context, not as load-bearing steps. The constants C_r and the auxiliary sequence a_0,...,a_{r-1} are explicitly chosen to satisfy inequalities that are then verified within the proof, and the Chernoff bound (Lemma 2.2) is a standard external tool whose assumptions do not include the target result. The greedly applied Lemma 2.3 and the maximality argument in Lemma 2.7 are argued directly, with no hidden dependence on the theorem being proved. Even if the proof contains a gap in the invariant verification (as the skeptic's commentary suggests), that is a correctness concern, not circularity: a failed proof step is not an assumption of the conclusion. There is therefore no step where the claimed output is equivalent to an input by construction, no fitted parameter renamed as a prediction, and no self-citation chain carrying the argument. The appropriate circularity score is 0.
Assumptions & free parameters
assumptions (2)
- standard math Chernoff bound for binomial random variables (Lemma 2.2).
- ad hoc to paper Inequality (1-x)^{(1/x)^s} ≤ x^{(1/x)^{s-2}} for 0<x<1 and s≥1 (Lemma 2.5).
Cite this review
Pith. "Pith review of Sparse Partitions of Graphs with Bounded Clique Number." pith.science (2026). https://pith.science/paper/MODYPQYD
@misc{pith2026241119915,
author = {Pith},
title = {Pith review of: Sparse Partitions of Graphs with Bounded Clique Number},
year = {2026},
howpublished = {\url{https://pith.science/paper/MODYPQYD}},
note = {Machine review of arXiv:2411.19915}
}
abstract
We prove that for each integer $r\geq 2$, there exists a constant $C_r>0$ with the following property: for any $0<\varepsilon \leq 1/2$ and any graph $G$ with clique number at most $r,$ there is a partition of $V(G)$ into at most $(1/\varepsilon)^{C_r}$ sets $S_1, \dots, S_t,$ such that $G[S_i]$ has maximum degree at most $\varepsilon |S_i|$ for each $1 \leq i \leq t.$ This answers a question of Fox, Nguyen, Scott and Seymour, who proved a similar result for graphs with no induced $P_4.$
Reference graph
Works this paper leans on
-
[1]
M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Strengthening R ödl's theorem. Jounal of Combinatorial Theory, Series B , 163:256--271, 2023
work page 2023
-
[2]
P. Erd o s and A. Hajnal. On spanned subgraphs of graphs. Graphentheorie und Ihre Anwen-dungen , (Oberhof, 1977)
work page 1977
-
[3]
P. Erd o s. Some remarks on the theory of graphs . Bulletin of the American Mathematical Society , 53(4):292 -- 294, 1947
work page 1947
-
[4]
P. Erd o s and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica , 2:463--470, 1935
work page 1935
-
[5]
J. Fox, T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. II . S parse and dense sets in cographs. arXiv:2307.00801 , 2023
arXiv 2023
- [6]
-
[7]
V. Rödl. On universality of graphs with uniformly distributed edges. Discrete Mathematics , 59(1):125--134, 1986
work page 1986
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.