Homomorphism indistinguishability

Seppelt, Tim Frederik; Grohe, Martin; Dell, Holger

doi:10.18154/RWTH-2024-11629

Homomorphism indistinguishability = Homomorphismen-Ununterscheidbarkeit

Seppelt, Tim Frederik^RWTH*

2024 & 2025

Verantwortlichkeitsangabevorgelegt von Tim Frederik Seppelt, Master of Advanced Study

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2025

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor)^RWTH* ; Dell, Holger (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2024-11-29

Online
DOI: 10.18154/RWTH-2024-11629
URL: https://publications.rwth-aachen.de/record/998785/files/998785.pdf

Einrichtungen

Projekte

SymSim - Symmetry and Similarity (101054974) (101054974)

Inhaltliche Beschreibung (Schlagwörter)
Lasserre hierarchy (frei) ; Sherali-Adams hierarchy (frei) ; counting logic (frei) ; graph isomorphism (frei) ; graph similarity (frei) ; treewidth (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Zwei Graphen G und H heißen Homomorphismen-ununterscheidbar über einer Graphenklasse 𝓕, wenn für all Graphen F ∊ 𝓕 gilt, dass die Zahl der Homomorphismen von F nach G gleich der Zahl der Homomorphismen von F nach H ist. Lovász zeigte 1967, dass zwei Graphen genau dann isomorph sind, wenn sie Homomorphismen-ununterscheidbar über der Klasse aller Graphen sind. Im Anschluss daran wurden zahlreiche Graphenisomorphie-Relaxationen wie Quantenisomorphie, sowie spektrale und logische Äquivalenzen als Homomorphismen-Ununterscheidbarkeits-Relationen charakterisiert. Dadurch verbindet Homomorphismen-Ununterscheidbarkeit scheinbar disparate Forschungsfelder wie Quanteninformationstheorie, Endliche Modelltheorie und Maschinelles Lernen. Diese Dissertation untersucht drei Themen: Zu Beginn geben wir einen Überblick über die Vielzahl von Charakterisierungen von Graphenisomorphie-Relaxationenals Homomorphismen-Ununterscheidbarkeits-Relationen, insbesondere von Relaxationen von ganzzahligen Programmen für Graphenisomorphie. Wir zeigen mittels bimarkierter Graphen und Homomorphismentensoren, dass die Lasserre-Hierarchie solche Charakterisierungen besitzt. Als Korollar bestimmen wir die Unterscheidungskraft dieser Hierarchie im Vergleich zur Sherali-Adams-Hierarchie. Mit dem Ziel, von der Fülle obiger Charakterisierungen zu abstrahieren, beginnen wir eine prinzipiellere Untersuchung von Homomorphismen-Ununterscheidbarkeit, insbesondere von Unterscheidungsstärke und Komplexität von Homomorphismen-Ununterscheidbarkeits-Relationen über Minoren-abgeschlossenen Graphenklassen. Der Homomorphismen-Unterscheidungs-Abschluss cl(𝓕) einer Graphenklasse 𝓕 ist der zentrale Begriff mit Hinblick auf die Unterscheidungsstärke von Homomorphismen-Ununterscheidbarkeits-Relationen. Er ist definiert als die maximale Graphenklasse, deren Homomorphismen-Ununterscheidbarkeits-Relation mit der von 𝓕 zusammenfällt. Roberson vermutete, dass jede Graphenklasse, die unter Minorenbildung und disjunkter Vereinigung abgeschlossen ist, Homomorphismen-Unterscheidungs-abgeschlossen ist, d.h. es gilt, dass cl(𝓕) = 𝓕. Wir bestätigen die Robersonsche Vermutung, die allgemein offen ist, für weitere Graphenklassen. Außerdem zeigen wir, ohne Annahme unbewiesener Aussagen, dass cl(𝓕) Minoren-abgeschlossen ist, wenn selbiges für 𝓕 gilt. Abschließend betrachten wir die Komplexität von Homomorphismen-Ununterscheidbarkeit. Wir zeigen, dass zwei Graphen in randomisierter Polynomialzeit auf Homomorphismen-Ununterscheidbarkeit über jeder Minoren-abgeschlossenen Graphenklasse beschränkter Baumweite geprüft werden können.

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.

OpenAccess:
PDF
(additional files)