Pith. sign in

REVIEW 2 major objections 3 minor 13 references

Which graph motif parameters count?

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read Pure graph motif parameters have a combinatorial interpretation precisely when all coefficients are nonnegative integers.

desk verdict 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. read the letter →

arxiv 2507.12244 v1 pith:DLBMFQZ6 submitted 2025-07-16 cs.CC math.CO

classification cs.CCmath.CO MSC 68Q1505C3005D1018A99
keywords graphmotifparametersinducedsubgraphcountscombinatorialinterpretationcountingcomplexityoracle#PRamseytheoryrelationalstructurescategory
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [§5.2, Lemma 22] 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.
  2. [Appendix C, Lemma 43 and Theorem 47] 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.
minor comments (3)
  1. [Appendix C, Definition 45] 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'.
  2. [§5.2, Lemma 19] 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.
  3. [Lemma 24] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the graph motif dichotomy is proved from explicit NTM constructions and external Ramsey theorems, with self-citations only contextual.

full rationale

The claimed dichotomy is not circular. The 'if' direction is an explicit NTM construction (Lemma 12). The 'only if' direction assumes a bad pure parameter φ and an NTM M computing Eval_φ, then derives a contradiction: Lemma 19 constructs set-instantiators by random padding; Proposition 21 (from the external ordered Ramsey Theorem 20) forces local constancy on isomorphic induced subgraphs; Lemma 22 converts this local behavior into a nonnegative-integer combination Ψ; the Witness Theorem 23 and Lemma 24 then produce a graph W with #acc_M^W(j) ≠ φ(W). All of these steps are proved in the paper except Lemma 20, which is cited to Nešetřil-Rödl and is an independent external result. The citations to Curticapean-Dell-Marx and Ikenmeyer-Pak are contextual: they supply definitions and the proof strategy, but the paper does not import the target theorem or a 'uniqueness' claim from those papers to close the argument. Equation (2) transfers ordered to unordered by a direct counting identity, not by renaming or fit. No parameter is fitted to a subset of data and then called a prediction; no quantity is defined in terms of the conclusion. Accordingly, there is no exhibited reduction of the theorem to its own inputs. Any concern about the Ramsey coloring bound in Lemma 22 would be a technical correctness issue, not a circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

There are no fitted parameters. The lower-bound proofs are self-contained modulo standard Ramsey theorems; the main modeling choice is identifying combinatorial interpretability with Pr-#P containment. The category-theoretic framework adds structural conditions rather than new objects.

assumptions (6)
  • standard math Nesetril-Rodl Ramsey theorem for ordered relational structures (Lemma 20, cited [29])
    Used in Proposition 21 and Lemma 22 to make the NTM's accepting-path counts invariant on isomorphic subgraphs; unordered graphs lack this property.
  • standard math Graham-Leeb-Rothschild Ramsey theorem for finite vector spaces ([12])
    Used to verify the M-Ramsey condition needed for the finite vector space dichotomy (Theorem 49).
  • standard math Graham-Rothschild theorem for parameter sets ([28, Thm 10.4])
    Used to establish M-Ramsey for parameter sets in Theorem 51.
  • domain assumption Type-2 oracle model with Pr-#P as formalization of combinatorial interpretability (Definitions 6-8)
    The dichotomy is about containment in a promise variant of oracle #P; the informal notion of combinatorial interpretation is used as a necessary condition.
  • standard math Linear independence of induced subgraph count functions (Fact 9)
    Guarantees uniqueness of coefficients, needed in Witness Theorems 23 and 44.
  • ad hoc to paper Conditions in Lemma 46 (well-poweredness, proper factorization system, joint M-embedding, blowup property, existence of set-instantiators)
    These are imposed to make the categorical proof go through; each application verifies them separately.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Which graph motif parameters count?." pith.science (2026). https://pith.science/paper/DLBMFQZ6

@misc{pith2026250712244,
  author       = {Pith},
  title        = {Pith review of: Which graph motif parameters count?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DLBMFQZ6}},
  note         = {Machine review of arXiv:2507.12244}
}
read the original abstract

For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interpretation. Linear combinations of such functions are called graph motif parameters and have recently received significant attention in counting complexity after a seminal paper by Curticapean, Dell and Marx (STOC'17). We show that, among linear combinations of functions #IndSub(H,*) involving only graphs H without isolated vertices, precisely those with positive integer coefficients maintain a combinatorial interpretation. It is important to note that graph motif parameters can be nonnegative for all inputs G, even when some coefficients are negative. Formally, we show that evaluating any graph motif parameter with a negative coefficient is impossible in an oracle variant of #P, where an implicit graph is accessed by oracle queries. Our proof follows the classification of the relativizing closure properties of #P by Hertrampf, Vollmer, and Wagner (SCT'95) and the framework developed by Ikenmeyer and Pak (STOC'22), but our application of the required Ramsey theorem turns out to be more subtle, as graphs do not have the required Ramsey property. Our techniques generalize from graphs to relational structures, including colored graphs. Vastly generalizing this, we introduce motif parameters over categories that count occurrences of sub-objects in the category. We then prove a general dichotomy theorem that characterizes which such parameters have a combinatorial interpretation. Using known results in Ramsey theory for categories, we obtain a dichotomy for motif parameters of finite vector spaces as well as parameter sets.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 8 canonical work pages

  1. [1]

    Set relations, i.e.Ri⊆ (V ki ) which is the kind of relational structures we have studied so far

  2. [2]

    These for example would allow us to express undirected self-loops in the graph setting

    Multiset relations, i.e.Ri is a set of multiset of vertices fromV withki total (not necessarily distinct) elements each. These for example would allow us to express undirected self-loops in the graph setting

  3. [3]

    Directed graphs without self-loops fall under this category

    List relations without repetitions, i.e.Ri is a tuple ofki vertices fromV, but without repetitions. Directed graphs without self-loops fall under this category. M. Bläser, R. Curticapean, J. Dörfler, C. Ikenmeyer 23

  4. [4]

    27 Saunders Mac Lane.Categories for the Working Mathematician, volume 5

    URL: https://publishup.uni-potsdam.de/frontdoor/index/index/docId/64603, doi:10.25932/PUBLISHUP-64603. 27 Saunders Mac Lane.Categories for the Working Mathematician, volume 5. Springer Science & Business Media, 1998. 28 Jaroslav Nešetřil. Ramsey theory. InHandbook of Combinatorics, volume 2, pages 1331–1403. Elsevier Science B.V., Amsterdam, 1995. 29 Jaro...

  5. [10]

    Directed graphs with self-loops fall under this category

    List relations with repetitions, i.e.Ri is a tuple ofki elements fromV with repetitions. Directed graphs with self-loops fall under this category. We can even allow different relations to be of different variants. We call such an (ordered) relational structure a mixed (ordered) relational structure. A mixed type ~∆ is now a type ∆, combined with the infor...

  6. [11]

    This factorization is unique, up to a unique isomorphism, i.e

    Every morphismf :a→b factors asf =me with e∈E and m∈M . This factorization is unique, up to a unique isomorphism, i.e. if there is some other factorizationf =m′e′ with e′∈E and m′∈M , then there is a unique isomorphismg such that the following diagramm commutes: a • • b e e′ m m′ g 5 These coproduct injections do not have to be injective, nor mono M. Bläs...

  7. [12]

    A factorization system is called proper, if all morphisms inE are epi and all morphisms inM are mono

    BothE andM contain all isomorphisms and are closed under composition. A factorization system is called proper, if all morphisms inE are epi and all morphisms inM are mono. One example of such a factorization system in the category of finite undirected graphs is given by choosingE as the (vertex) surjective graph homomorphisms, andM as the strong graph emb...

  8. [13]

    the”n-parameter setAn and “the

    For each subspaceW⊆V, all accepting paths of the computation#accMh(W)(pd) do not query the oracle for any vectors inh(V\W ). If each of these events (we count property 2 individually for each of the finitely many subspaces) happens with high probability with growingd, then eventually there is anh fulfilling all of them. For now, fix some subspaceW⊆V. Furt...

Show all 13 references
  1. [1991]

    19 Mark Jerrum and Kitty Meeks

    URL: https://www.sciencedirect.com/science/article/pii/002240499190099N, doi:10.1016/0022-4049(91)90099-N. 19 Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs.J. Comput. Syst. Sci., 81(4):702–716, 2015. doi:10.1016/j.jc...

  2. [1995]

    3 Richard Beigel

    doi:10.1109/SFCS.1995.492671. 3 Richard Beigel. Closure properties of GapP and #P. In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 144–146. IEEE, 1997. 4 Andrei Z Broder. The r-stirling numbers.Discrete Mathematics, 49(3):241–259, 1984. ...

  3. [2019]

    doi:10.22028/D291-28348. M. Bläser, R. Curticapean, J. Dörfler, C. Ikenmeyer 19 38 Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting small induced subgraphs satisfying monotone properties. In61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Dur...

  4. [2020]

    39 Marc Roth, Johannes Schmitt, and Philip Wellnitz

    doi:10.1109/FOCS46700.2020.00128. 39 Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and counting small subgraphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders. In48th International Colloquium on Automa...

  5. [2024]

    12 RL Graham, K Leeb, and BL Rothschild

    doi:10.1145/3618260.3649644. 12 RL Graham, K Leeb, and BL Rothschild. Ramsey’s theorem for a class of categories.Advances in Mathematics, 8(3):417–433, 1972. 13 Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Texts in Theoretical Computer Science. ...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.