标题： 哪些图基序参数被计数？ 显示英文标题

标题： Which graph motif parameters count?

摘要： 对于固定的图H，函数#IndSub(H,*)将图G映射到G中诱导H拷贝的数量；这个函数显然“计数某些东西”，因为它有组合解释。 这样的函数的线性组合被称为图特征参数，并在Curticapean、Dell和Marx（STOC'17）的一篇开创性论文之后最近在计数复杂性中受到了广泛关注。 我们证明，在仅涉及没有孤立顶点的图H的函数#IndSub(H,*)的线性组合中，只有那些具有正整数系数的保持组合解释。 需要注意的是，图特征参数对于所有输入G都可以是非负的，即使某些系数是负数。 形式上，我们证明在#P的一个Oracle变体中，评估任何具有负系数的图特征参数是不可能的，其中隐含的图通过Oracle查询来访问。 我们的证明遵循Hertrampf、Vollmer和Wagner（SCT'95）对#P的相对化闭包性质的分类，以及Ikenmeyer和Pak（STOC'22）开发的框架，但我们在应用所需的Ramsey定理时发现更为微妙，因为图不具有所需的Ramsey性质。 我们的技术从图推广到关系结构，包括着色图。 极大地推广这一点，我们引入了在范畴上定义的特征参数，这些参数计算范畴中子对象的出现次数。 然后我们证明了一个一般的二分定理，该定理表征了哪些此类参数具有组合解释。 利用范畴中的Ramsey理论已知结果，我们也得到了有限向量空间以及参数集的特征参数的二分法。 显示英文摘要

摘要： 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.