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

Mittwoch, 11.10.2023, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

Vortragender: 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.