Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors

Two graphs $G$ and $H$ are \emph{homomorphism indistinguishable} over a class of graphs $\mathcal{F}$ if for all graphs $F \in \mathcal{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. In this talk, the interplay of the properties of a graph class and its homomorphism indistinguishability relation are studied. As an application, \emph{self-complementarity}, a property of logics on graphs satisfied by many well-studied logics, is identified. It is proven that the equivalence over a self-complementary logic admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. Thereby, first evidences are provided for a possible connection between minors and homomorphism indistinguishability as conjectured by Roberson~(2022). Contributed talk given by Tim Seppelt

Authors

• Tim Seppelt

Keywords

No keywords are indexed for this paper.