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 from fields as diverse as quantum information theory, algebraic graph theory, convex optimisation, or category theory 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 theory of homomorphism indistinguishability. We will focus on three themes:
- Characterisations: How to characterise homomorphism indistinguishability relations in particular in terms of matrix questions such as the Sherali--Adams or Lasserre integer programming hierarchies?
- Closure: How to compare the expressiveness of homomorphism indistinguishability relations using tools from structural graph theory?
- Complexity: What is the complexity of deciding whether two input graphs are homomorphism indistinguishable over a given graph class?
Nie jesteś zalogowany |
