Graph similarities revealed through shape and space ideas
Topological and Geometric Perspectives on Homomorphism Indistinguishability
Discrete MathematicsLogic in Computer Science
Summary
The problem is to understand when two networks (graphs) look the same through the lens of how smaller patterns map into them. The paper connects this idea to shapes and spaces (topology and geometry), offering a new way to characterize when two graphs can't be told apart by counting pattern mappings. The authors also build on past work to give an alternative description of graph features based on these mappings and discuss implications for a classic problem about reconstructing graphs from parts.
What this means in practice
- •For network analysts: Improve methods to identify when two networks share structural properties by using topological and geometric characterizations of pattern mappings.
- •For graph algorithm designers: Design new algorithms that leverage topological and geometric insights to distinguish non-isomorphic graphs more effectively.
A theory result. No direct application yet.
Authors
Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson, Tim Seppelt, Gian Luca Spitzer, Peter Zeman
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.