Topological and Geometric Perspectives on Homomorphism Indistinguishability

Source abstract

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if, for every graph $F \in \mathcal{F}$, the number of homomorphisms from $F$ to $G$ is equal to the number of homomorphisms from $F$ to $H$. Lovász (Acta Mathematica Academiae Scientiarum Hungarica, 1967) showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs. Subsequently, homomorphism indistinguishability relations of a long list of natural graph classes have been equated with natural graph isomorphism relaxations. Given the wealth of such results, Atserias, Kolaitis, & Wu (LICS 2021) asked for an axiomatic characterisation of homomorphism indistinguishability relations. By exhibiting topological and geometric structure associated with homomorphism indistinguishability, we derive such an axiomatic characterisation. Here, a central ingredient is a novel characterisation of graph parameters of the form $\hom(F, \star)$ for some graph $F$ alternative to a previous result of Lovász & Schrijver (JCTA 2010). Moreover, we investigate the topology of homomorphism indistinguishability and discuss repercussions for the Ulam--Kelly Reconstruction Conjecture.