Topological and Geometric Perspectives on Homomorphism Indistinguishability

Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson, Tim Seppelt, Gian Luca Spitzer, Peter Zeman

arXivarxiv/2610.07927Oct 6, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.07927
curl -X POST /api/v1/records/arxiv/2610.07927/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.07927/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'