+**********************************************************************
*
*
*                          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