Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation

03/20/2023
by   Benjamin Scheidt, et al.
0

We introduce the 2-sorted counting logic GC^k that expresses properties of hypergraphs. This logic has available k variables to address hyperedges, an unbounded number of variables to address vertices, and atomic formulas E(e,v) to express that a vertex v is contained in a hyperedge 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset