REVIEW 2 major objections 4 minor 21 references
Effectiveness and strong graph indivisibility
T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The three-graph classification of strongly indivisible graphs is effective up to computable presentation, and its least-counterexample step is exactly as strong as Sigma-0-2 induction.
desk verdict A careful, correct reverse-math analysis of Cameron's strongly indivisible graph classification; the new construction in Theorem 3.5 is the real gem. 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 load-bearing object is the partition built from a least extension failure. For a graph with no isolated or universal vertices that is not random, take the least $n$ for which some pair of disjoint finite sets $A,B$ with $|A|+|B|=n$ has no vertex correctly joined to $A$ and not joined to $B$; splitting $A\cup B$ into two nonempty pieces produces sets $X_0,X_1$ that each fail smaller extension instances, so neither can be isomorphic to the original graph. To make this effective, the paper uses a computable-presentation theorem: every computable graph has a computable copy in which the isolated vertices (and hence, by edge complementation, the universal vertices) form a computable set. The obstruction to uniform effectiveness is the graph $K_{<\omega}^\infty$, built by a stage construction whose requirements force finished copies of each $K_n$ into one side of every computable partition. The induction analysis turns on the equivalence between the existence of the least $n$ and the scheme $L\Sigma^0_2$.
What would settle it
Simulate the stage construction of Theorem 3.5 and look for a finite stage where a higher-priority requirement has claimed a vertex that a lower-priority requirement later needs; if such a collision appears, the claimed independence fails and the partition property could collapse. Alternatively, build an $\mathsf{RCA}_0$ model satisfying $\neg L\Sigma^0_2$ in which every non-random graph still has a least failing extension pair; that would directly refute Theorem 5.1.
Extended reading notes
Core claim
The central claim is that the classical three-graph classification is effective up to computable presentation. Concretely, for any computable graph $G$ not isomorphic to $K_\omega$, $\overline{K_\omega}$, or the random graph $R$, there is a computable copy $H$ of $G$ and a computable partition $H=X_0\sqcup X_1$ such that neither induced subgraph $X_0$ nor $X_1$ is classically isomorphic to $G$. This is the strongest natural effective form because the paper also constructs a computable copy of the graph $K_{<\omega}^\infty$---infinitely many disjoint copies of each finite complete graph $K_n$---for which every computable partition has at least one side classically isomorphic to the whole graph. On the reverse-mathematics side, the paper shows that the statement 'every non-random graph has a least counterexample to the extension property' is equivalent to the $\Sigma^0_2$ least-number principle $L\Sigma^0_2$, and it proves a partial version of the full theorem inside the $\omega$-model $\mathsf{REC}$ under the extra assumption that the set of vertices of finite degree is computably enumerable.
Load-bearing premise
The construction of the special graph $K_{<\omega}^\infty$ assumes that the requirements for different indices never interfere, so that no higher-priority requirement claims a vertex a lower-priority strategy needs as a parameter or extension witness; the paper states this independence informally but does not write out a full priority verification for it.
Editorial extensions
If this is right
- For every computable graph outside the three strongly indivisible types, there is a computable copy and a computable partition that witness non-indivisibility in the classical isomorphism sense.
- The special computable copy of $K_{<\omega}^\infty$ shows that no such witness can be extracted uniformly from an arbitrary presentation; sometimes the graph must first be re-presented.
- Any proof of the classification that proceeds by choosing a least counterexample to the random-graph extension property uses exactly $\Sigma^0_2$ induction, so the theorem cannot be proved in $\mathsf{RCA}_0$ by that route.
- In the $\omega$-model $\mathsf{REC}$, the classification is established for computable graphs with isolated vertices whose finite-degree vertices are c.e., leaving the general case as a precise open problem.
Reading between the lines
- If the independence claim in the $K_{<\omega}^\infty$ construction is made fully formal, the same parameter-tracking technique may transfer to other Fraïssé limits whose finite substructures have the same 'delete finitely many vertices, add disjoint copies' flexibility, suggesting that many such classifications are effective up to presentation.
- The c.e.-finite-degree hypothesis in the $\mathsf{REC}$ result looks like a genuine boundary: a counterexample to the full $\mathsf{REC}$ statement would have to be a computable graph with isolated vertices, no computable copy of the offending partition, and a non-c.e. set of finite-degree vertices.
- The equivalence of the least-extension-failure principle with $L\Sigma^0_2$ suggests that any weak-system proof of the classification must avoid minimal counterexamples entirely, perhaps by constructing a partition directly from a non-randomness witness given without a least size.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Cameron's classification of strongly indivisible countable graphs (K_omega, the completely disconnected graph, and the random graph) from the viewpoints of computability theory and reverse mathematics. Section 2 presents a classical proof of the classification and shows it can be formalized in ACA0. Section 3 proves that the classification is effective up to computable presentation: every non-special computable graph has a computable copy with a computable partition witnessing non-indivisibility, and it shows this presentation shift is necessary by constructing a computable copy of K^infinity_<omega that is indivisible with respect to all computable partitions. Section 4 gives a partial result toward the full statement in the omega-model REC for graphs with a c.e. set of finite-degree vertices. Section 5 analyzes the induction strength of Cameron's proof, claiming an equivalence over RCA0 between LSigma^0_2 and the existence of minimal counterexamples to the random-graph extension property.
Significance. If correct, the paper makes a meaningful contribution to computable combinatorics and reverse mathematics. Theorem 3.2 is a strong effectiveness result: for every computable non-special graph, a computable witness to non-indivisibility can be found up to presentation. Theorem 3.5 is a clean construction showing that this presentation dependence is unavoidable. Section 4's partial REC result is a useful step toward a difficult open question. Section 5's equivalence, if properly proved, clarifies the exact induction strength needed for Cameron's original argument. The proofs are generally detailed and constructive, and the paper gives explicit constructions rather than relying on abstract principles. The main gaps I found are in Section 5, where two key claims in the proof of the LSigma^0_2 equivalence are not justified as written.
major comments (2)
- [Section 5, proof of (1) implies (2), forward direction] The proof claims 'We claim that x_{n,t}=x' after choosing t by bounded collection. However, the t obtained only bounds the counterexample witnesses y for u<x; it does not guarantee t >= x, and x_{n,t} is defined as the least x' <= t satisfying the bounded condition, or t+1 if none exists. Thus x_{n,t} can be strictly less than x. For example, if phi(n,x,y) is (x >= 100) or (y < 1), then the least x is 100, while the bound t on the counterexamples for u<100 can be 2, giving x_{n,2}=3, not 100. The proof should instead argue that x_{n,s} eventually reaches x after finitely many increments, or choose t large enough to exceed x.
- [Section 5, proof of (1) implies (2), backward direction] The proof states 'It follows that x_{k,t} > ell for all k < m, and hence min F_{k,t} > ell for all k < m. In particular, for all s >= t and k < m, F_{k,s} is not a subset of X0.' This inference is invalid: a finite set F of size k with all elements greater than the least element of X0 can still be a subset of X0. The correct argument must use the fact that for each k < m, since not psi(k), the set F_{k,s} is redefined infinitely often, and after stage t0 the newly added vertices are distinct from the fixed finite set X0, so eventually F_{k,s} is disjoint from X0. As written, the proof does not establish that the m-extension pair <X0,X1> is active at sufficiently large stages.
minor comments (4)
- [Abstract] The abstract contains a typo: 'Cameron's theorem is is effective' should read 'Cameron's theorem is effective'.
- [Section 5] The proof uses a scheme called BSigma^0_0, but the instance being applied is bounded Sigma^0_1 collection (BSigma^0_1); the name should be corrected or the instance clarified.
- [Section 3, proof of Theorem 3.5] The verification of the construction is summarized by saying 'there is no interaction between the requirements with different indices.' A fully formal verification of the independence and of the invariants for the parameters m^e_i and C^e would make the paper more self-contained, though the construction itself appears sound.
- [Introduction] The reference to 'Ko/suppress lodziejczyck' is garbled; the intended name is Kołodziejczyk.
Circularity Check
No significant circularity: the paper's derivations are self-contained, with independent constructions and no fitted parameters or load-bearing self-citations.
full rationale
The paper's main results are proved directly rather than assumed. Cameron's classification is reproved in Section 2, and the lower-bound equivalences (Proposition 2.6 and Theorem 5.1) are established by explicit constructions rather than imported from the literature. The effectiveness result Theorem 3.2 rests on Theorem 3.3, which is independently proved by a stage construction with supporting lemmas. Theorem 3.5 is a priority construction with private components for each requirement and explicit counting of fresh vertices, and its verification is not taken from any citation. Self-citations such as [10] and [11] appear only in background discussion and do not supply load-bearing premises for the main theorems. No parameter is fitted to a target quantity and then renamed as a prediction, and no uniqueness theorem is invoked as a self-citation to force the authors' choices. The stated open question about whether REC satisfies the full classification is honestly presented as a limitation rather than disguised as a result. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- standard math RCA0 is the base subsystem of second-order arithmetic; all reverse-math comparisons are over RCA0 unless stated.
- standard math L-Sigma-0-2 is equivalent to I-Sigma-0-2 over RCA0.
- standard math The classic back-and-forth proof that any two countable random graphs are isomorphic can be formalized in RCA0.
- standard math B-Sigma-0-0 and L-Pi-0-1 are provable in RCA0.
- domain assumption All graphs in the paper are countable, with vertex set a subset of the first-order part of the model.
Cite this review
Pith. "Pith review of Effectiveness and strong graph indivisibility." pith.science (2026). https://pith.science/paper/4YKGFMKO
@misc{pith2026241116950,
author = {Pith},
title = {Pith review of: Effectiveness and strong graph indivisibility},
year = {2026},
howpublished = {\url{https://pith.science/paper/4YKGFMKO}},
note = {Machine review of arXiv:2411.16950}
}
abstract
A relational structure is \emph{strongly indivisible} if for every partition $M = X_0 \sqcup X_1$, the induced substructure on $X_0$ or $X_1$ is isomorphic to $\mathcal{M}$. Cameron (1997) showed that a graph is strongly indivisible if and only if it is the complete graph, the completely disconnected graph, or the random graph. We analyze the strength of Cameron's theorem using tools from computability theory and reverse mathematics. We show that Cameron's theorem is is effective up to computable presentation, and give a partial result towards showing that the full theorem holds in the $\omega$-model $\mathsf{REC}$. We also establish that Cameron's original proof makes essential use of the stronger induction scheme $\mathsf{I}\Sigma^0_2$.
Reference graph
Works this paper leans on
-
[1]
Tourna ments and orders with the pi- geonhole property,
Anthony Bonato, Peter Cameron and Dejan Deli´ c, “Tourna ments and orders with the pi- geonhole property,” Canadian Mathematical Bulletin 43(4), 2000, 397–405
work page 2000
-
[2]
A pigeonhole property for relational structures,
Anthony Bonato and Dejan Deli´ c, “A pigeonhole property for relational structures,” Mathe- matical Logic Quarterly 45, 1999, 409–413
work page 1999
-
[3]
On the uniform c omputational content of Ramsey’s Theorem,
Vasco Brattka and Tahina Rakotoniaina, “On the uniform c omputational content of Ramsey’s Theorem,” The Journal of Symbolic Logic 82(4), 2017, 1278–1316
work page 2017
-
[4]
Peter J. Cameron, “The random graph,” in Algorithms and Combinatorics 14, The mathe- matics of Paul Erd˝ os. II, Ronald L. Graham and Jaroslav Neˇ setˇ ril, editors, Springer-Verlag, Berlin, 1997, 333-351
work page 1997
-
[5]
On the strengt h of Ramsey’s theorem for trees,
C.T. Chong, W ei Li, W ei W ang, and Yue Yang, “On the strengt h of Ramsey’s theorem for trees,” Advances in Mathematics 39 369:107180, 2020
work page 2020
-
[6]
Reverse mathematics, com- putability, and partitions of trees,
Jennifer Chubb, Jeffry L. Hirst and Timothy H. McNicholl, “Reverse mathematics, com- putability, and partitions of trees,” The Journal of Symbolic Logic 74(1), 2009, 201–215
work page 2009
-
[7]
R everse mathematics and Ramsey’s property for trees,
Jared Corduan, Marcia J. Groszek and Joseph R. Mileti, “R everse mathematics and Ramsey’s property for trees,” The Journal of Symbolic Logic 75(3), 2010, 945–954
work page 2010
-
[8]
On uniform relationships between combinatorial problems ,
Fran¸ cois Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Jo seph R. Mileti, and Paul Shafer, “On uniform relationships between combinatorial problems ,” Transactions of the American Mathematical Society 368(2), 2016, 1321–1359
work page 2016
Show all 21 references
-
[9]
Dzhafarov and Carl Mummert, Reverse mathematics – problems, reductions, and proofs, Springer Nature, 2022
Damir D. Dzhafarov and Carl Mummert, Reverse mathematics – problems, reductions, and proofs, Springer Nature, 2022
2022
-
[10]
Ramsey’s theorem for singletons and strong computable reducibility ,
Damir D. Dzhafarov, Ludovic Patey, Reed Solomon and Lin da Brown W estrick, “Ramsey’s theorem for singletons and strong computable reducibility ,” Proceedings of the American Mathematics Society 145(3), 2017, 1343–1355
2017
-
[11]
T he tree pigeonhole principle in the W eihrauch degrees,
Damir D. Dzhafarov, Reed Solomon and Manlio Valenti, “T he tree pigeonhole principle in the W eihrauch degrees,” arXiv:2312.10535
-
[12]
Indivisibility and uniform computatio nal strength,
Kenneth Gill, “Indivisibility and uniform computatio nal strength,” arXiv:2312.03919, 2023
2023 arXiv
-
[13]
A family of countable homogeneous grap hs,
C. W ard Henson, “A family of countable homogeneous grap hs,” Pacific Journal of Mathe- matics 38(1), 1971, 69–83
1971
-
[14]
Hirschfeldt, Slicing the Truth: On the Computational and Reverse Mathema tics of Combinatorial Principles , W orld Scientific, 2014
Denis R. Hirschfeldt, Slicing the Truth: On the Computational and Reverse Mathema tics of Combinatorial Principles , W orld Scientific, 2014
2014
-
[15]
On noti ons of computable reduction between Π 1 2 principles,
Denis R. Hirschfeldt and Carl G. Jockusch, Jr., “On noti ons of computable reduction between Π 1 2 principles,” Journal of Mathematical Logic 16, 2016, article 1650002. EFFECTIVENESS AND STRONG GRAPH INDIVISIBILITY 19
2016
-
[16]
Combinator ial principles weaker than Ramey’s Theorem for Pairs,
Denis R. Hirschfeldt and Richard A. Shore, “Combinator ial principles weaker than Ramey’s Theorem for Pairs,” Journal of Symbolic Logic 72, 2007, 171–206
2007
-
[17]
Hirst, Combinatorics in Subsystems of Second Order Arithmetic , PhD thesis, Penn- sylvania State University, 1987
Jeffry L. Hirst, Combinatorics in Subsystems of Second Order Arithmetic , PhD thesis, Penn- sylvania State University, 1987
1987
-
[18]
Partition genericity and pigeonhole basis theorems,
Benoit Monin and Ludovic Patey, “Partition genericity and pigeonhole basis theorems,” The Journal of Symbolic Logic 89 (2), 2024, 829–857
2024
-
[19]
The weakness of being cohesive, thin or free in reverse mathematics,
Ludovic Patey, “The weakness of being cohesive, thin or free in reverse mathematics,” Israeli Journal of Mathematics 216(2), 2016, 905–955
2016
-
[20]
Simpson, Subsystems of second order arithmetic , Springer–Verlag, Heidelberg, 1999
Stephen G. Simpson, Subsystems of second order arithmetic , Springer–Verlag, Heidelberg, 1999
1999
-
[21]
Soare, Recursively enumerable sets and degrees , Springer–Verlag, Heidelberg, 1987
R.I. Soare, Recursively enumerable sets and degrees , Springer–Verlag, Heidelberg, 1987
1987
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.