{"id":"9e75d84d-e99b-405d-90c7-f0011068bca7","arxiv_id":"2411.16950","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper shows Cameron's classification of strongly indivisible graphs is effective up to a change of computable presentation, partially holds in the omega-model REC, and requires the induction scheme I-Sigma-0-2 in Cameron's original proof.","lead":"This paper studies a 1997 theorem of Cameron that says only three kinds of countable graphs are strongly indivisible: the complete graph, the completely disconnected graph, and the random graph. Using computability theory and reverse mathematics, the authors determine how much logical power is needed to prove this theorem and build computable counterexamples when a graph is not one of the three.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The paper's main claim is Theorem 3.2, which requires Theorem 3.3 (a computable copy with computable isolated vertices) and the classical partition argument. I checked Theorem 3.3: the construction of the Δ^0_2 isomorphism and the lemmas showing edges stabilize and each natural is eventually hit are sound. Theorem 3.5, used to show a presentation change is necessary, has the only non-fully-formal verification, but the informal independence claim is supported by the disjoint-component structure and the exact counting of fresh vertices. The reader's weakest assumption is not a real defect. I also noted a probable typo in Section 5 (the least element of X0 should likely be the greatest), but this is in a secondary reverse-math result and is easily corrected; it does not affect the effectiveness claims. Hence no verdict change.","tokens_in":19205,"tokens_out":30972,"duration_ms":282364,"concrete_test":"Formalize the stage-by-stage verification of Theorem 3.5: prove by induction that (i) each C^e is a finite clique, (ii) C^e and C^{e'} are disjoint for e≠e', and (iii) at every stage the number of unused fresh vertices made available equals the number of requirements whose current max C^e has halted. If (i)-(iii) hold, the 'no interaction' assertion is justified and the R_e requirements are independent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a careful check of Theorem 3.5, the suspected interaction between requirements does not arise. Each requirement R_e owns its private component C^e; vertices are never reassigned, and at a given stage a fresh vertex is attached only to the current C^e of the requirement being processed. Components for different e are therefore pairwise disjoint and no edge ever connects them. The count k = π1(s)+2+|H_s| in the formal construction provides exactly one new vertex for the new clique, one to initialize C^s, and one for each e with Φ_{e,s}(max C^e) halting, so no requirement can be starved by higher-priority ones. Within a single requirement, the size argument before reaching π1(m^e_0)+π1(m^e_1)+2 guarantees the C^e component remains finite and restarts infinitely often if Φ_e is total. The rest of Theorem 3.2 is supported by the independently checkable Theorem 3.3 construction. I therefore find no load-bearing gap; the paper's central effectiveness claim is secure.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":29,"tokens_out":24747,"duration_ms":843425,"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":[{"comment":"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":"Section 5, proof of (1) implies (2), forward direction"},{"comment":"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.","section":"Section 5, proof of (1) implies (2), backward direction"}],"minor_comments":[{"comment":"The abstract contains a typo: 'Cameron's theorem is is effective' should read 'Cameron's theorem is effective'.","section":"Abstract"},{"comment":"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":"Section 5"},{"comment":"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.","section":"Section 3, proof of Theorem 3.5"},{"comment":"The reference to 'Ko/suppress lodziejczyck' is garbled; the intended name is Kołodziejczyk.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The central effectiveness results (Theorems 3.2, 3.3, and 3.5) and the partial REC result (Theorem 4.1) appear correct and well-supported. The main weakness is in Section 5, where two steps in the proof of Theorem 5.1 contain assertions that are false as stated. Both issues are local and repairable, but they affect a result advertised in the abstract. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is one of those papers that does exactly what it says, without overclaiming. It gives the first effective and reverse-mathematical analysis of Cameron's 1997 classification of strongly indivisible countable graphs. The main results are new: Theorem 3.2 shows that every computable non-strongly-indivisible graph has a computable copy with a computable partition witnessing non-indivisibility (up to classical isomorphism, on both sides). Theorem 3.5 shows the presentation change is necessary: there is a computable copy of K_∞_<ω such that every computable partition leaves one side classically isomorphic to the whole. That construction is the most interesting thing in the paper. Theorem 4.1 is a genuinely partial result toward proving the classification in REC, under a c.e. finite-degree hypothesis, and the paper is explicit that the full question remains open. Theorem 5.1 calibrates the induction strength: the existence of a minimal counterexample to the random graph extension property is equivalent to LΣ^0_2 over RCA0.\n\nThe proofs are detailed and, as far as I can tell, correct. I checked the one spot that looked soft: the 'no interaction between requirements' claim in Theorem 3.5. The stress-test note is right. Each requirement works on its own private component, vertices are never reassigned, and the counting at each stage gives each active requirement fresh vertices. So that informal justification holds up.\n\nSoft spots are minor. The verification in Theorem 3.5 is compressed; the formal construction is given, but the proof that the requirements are independent is more of a sketch. A referee should ask for that to be expanded, but it's not a gap. There are some typos in the arXiv version, including a mangled name in the introduction, but nothing mathematical. Section 5 is the most self-contained and is a nice piece of work.\n\nWho is this for: computable combinatorics and reverse mathematics readers, especially anyone working on indivisibility or pigeonhole principles. It's not a blockbuster but it is solid and it settles some natural questions while leaving the right open question visible.\n\nI'd send it to a serious referee. The priority argument in Theorem 4.1 is intricate enough to warrant careful checking, and the paper deserves to be in the literature.","headline":"A careful, correct reverse-math analysis of Cameron's strongly indivisible graph classification; the new construction in Theorem 3.5 is the real gem.","tokens_in":19929,"tokens_out":2364,"would_cite":true,"duration_ms":20085,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03D80","03B30","05C63"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["strong indivisibility","random graph","computable presentation","computable partition","reverse mathematics","Sigma-0-2 induction","pigeonhole property","infinite graphs"],"falsifier":"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.","tokens_in":18990,"feed_emoji":"🕸️","tokens_out":8269,"duration_ms":74692,"temperature":0.7,"pith_summary":"A countable graph is strongly indivisible if every partition of its vertices into two sets leaves one of the two induced subgraphs isomorphic to the original graph. The complete graph, the completely disconnected graph, and the random graph are the only countable graphs with this property, and this paper asks how much logical power that classification needs. The paper proves that every computable graph outside the three exceptional types has a computable copy with a computable partition whose two sides are not even classically isomorphic to the original graph, making the classification effective up to presentation. It also shows that a particular presentation of one non-exceptional graph can resist every computable partition, so changing presentation is genuinely necessary, and that the classical proof's least-counterexample step is equivalent to the $\\Sigma^0_2$ induction scheme. The full question of whether the classification holds in the $\\omega$-model of computable sets remains open except for graphs whose finite-degree vertices are c.e.","feed_headline":"Only three countable graphs are strongly indivisible; the rest split effectively","feed_subtitle":"A computable graph outside the exceptional types has a computable copy and partition witnessing non-indivisibility.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the classification theorem (three strongly indivisible countable graphs) whose effective content is the subject of the paper.","marker":"[4]"},{"why":"Supplies the fact that a random graph has a color class isomorphic to itself, the indivisibility direction extended here.","marker":"[13]"},{"why":"Provides the Weihrauch-style study of indivisible structures that motivates the effectiveness questions addressed.","marker":"[12]"},{"why":"Gives the tree pigeonhole principle and its induction-strength analysis, the comparison point for the $\\Sigma^0_2$ induction result.","marker":"[11]"},{"why":"Establishes the $\\mathsf{RT}^1$/$B\\Sigma^0_2$ equivalence used as the baseline induction benchmark in the introduction.","marker":"[17]"}],"fun_headline_variants":["Three graph types stand, rest split computably","Effective splitting for all but three countable graphs","Computable partition splits every non-exceptional graph","Cameron's indivisibility trichotomy made computable","Only K_omega, empty, random resist computable splitting"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Three graph types stand, rest split computably","Effective splitting for all but three countable graphs","Computable partition splits every non-exceptional graph","Cameron's indivisibility trichotomy made computable","Only K_omega, empty, random resist computable splitting"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000847,"raw_usage":{"total_tokens":3679,"prompt_tokens":935,"completion_tokens":2744,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":2667}},"tokens_in":551,"tokens_out":2744,"duration_ms":21562,"temperature":1.0,"reasoning_tokens":2667,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:42:15.649076+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The random graph,","cited_arxiv_id":null,"evidence_quote":"Supplies the classification theorem (three strongly indivisible countable graphs) whose effective content is the subject of the paper."},{"cited_title":"A family of countable homogeneous grap hs,","cited_arxiv_id":null,"evidence_quote":"Supplies the fact that a random graph has a color class isomorphic to itself, the indivisibility direction extended here."},{"cited_title":"Indivisibility and uniform computational strength","cited_arxiv_id":"2312.03919","evidence_quote":"Provides the Weihrauch-style study of indivisible structures that motivates the effectiveness questions addressed."},{"cited_title":"The tree pigeonhole principle in the Weihrauch degrees","cited_arxiv_id":"2312.10535","evidence_quote":"Gives the tree pigeonhole principle and its induction-strength analysis, the comparison point for the $\\Sigma^0_2$ induction result."},{"cited_title":"Hirst, Combinatorics in Subsystems of Second Order Arithmetic , PhD thesis, Penn- sylvania State University, 1987","cited_arxiv_id":null,"evidence_quote":"Establishes the $\\mathsf{RT}^1$/$B\\Sigma^0_2$ equivalence used as the baseline induction benchmark in the introduction."}],"review_version":1}