Pith. sign in

REVIEW 3 major objections 2 minor 12 references

A complete graph edge-colored with any number of colors, where no color contains an induced complete join of graphs chosen from a bounded list, admits a bounded cover of its vertices by sets that each exclude a listed graph in some color.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 10:20 UTC pith:2XJUID62

load-bearing objection A natural multicolor CSS generalization, but Lemma 2.3 has a concrete false inequality at (1,3) that breaks the main proof; needs revision before it can be cited as a theorem. the 3 major comments →

arxiv 2606.24695 v2 pith:2XJUID62 submitted 2026-06-23 math.CO

Forcing monochromatic induced subgraphs

Sepehr Hajebi , Sophie Spirkl This is my paper
classification math.CO MSC 05C5505C1505D10
keywords multicolor edge-colored complete graphsinduced subgraphscomplete joinpure pairsbisequence methodsparse pairscovering theoremsstructural graph theory
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a common generalization of the classical multicolor theorem for complete subgraphs and the two-color 'excluding pairs of graphs' theorem. It shows that for any number c of colors, any graph-size bound h, and any list of up to t graph classes assigned to each color, if a c-multicoloring of a complete graph has no induced copy of a complete join whose parts are chosen from the color's list, then the vertex set is the union of a bounded number of sets n = c^{τ c(t−1)}−1. Each such set is either a single vertex or, in some color, induces a graph that excludes at least one graph from that color's list as an induced subgraph. The theorem allows colors to overlap and lists to differ per color, and it yields improved bounds for a Ramsey-type application on K_{b,b}-free graphs.

Core claim

The central claim (Theorem 1.4) is the following. Let c,h,t ≥ 2 and set n = c^{τ c(t−1)}−1 where τ = 2 c^{3cht} − c^{3ct}. Let (G_1,…,G_c) be a c-multicoloring of E(K_V) such that for each i, the graph G_i has no 'L_i-complete' induced subgraph, where L_i is a list of at most t nonempty classes of nonnull graphs on at most h vertices. Then V is the union of n sets V_1,…,V_n such that for each j, either |V_j|=1, or there is an i for which G_i[V_j] is H-free for some graph class H from L_i. This is the multicolor, overlapping-color, list version of the earlier two-color 'excluding pairs of graphs' theorem: when h=1 it contains the classical multicolor complete-subgraph theorem with the same bo

What carries the argument

The proof's engine is a measure-theoretic lemma that, in any c-multicolored complete graph whose color graphs each forbid a fixed graph H_i, finds two large disjoint subsets that are 'sparse' in some color—each vertex of one set has few neighbors in the other. To get there, the proof introduces two bisequences δ and ε defined recursively over pairs of natural numbers, and a notion of 'tenacity' measuring the maximum depth of a chain of subset refinements that make pairs sparse in distinct colors. It shows the tenacity is always less than c, guaranteeing a spare color, then applies a large-sparse-pair lemma of the pure-pair type to extract the required structure. The main theorem follows by i

Load-bearing premise

The argument depends on a set of numerical inequalities (the bisequence bound ε≤min{δ^c/c,1/h,η}) that force the shrinking process to always have a spare color, and the h=1 base case is delegated to the classical theorem with the overlapping-color adjustment left to the reader; if either fails, the induction collapses.

What would settle it

Find an explicit c-multicoloring of a complete graph with more than c^{τ c(t−1)}−1 vertices in which every color avoids all listed complete joins, yet any cover by 'H-free in some color or singleton' sets needs more than n sets—such a construction would refute the theorem. A cheaper check is to write out the h=1 overlapping-colors base case: if that adjustment fails for some two-color overlapping example, the induction lacks a foundation.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • It simultaneously unifies the single-vertex (complete-subgraph) case with the two-color complete-join case, so any future improvement of the cover bound applies to both settings.
  • Because colors are allowed to overlap, the result covers edge-coverings of complete graphs, not just partitions, which is exactly what the K_{b,b}-free application needs.
  • The bound n is explicit; in particular, the h=1 case recovers the classical bound c^{c(t−1)} with τ=1.
  • The application (Theorem 1.5) turns a prior tower-type bound into the bounds of Theorem 1.4 in an 'α-strengthened' hitting-set/anticomplete-sets dichotomy for K_{b,b}-free graphs.
  • The theorem provides a structural dichotomy: either a set is trivial or some color graph on it is H-free for a listed H—this is the natural 'simplicity' notion in this multi-color context.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • It is plausible the explicit bound n is far from optimal; the bisequence recursion suggests the true growth might be single or double exponential rather than the triple exponential appearing here, and the proof's numerical slack could likely be tightened.
  • The overlapping-color feature suggests a compactness or limit statement: for infinite edge-covered complete graphs with the same local avoidance, pieces might be refined to a finite covering in the limiting object.
  • One testable extension is to drop the 'nonnull' restriction or the vertex-count bound h on the listed graphs; the proof as written uses h only in the size of the sets and in the induction, so a version for hereditary classes of graphs with bounded 'dimension' might be within reach.
  • The h=1, overlapping-colors step is delegated to the classical theorem with a small adjustment left to the reader; verifying that adjustment explicitly (and testing it on a two-color overlapping example) is a concrete way to confirm the foundation of the induction.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 2 minor

Summary. The paper states and attempts to prove a multicolor, overlapping-color, list version of the Chudnovsky–Scott–Seymour theorem (Theorem 1.4). The proof strategy is to establish a measure-theoretic sparse-pair lemma (Lemma 2.3), use Ramsey's theorem to select a fixed color and a large index set, and then prove by induction on the total number of excluded graphs that the vertex set can be covered by few simple pieces. An application to an α-strengthening of a Ramsey-type result is given in Theorem 1.5, with proofs in the appendix.

Significance. If the result were correct, it would be a genuine common generalization of Ramsey's theorem and the Chudnovsky–Scott–Seymour theorem, and the application to tree-independence-type results would be of interest. The paper also contains useful structural ideas, especially Lemma 2.1 and Lemma 2.2. However, the proof as written has several serious technical gaps, two of which are in the central Lemma 2.3 and one in the application proof.

major comments (3)
  1. [Lemma 2.3, inequality (2)] Inequality (2) is false at the second pair in co-lex order, (p,q)=(1,3). Since π_{δ^c}(1,3)=1 and π_ε(1,3)=ε(1,2)=1/b, the recursion gives δ(1,3)=1/b and ε(1,3)=1/b^c. Hence ε(1,3)=δ(1,3)^c, which is strictly larger than δ(1,3)^c/c for c≥2. The proof of (3) explicitly uses the factor 1/c to conclude each color class occupies less than μ(Y_c)/c, so the tenacity bound is not established for (1,3). Since the backward recursion over I processes (1,3), this is load-bearing. A weaker inequality such as ε≤δ^{c-1}/c would suffice for (3), so the issue may be locally repairable, but as written the proof is incomplete.
  2. [Lemma 2.3, proof of (7)] The proof of (7) does not follow from the preceding estimate. The induction proves e_i≤(2c+2)^{i-2}. For i=binom(n,2)+1 this gives 1/δ(1,n+1)≤b^{(2c+2)^{\binom{n}{2}-1}}. The hypothesis on a in Lemma 2.3 is only a≥b^{(2c+2)\binom{n}{2}-1}. These quantities differ vastly for large n; with the choices in Theorem 1.4, a=b^{(2c+2)\binom{c^{cht}}{2}}, while the required lower bound is exponential in \binom{n}{2}. Thus the assertion a≥1/δ(1,n+1) is unsupported, and the final step μ(X),μ(Y)≥β collapses. This is a second, independent load-bearing gap: either a must be made exponentially larger, which would destroy the estimate λ<c^τ in (8), or the growth of δ must be controlled polynomially, which the recurrence does not do.
  3. [Theorem 1.5, proof of (13)] In the application of Theorem 1.4, the proof defines X_j={v_{i_j,T}:T∈T_j}. For i_j∈{k+1,...,c-1}, the vertices v_{i_j,T} are undefined, because the enumerations v_{i,S} are only defined for i≤k. Moreover, the assertion that the third outcome implies |T_j|≤b is false: G_{i_j} is edgeless, and an edgeless graph is K_b-free for arbitrarily large T_j. This invalidates the construction of the hitting set X in Theorem 1.5 as written. One possible repair is to use, for colors i>k, a list of t copies of K_1 so that T_j is forced to be empty, but this needs to be stated and the proof adjusted.
minor comments (2)
  1. [Theorem 1.4, h=1 paragraph] The sentence 'τ=1' is false: the displayed formula gives τ=2c^{3cht}-c^{3ct}=c^{3ct} when h=1. The h=1 case still follows from Theorem 1.1 with a much better bound, but the explanation should be corrected.
  2. [Lemma 2.3, notation] The condition α+βa≤c^{-ch} is used as α+β·a, but the typography could be misread as β^a. Please clarify the intended meaning in the displayed statement.

Circularity Check

0 steps flagged

No circularity: the main theorem is proved from external Ramsey theory and structural lemmas; self-citations are not load-bearing.

full rationale

Theorem 1.4 is derived by induction using Lemmas 2.1-2.3. Lemma 2.3's proof invokes Ramsey's theorem (Theorem 1.1) and the given H_i-free hypotheses; its sparse-pair conclusion is not the theorem's conclusion and is not fed back as an assumption. The h=1 case is delegated to Ramsey's theorem, an external benchmark, so no circularity arises. Self-citations [10] and [2] appear only in the application section and context; Theorem 1.5's proof is included in the appendix rather than resting on [10]. Two defects found in the text are correctness, not circularity: (i) the assertion in the h=1 case that tau=1 is numerically false (for h=1, tau=c^{3ct}), and the overlapping-colors adjustment is left to the reader; (ii) the skeptic's check of Lemma 2.3 shows inequality (2) fails at (p,q)=(1,3) because epsilon(1,3)=1/b^c > delta(1,3)^c/c, so the tenacity bound (3) is unsupported at that pair. Neither defect is a case of defining a quantity in terms of the target, renaming an empirical pattern, or fitting a parameter and calling it a prediction; consequently the circularity score remains 0.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

No fitted constants or new entities. The auxiliary numbers b,a,λ,α,β are explicit functions of the input c,h,t chosen to satisfy the inequalities in Lemma 2.3; they are not fit to data. Self-cited works [10] and [2] are cited as context and application, not as proof dependencies.

axioms (3)
  • standard math Ramsey's theorem (Theorem 1.1) with the explicit bound n≥c^{c(t−1)}.
    Used in Lemma 2.3(5) to find an (h+1)-subset L all of whose pairs avoid a color, and in the appendix and h=1 case.
  • standard math The subadditive 'space' axioms for μ: μ(∅)=0, μ(Ω)=1, and μ(X)≤μ(Y)+μ(Z) whenever X⊆Y∪Z.
    Defines the measure framework; Lemma 2.2 and the measure-chain arguments (4)–(7) rely on it.
  • domain assumption Multicoloring model: E(G_1)∪...∪E(G_c)=E(K_V), so every edge receives at least one color.
    This is the stated object of study; the proof uses that the neighborhood of any vertex in Y_c is covered by the c color graphs.

pith-pipeline@v1.3.0-alltime-deepseek · 15189 in / 31414 out tokens · 288047 ms · 2026-08-02T10:20:48.077745+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Forcing monochromatic induced subgraphs." pith.science (2026). https://pith.science/paper/2XJUID62

@misc{pith2026260624695,
  author       = {Pith},
  title        = {Pith review of: Forcing monochromatic induced subgraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2XJUID62}},
  note         = {Machine review of arXiv:2606.24695}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We prove that for all $c\in\mathbb N$ and nonnull graphs $H_1,\ldots,H_t$, there exists $n\in\mathbb N$ such that if $G$ is a $c$-edge-colored complete graph with no monochromatic induced copy of the complete join of $H_1,\ldots,H_t$, then $V(G)$ is the union of $n$ sets $V_1,\ldots,V_n$ such that within each set $V_j$ with $|V_j|\neq 1$, the edges of some color form a graph that excludes at least one of $H_1,\ldots,H_t$ as an induced subgraph. In fact, the same holds even if the colors overlap, and with a different list of graphs $H_1,\ldots,H_t$ assigned to each color. When $H_1,\ldots,H_t$ each have a single vertex, this is Ramsey's theorem, and when $c=2$, this is the "excluding pairs of graphs" theorem of Chudnovsky, Scott, and Seymour.

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 2 linked inside Pith

  1. [1]

    Balister, B

    P. Balister, B. Bollobás, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, and M. Tiba. Upper bounds for multicolour Ramsey numbers.J. Amer. Math. Soc., 39(3):765–780, 2026

    2026

  2. [2]

    Chudnovsky, J

    M. Chudnovsky, J. Codsi, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions XIX. Thetas and trees. Manuscript available athttps://arxiv.org/abs/2506.05602, 2025

    arXiv 2025

  3. [3]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, and P. Seymour. Excluding pairs of graphs.J. Combin. Theory Ser. B, 106:15–29, 2014

    2014

  4. [4]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Pure pairs. I. Trees and linear anticomplete pairs.Adv. Math., 375:107396, 20, 2020

    2020

  5. [5]

    Dallard, M

    C. Dallard, M. Krnc, O. Kwon, M. Milanič, A. Munaro, K. Štorgel, , and S. Wiederrecht. Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star. Manuscript available athttps://arxiv.org/abs/2402.11222, 2024

    Pith/arXiv arXiv 2024

  6. [6]

    Dallard, M

    C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. II. Tree-independence number.J. Combin. Theory Ser. B, 164:404–442, 2024

    2024

  7. [7]

    Erdős and A

    P. Erdős and A. Hajnal. Ramsey-type theorems. volume 25, pages 37–52. 1989. Combinatorics and complexity (Chicago, IL, 1987)

    1989

  8. [8]

    R. L. Graham and B. L. Rothschild. Ramsey’s theorem forn-parameter sets.Transactions of the American Mathematical Society, 159:257–292, 1971

    1971

  9. [9]

    S. Hajebi. Induced subdivisions with pinned branch vertices.European J. Combin., 124:Paper No. 104072, 2025

    2025

  10. [10]

    Hajebi and S

    S. Hajebi and S. Spirkl. Tree-independence number and excluding finitely many graphs. Manuscript available athttps://arxiv.org/abs/2605.01223, 2026

    Pith/arXiv arXiv 2026

  11. [11]

    Lozin and I

    V. Lozin and I. Razgon. Tree-width dichotomy.European J. Combin., 103:Paper No. 103517, 8, 2022

    2022

  12. [12]

    F. P. Ramsey. On a Problem of Formal Logic.Proc. London Math. Soc. (2), 30(4):264–286, 1929. FORCING MONOCHROMATIC INDUCED SUBGRAPHS 13 Appendix: Proof of Theorem 1.5 For completeness, let us first give a proof of the explicit bound in Theorem 1.1: Theorem 1.1(Ramsey [12]).For allc, t∈Nwithc≥2and every integern≥c c(t−1), everyc-coloring ofE(K n)contains a...

    1929