Speaker
Tim Seppelt, RWTH Aachen University
Title
Syntax and Semantics of Homomorphism Indistinguishability
Abstract
In 1967, Lovász proved that two graphs G and H are isomorphic iff they are homomorphism indistinguishable over the the family of all graphs, i.e. for all graphs F the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. In recent years, many natural relaxations of graph isomorphism like quantum isomorphism, cospectrality, or logical equivalences have been characterised as homomorphism indistinguishability relations over restricted graph classes.
Motivated by the wealth of such results, we set out in this talk to develop a more general theory of homomorphism indistinguishability. In particular, we aim at understanding the interplay of properties of a graph class (syntax) and its homomorphism indistinguishability relation (semantics). Concretely, we discuss:
-
how closure properties of a graph class are reflected by preservation properties of its homomorphism indistinguishability relation (arXiv:2302.11290) and
-
what graph structure theory may reveal about the semantics of homomorphism indistinguishability relations (with David Roberson, arXiv:2302.10538, ICALP 2023).
