+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 29. November 2024, 11.00 Uhr Ort: Raum 9222, Gebäude E3, Informatik-Zentrum Referent: Tim Seppelt, MASt Lehrstuhl Informatik 7 Thema: Homomorphism Indistinguishability Abstract: Two graphs/G/ and/H/ are homomorphism indistinguishable over a class of graphs 𝓕 if, for all graphs/F/ ∊ 𝓕, the number of homomorphisms from/F/ to/G/ is equal to the number of homomorphisms from/F/ to/H/. In 1967, Lovász showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over the class of all graphs. Subsequently, many graph isomorphism relaxations such as quantum isomorphism, spectral, and logical equivalences have been characterised as homomorphism indistinguishability relations over certain graph classes. Thereby, homomorphism indistinguishability connects seemingly disparate fields such as quantum information, finite model theory, and machine learning. This thesis explores three themes: We first review the plenitude of *characterisations* of graph isomorphism relaxations as a homomorphism indistinguishability relation. Focusing on integer programming relaxations for graph isomorphism, we prove that the feasibility of each level of the Sherali–Adams and Lasserre hierarchies is characterised as homomorphism indistinguishability relations. These results, which are derived using (bi)labelled graphs and homomorphism tensors, shed light on the distinguishing power of these hierarchies. In particular, we determine the precise number of Sherali–Adams levels necessary such that their feasibility guarantees the feasibility of a given Lasserre level. Abstracting from the wealth of homomorphism indistinguishability characterisations, we embark on a more principled study of homomorphism indistinguishability investigating the distinguishing power and the complexity of homomorphism indistinguishability relations over minor-closed graph class. The homomorphism distinguishing*closure* cl(𝓕) of a graph class 𝓕 is the central notion for studying the distinguishing power of homomorphism indistinguishability relations. It is defined as the maximal graph class whose homomorphism indistinguishability relation coincides with the one of 𝓕. Roberson conjectured that every minor-closed union-closed graph class 𝓕 is homomorphism distinguishing closed, i.e. cl(𝓕) = 𝓕. We confirm Roberson's conjecture, which is generally wide open, for further graphs classes and prove unconditionally that if 𝓕 is minor-closed then so is cl(𝓕). Lastly, we investigate the*complexity* of deciding whether two graphs are homomorphism indistinguishable over a fixed graph class. For infinite graph classes, this problem is a priori not even decidable. In stark contrast to this, we show that, over every minor-closed graph class of bounded treewidth, homomorphism indistinguishability can be decided in randomised polynomial time. Es laden ein: die Dozentinnen und Dozenten der Informatik