Bi-Weekly Talk: Tim Seppelt: What is Homomorphism Indistinguishability?

Wednesday, October 11, 2023, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Speaker: Tim Seppelt


What is Homomorphism Indistinguishability?

Two graphs G and H are homomorphism indistinguishable over a class of graphs F if for all graphs F ∊ F the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. Homomorphism indistinguishability relations over certain graph classes can characterise various natural equivalence relations that compare graphs, such as (quantum) isomorphism, spectral, and logical equivalences.

Abstracting from the wealth of such instances, we show in this talk that there is a close correspondence between closure properties of the graph class F and preservation properties of the homomorphism indistinguishability relation over F. In particular, most well-studied logical equivalences admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. This result suggests that homomorphism indistinguishability relations are of a distinct nature.