We introduce the 2-sorted counting logic $GC^k$ that expresses properties of hypergraphs. This logic has available k "blue" variables to address edges, an unbounded number of "red" variables to address vertices of a hypergraph, and atomic formulas E(e,v) to express that vertex v is contained in edge e. We show that two hypergraphs H, H' satisfy the same sentences of the logic $GC^k$ if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of generalised hypertree width at most k. Here, H, H' are called homomorphism indistinguishable over a class C if for every hypergraph G in C the number of homomorphisms from G to H equals the number of homomorphisms from G to H'. This result can be viewed as a generalisation (from graphs to hypergraphs) of a result by Dvorak (2010) stating that any two (undirected, simple, finite) graphs H, H' are indistinguishable by the (k+1)-variable counting logic $C^{k+1}$ if, and only if, they are homomorphism indistinguishable on the class of graphs of tree width at most k.
翻译：有界广义超树宽下的超图同态计数：逻辑特征
翻译后的摘要：
我们引入 2-sorted 计数逻辑 $GC^k$，表达超图的特征。此逻辑可用 k 个“蓝色”变量来表示边，用不受限的“红色”变量来表示超图的顶点，以及原子公式 E(e, v) 来表达顶点 v 是否包含在边 e 中。我们证明：当且仅当两个超图 $H, H'$ 在广义超树宽不超过 k 的超图类中无法辨别同态时，它们都满足逻辑 $GC^k$ 中的相同句子。这里，$H, H'$ 被称为在类 C 中无法辨别同态，当对于 C 中的每个超图 G，从 G 到 H 的同态数量等于从 G 到 $H'$ 的同态数量。此结果可视为 Dvorak（2010 年）结果的推广（从图到超图），该结果声明任何两个（无向、简单、有限）图 $H, H'$ 都可以通过（k+1）变量计数逻辑 $C^{k+1}$ 无法辨别，当且仅当它们在树宽不超过 k 的图类上无法辨别同态。
相关内容
微信扫码咨询专知VIP会员