License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.82
URN: urn:nbn:de:0030-drops-186161
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18616/
Go to the corresponding LIPIcs Volume Portal

Seppelt, Tim

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors

pdf-format:
LIPIcs-MFCS-2023-82.pdf (0.8 MB)

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. Many natural equivalence relations comparing graphs such as (quantum) isomorphism, spectral, and logical equivalences can be characterised as homomorphism indistinguishability relations over certain graph classes.
Abstracting from the wealth of such instances, we show in this paper that equivalences w.r.t. any self-complementarity logic admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. Self-complementarity is a mild property satisfied by most well-studied logics. This result follows from a correspondence between closure properties of a graph class and preservation properties of its homomorphism indistinguishability relation.
Furthermore, we classify all graph classes which are in a sense finite (essentially profinite) and satisfy the maximality condition of being homomorphism distinguishing closed, i.e. adding any graph to the class strictly refines its homomorphism indistinguishability relation. Thereby, we answer various questions raised by Roberson (2022) on general properties of the homomorphism distinguishing closure.

BibTeX - Entry

@InProceedings{seppelt:LIPIcs.MFCS.2023.82,
  author =	{Seppelt, Tim},
  title =	{{Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{82:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18616},
  URN =		{urn:nbn:de:0030-drops-186161},
  doi =		{10.4230/LIPIcs.MFCS.2023.82},
  annote =	{Keywords: homomorphism indistinguishability, graph minor, logic}
}

Keywords: homomorphism indistinguishability, graph minor, logic
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI