Topological and Geometric Perspectives on Homomorphism Indistinguishability
Abstract
Two graphs G and H are homomorphism indistinguishable over a graph class ℱ if, for every graph 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, ⋆) 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.
Related
- Smoothing topological isotopy of surfaces in 4-manifolds with a boundary geometric dual
- Étale Fundamental Groups: a geometric and topological approach to fundamental groups in algebraic geometry
- Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives
- Graph Models of Cultural M-Grams: Polygonal Number Networks, Topological Index Partitions, and Geometric Transformations
- Quantale-Valued Tolerance Convergence Function Spaces: Topological and Cartesian-Closed Categorical Perspectives
BibTeX
@misc{bruyn2026topological,
title = {{Topological and Geometric Perspectives on Homomorphism Indistinguishability}},
author = {Josse van Dobben de Bruyn and Jérémie Marquès and David E. Roberson and Tim Seppelt and Gian Luca Spitzer and Peter Zeman},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07927},
eprint = {2610.07927},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07927},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Topological and Geometric Perspectives on Homomorphism Indistinguishability
AU - Josse van Dobben de Bruyn
AU - Jérémie Marquès
AU - David E. Roberson
AU - Tim Seppelt
AU - Gian Luca Spitzer
AU - Peter Zeman
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07927
UR - https://arxiv.org/abs/2610.07927
AB - Two graphs G and H are homomorphism indistinguishable over a graph class ℱ if, for every graph 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, ⋆) 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.
ER -