{"id":"5bf64b23-6d81-47ad-bf5f-156b8b13f241","arxiv_id":"2507.12244","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A pure graph motif parameter has a combinatorial interpretation (lies in oracle #P) if and only if all coefficients are nonnegative integers.","lead":"This paper classifies when a linear combination of induced subgraph counts, a graph motif parameter, can be computed by counting accepting paths of a nondeterministic machine: for patterns without isolated vertices, this happens exactly when all coefficients are nonnegative integers. It generalizes the criterion to relational structures, colored graphs, finite vector spaces, and parameter sets.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 22 applies Proposition 21 with t = max_{H⊑G} φ(H), but the coloring Φ on P(~G) takes values φ(H) that can exceed t, so the Ramsey step is not valid as written.","rationale":"The reader's weakest assumption was the ordered-to-unordered transfer via Eq. (2) and the Nesetril-Rodl theorem; that transfer appears sound. The actual soft spot is a concrete mismatch in Lemma 22 between the number of colors t fixed before applying Proposition 21 and the values of the coloring Φ defined afterward. Since Φ(H) equals φ(H) for all H⊑~G, and φ is not bounded on all induced subgraphs of the Ramsey extension, the coloring can use more than t colors. This is not a matter of consensus or presentation; it is a correctness gap in a load-bearing lemma. The proposed concrete test isolates the gap with a minimal example and checks whether the standard adaptive Ramsey repair works. If the repair works, the main theorem may survive with a revised proof; hence a conditional verdict is appropriate rather than rejection. The reader's own flagged issue does not match this concern, so agreement_with_reader is disagree.","tokens_in":37633,"tokens_out":22647,"duration_ms":274116,"concrete_test":"Run the proof of Lemma 22 with φ(G) = #Ind(K2→G), G = K2, and M the natural polynomial-time NTM that guesses two ordered vertices and accepts iff the oracle reports an edge. Following the proof literally, t = max_{H⊑K2} φ(H) = 1, but for the ~G returned by Proposition 21, Φ(~G) = #E(~G) > 1, so Proposition 21 cannot be applied to Φ with t = 1. Then test the repairability: replace the single Ramsey application by an iterative construction that, for each isomorphism type F of induced subgraphs of G, applies Lemma 20 with G_current and with t equal to the maximum Φ-value on F-copies of G_current (computed after constructing the set-instantiator for G_current). If this adaptive iteration produces a G-copy whose induced subgraphs are all monochromatic, the gap is repairable; if not, the proof of Theorem 16/13 is incomplete.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Lemma 22, the proof sets t := max{φ(H) : H⊑G}, obtains ~G from Proposition 21, and then defines Φ(H) := #accM inst_SI(H)(j). Since M computes Eval_φ and inst_SI(H) differs from H only by isolated vertices, Φ(H) = φ(H) for every H⊑~G. Proposition 21, however, only applies to colorings P(~G) → {0,...,t}. The structure ~G produced by the Ramsey theorem can contain induced subgraphs whose φ-value is much larger than t: for example, if φ(G) = #Ind(K2→G) and G = K2, then t = 1, while any nontrivial ~G has many edges and hence Φ(~G) ≫ 1. Thus Φ is not a t-coloring, and the claimed conclusion that Φ is constant on isomorphic induced subgraphs of some G_Φ≅G does not follow. This gap affects Lemma 22 directly, and Lemma 22 is the core tool used to derive the contradiction in Lemma 24 and hence the hardness direction of Theorem 16 and Theorem 13. The issue is not the ordered-to-unordered transfer flagged by the reader; it is inside the ordered proof itself.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies graph motif parameters, i.e., rational linear combinations of induced subgraph counts #Ind(H→·), and asks which of them have a combinatorial interpretation, formalized as containment of their type-2 evaluation function in the class Pr-#P. The main theorem (Theorem 13) states that a pure graph motif parameter, meaning one whose patterns have no isolated vertices, is combinatorially interpretable if and only if all of its coefficients are nonnegative integers. The proof proceeds by first proving an ordered-graph version (Theorem 16), using a Ramsey theorem for ordered graphs, a probabilistic construction of set-instantiators, and a linear-algebraic witness theorem, and then reducing the unordered case to the ordered case. The framework is subsequently generalized to relational structures and, more broadly, to categories, with applications to finite vector spaces and parameter sets.","tokens_in":37907,"tokens_out":8588,"duration_ms":106354,"significance":"If Theorem 13 were established, it would be a clean and valuable classification result: it would show that nonnegative integer quantities of this form cannot be counted unless they are literal sums of induced subgraph counts, formalizing the absence of combinatorial interpretations in a way that goes beyond the existing Ikenmeyer–Pak and Hertrampf–Vollmer–Wagner frameworks. The categorical extension, if correct, would provide a broadly applicable template for such dichotomies. The paper is well structured and the overall proof architecture is appealing. However, the central proof currently contains a gap in the key Ramsey step, and this gap invalidates the main theorem and its categorical generalizations as presented.","major_comments":[{"comment":"The proof invokes Proposition 21 with t := max_{H⊑G} φ(H), then defines Φ(H) := #accM inst_SI(H)(j) for H⊑~G. Since M is assumed to compute Evalφ and inst_SI(H) differs from H only by isolated vertices, we have Φ(H)=φ(H) for every H⊑~G. But φ(H) can be strictly larger than t on induced subgraphs of the Ramsey object ~G: for example, if φ counts induced K2-copies (edges) and G=K2, then t=1, while any nonempty ~G contains induced subgraphs with many edges, so Φ(~G) is far larger than t. Thus Φ is not a coloring P(~G)→{0,...,t}, and Proposition 21 cannot be applied as written. The subsequent conclusion that Φ is constant on isomorphism types of induced subgraphs of some G_Φ≅G is therefore unsupported. Since Lemma 22 is the core tool used in Lemma 24 to derive the contradiction, this gap invalidates the proof of Theorem 16 and hence of Theorem 13.","section":"§5.2, Lemma 22"},{"comment":"The categorical analogue of Lemma 22 repeats the same error. In Lemma 43, t is set to max{φ(a) : a∈domP(b)} before the Ramsey object c is produced, and then Φ(g) := #accM inst_SI(g)(j) satisfies Φ(g)=φ(dom g) for all g∈P(c), which can exceed t. Consequently Proposition 42 is inapplicable, and the conclusion that Φ is domP(b)-good is not established. Since Lemma 43 is the engine for the lower-bound direction of Theorem 47, the vector-space dichotomy (Theorem 49) and the parameter-set dichotomy (Theorem 51) are also not established by the current proof. A repair would require a substantially different treatment of the coloring bound, not a local correction.","section":"Appendix C, Lemma 43 and Theorem 47"}],"minor_comments":[{"comment":"The second displayed equality in the blowup property reads '#SubM(a→c') = #SubM(a→c') for every a∈P', which is tautological and cannot serve as a condition; presumably it should read '#SubM(a→c') = #SubM(a→c) for every a∈P'.","section":"Appendix C, Definition 45"},{"comment":"The averaging argument over the groups labeled by the image of V(H) is not fully detailed: the groups may not have equal size under the chosen random model, so the step from 'a fraction of 1−|SI|·|V(G)|/n within each group' to the same fraction globally needs a more careful counting argument.","section":"§5.2, Lemma 19"},{"comment":"The construction of G2 by adding isolated vertices 'in between every pair of adjacent vertices' is described informally; the inequality (5) for every non-pure H∈P(G1) deserves an explicit proof, since the number of induced copies of a non-pure pattern can be sensitive to the placement of added vertices.","section":"Lemma 24"}],"recommendation":"reject","confidential_remarks":"The main theorem is not established by the submitted manuscript. The flaw in Lemma 22 is load-bearing: it sits at the very center of the proof of Theorem 16 and of Theorem 13, and the same flaw propagates to the categorical applications. The manuscript contains promising ideas and a well-written framework, but the current proof does not meet the standard required for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper is worth taking seriously, but the central proof has a gap that is not a formality. The unordered pure-graph dichotomy, the relational-structure generalizations, and the category-theoretic framework are genuinely new and well motivated. The exposition is clear, the linearization lemmas are useful, and the examples are honest. If the main theorem is true, this is a significant contribution to counting complexity and algebraic combinatorics.\n\nThe soft spot is inside the ordered proof, before the ordered-to-unordered transfer. In Lemma 22, the authors set t := max{φ(H) : H ⊑ G}, obtain ~G from Proposition 21 for that t, and then define Φ(H) := #accM instSI(H)(j). Since M computes Evalφ, Φ(H) = φ(H) for every H ⊑ ~G. But ~G is produced by the Ramsey theorem and can contain induced subgraphs whose φ-values are much larger than t. For instance, if φ counts induced edges and G = K2, then t = 1, but ~G will have many edges, so Φ(~G) is large. Proposition 21 only applies to colorings with values in {0,...,t}, so the coloring step in Lemma 22 is invalid as written. This is not the ordered-to-unordered issue; it is one step earlier, and it directly affects Lemma 24, Theorem 16, and therefore Theorem 13.\n\nThere are also minor issues: Definition 45 has an obvious typo (the second bullet should compare #SubM(a→c') with #SubM(a→c)), and the abstract's \"general dichotomy\" overstates Theorem 47, which the body correctly notes is only one-directional for arbitrary categories.\n\nThe gap in Lemma 22 might be repairable—for example by a more careful Ramsey statement that controls the growth of φ on the Ramsey object, or by a different coloring argument—but the paper does not supply such a repair. As it stands, the main theorem is not proved.\n\nI would still send this to serious referees, because the question is important, the framework is valuable, and the flaw is localized enough that a fix might exist. But I would not cite the main dichotomy as a proven result in the next year until the Ramsey step is repaired.","headline":"Important framework, but the main hardness proof has a real gap in Lemma 22: the Ramsey coloring is not bounded by t, so Theorem 13 is unproven as written.","tokens_in":38364,"tokens_out":3707,"would_cite":false,"duration_ms":49453,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","05C30","05D10","18A99"],"pacs":[],"model":"deepseek-v4-flash","headline":"Pure graph motif parameters have a combinatorial interpretation precisely when all coefficients are nonnegative integers.","keywords":["graph motif parameters","induced subgraph counts","combinatorial interpretation","counting complexity","oracle #P","Ramsey theory","relational structures","category theory"],"falsifier":"Take a pure graph motif parameter with a negative coefficient, such as the one in Example 2, and attempt to build a polynomial-time nondeterministic oracle machine that outputs its value on every oracle-encoded graph. The paper's Lemma 24 says every such machine fails on some padded graph constructed by the Witness Theorem; finding even one machine that succeeds on all of those witness graphs would refute Theorem 13.","tokens_in":37452,"feed_emoji":"🔢","tokens_out":9459,"duration_ms":99894,"temperature":0.7,"pith_summary":"The paper asks which linear combinations of induced subgraph counts can be understood as literally counting something, rather than merely evaluating to a nonnegative number. Its answer, for combinations built from patterns without isolated vertices, is that a parameter has a combinatorial interpretation exactly when all of its coefficients are nonnegative integers; any negative coefficient rules out a combinatorial interpretation even if the function is nonnegative on every graph. The negative direction is proved in an oracle model of $\\#\\mathrm{P}$ in which the input graph is accessed only by queries, and the argument forces any hypothetical counting machine to treat isomorphic induced subgraphs identically via an ordered Ramsey theorem. The same dichotomy is extended to relational structures, to colored and mixed directed structures, and through a category-theoretic framework to finite vector spaces over finite fields and to parameter sets.","feed_headline":"Only nonnegative coefficients make graph motifs count","feed_subtitle":"A pure motif parameter lies in oracle #P exactly when it is a nonnegative integer combination of induced subgraph counts.","key_machinery":"The argument is carried by three devices. A set-instantiator is a randomized padding construction that, for a fixed ordered graph $G$, embeds every induced subgraph $H\\sqsubseteq G$ as an oracle graph of the same size such that $\\varphi$ is unchanged and every accepting computation path of the machine queries exactly the vertices of $H$; this makes the machine's perception of $H$ equal to the induced subgraph it actually observes. The ordered Ramsey theorem (Lemma 20 and Proposition 21) then colors the induced subgraphs of a huge ordered graph so that the number of accepting paths becomes invariant under isomorphism, which forces the machine's local behaviour to be a nonnegative integer combination of induced-subgraph-count functions. Finally, the Witness Theorem uses linear independence of the functions $\\#\\mathrm{Ind}(H\\to\\,\\cdot\\,)$ to find a pure induced subgraph on which this locally good function disagrees with the original bad parameter. The unordered case is reduced to the ordered one by Equation (2), which expands each unordered induced-subgraph count into a sum over linear orders of the pattern. For the categorical generalizations, the same structure is recast using $M$-subobjects, a proper $(E,M)$-factorization system, a Ramsey property, and a blowup property.","core_discovery":"On the paper's own terms, the discovery is Theorem 13: if $\\varphi$ is a pure graph motif parameter, that is, a rational linear combination $\\varphi(G)=\\sum_i \\alpha_i\\,\\#\\mathrm{Ind}(H_i\\to G)$ in which every pattern $H_i$ has no isolated vertices, then $\\mathrm{Eval}_\\varphi$ lies in $\\mathrm{Pr}\\text{-}\\#\\mathrm{P}$ if and only if all coefficients $\\alpha_i$ are nonnegative integers. The forward direction is immediate, since such sums count induced occurrences with multiplicity. The theorem's content is the converse: a nonnegative-integer-valued pure parameter with a negative coefficient cannot be computed by any nondeterministic polynomial-time oracle machine, even though parameters like $(n-1)^2$ show that nonnegativity of the function does not force nonnegativity of the coefficients. The proof constructs, for any allegedly computing machine, a padded oracle graph on which the machine's accepting-path count must disagree with the value of $\\varphi$.","pith_inferences":["Editorial inference: the theorem makes coefficient negativity a general impossibility certificate; any future candidate nonnegative quantity in graph combinatorics that linearizes with a negative coefficient on a pure pattern should be abandoned as a candidate for a #P-style combinatorial interpretation, without needing a problem-specific hardness proof.","Editorial inference: the ordered-to-unordered transfer via Equation (2) is a template that may extend to other Ramsey-deficient structures, such as hypergraphs or tournaments with natural orderings, whenever signing of coefficients survives the sum over linear orders.","Editorial inference: the categorical framework suggests a concrete research direction — check which encodings of well-known Ramsey categories, such as permutation patterns or matroids, admit set-instantiators; each successful construction would yield a new dichotomy of the same shape.","Editorial inference: since the upper bound is trivial, the theorem's real content is negative; a counterexample would require an oracle machine that exploits non-isomorphic padded instantiations, which is precisely what the ordered Ramsey argument rules out for ordered structures."],"forward_implications":["The Example 2 parameter, a nonnegative sum of five induced-subgraph counts with one negative coefficient, is provably not in $\\mathrm{Pr}\\text{-}\\#\\mathrm{P}$, so it has no combinatorial interpretation in the formal sense.","The same criterion applies verbatim to relational structures, mixed relational structures with set, multiset, or list relations, and colored graphs: pure pattern sets with a negative coefficient cannot be counted.","Over finite vector spaces, a motif parameter is combinatorially interpretable exactly when it is a nonnegative integer combination of Gaussian-binomial subobject counts; over parameter sets, the same holds with Stirling-number counts.","For any category satisfying the listed conditions, the hardness half of the dichotomy holds: every bad $P$-pure motif parameter lies outside $\\mathrm{Pr}\\text{-}\\#\\mathrm{P}$, and the missing upper bound is exactly the question of whether nonnegative coefficients always give an oracle-counting procedure.","The result gives a formal negative test for combinatorial interpretability: linearize a nonnegative quantity in the induced-subgraph basis; if a negative coefficient appears on a pure pattern, no oracle counting machine can realize the quantity."],"supporting_citations":[{"why":"Introduces graph motif parameters as linear combinations of induced subgraph counts and provides the linear-independence and basis facts on which the classification is built.","marker":"[8]"},{"why":"Supplies the ordered Ramsey theorem used to make accepting-path counts invariant under isomorphism of induced subgraphs.","marker":"[29]"},{"why":"Provides the set-instantiator framework and the oracle-#P closure approach that the proof adapts from ordered graphs.","marker":"[16]"},{"why":"Classifies relativizing closure properties of #P, giving the oracle-model backdrop for the impossibility result.","marker":"[15]"},{"why":"Gives the Ramsey theorem for categories that yields the finite-vector-space dichotomy.","marker":"[12]"},{"why":"Gives the Ramsey theorem for parameter sets and documents the failure of the unordered Ramsey property for graphs.","marker":"[28]"},{"why":"Establishes the univariate binomial-basis closure result whose coefficient criterion motivates the main theorem.","marker":"[5]"}],"fun_headline_variants":["Nonnegative coefficients are the secret to graph motif counting","Negative coefficients disqualify graph motifs from #P","Graph motif counting hinges on coefficient signs","Oracle #P says no to negative graph motif coefficients","How to make graph motifs count: positive integers only"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the ordered Ramsey theorem being strong enough to survive the reduction from unordered to ordered graphs; if accepting-path counts cannot be made invariant under isomorphism through that reduction, the unordered classification does not follow from the ordered one.","fun_headline_variants_meta":{"raw":{"variants":["Nonnegative coefficients are the secret to graph motif counting","Negative coefficients disqualify graph motifs from #P","Graph motif counting hinges on coefficient signs","Oracle #P says no to negative graph motif coefficients","How to make graph motifs count: positive integers only"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000328,"raw_usage":{"total_tokens":1880,"prompt_tokens":1044,"completion_tokens":836,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":764}},"tokens_in":660,"tokens_out":836,"duration_ms":9409,"temperature":1.0,"reasoning_tokens":764,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:50:54.811975+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a pure graph motif parameter with a negative coefficient, such as the one in Example 2, and attempt to build a polynomial-time nondeterministic oracle machine that outputs its value on every oracle-encoded graph. The paper's Lemma 24 says every such machine fails on some padded graph constructed by the Witness Theorem; finding even one machine that succeeds on all of those witness graphs would refute Theorem 13.","supporting_citations":[{"cited_title":"A factorization system is called proper, if all morphisms inE are epi and all morphisms inM are mono","cited_arxiv_id":null,"evidence_quote":"Gives the Ramsey theorem for categories that yields the finite-vector-space dichotomy."}],"review_version":1}