Metraipolis › archive › dc_fa2c39566fc5

Topological and Geometric Perspectives on Homomorphism Indistinguishability — arXiv:2610.07927

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07927
License (as archived)
CC0-1.0
Archived
2026-10-07T11:53:13.201Z
SHA-256 of the archived text
a97e79eecad0bca58d49e15a09287820128ce21243b4a0f3166754b7a9c250ad
Stable URL of this page
https://metraipolis.com/documento/dc_fa2c39566fc5

How to cite

Topological and Geometric Perspectives on Homomorphism Indistinguishability — arXiv:2610.07927 — arXiv (en), https://arxiv.org/abs/2610.07927 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fa2c39566fc5 (Metraipolis archive dc_fa2c39566fc5, sha256 a97e79eecad0bca58d49e15a09287820128ce21243b4a0f3166754b7a9c250ad)
BibTeX
@misc{dcfa2c39566fc5,
  title = {Topological and Geometric Perspectives on Homomorphism Indistinguishability — arXiv:2610.07927},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07927},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fa2c39566fc5; sha256 a97e79eecad0bca58d49e15a09287820128ce21243b4a0f3166754b7a9c250ad},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07927. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.07927 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:22:09.554Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).