Metraipolis › archive › dc_a3f29c461e2d

Distinguishing graphs with simple spectrum by homomorphism counts — arXiv:2610.09042

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09042
License (as archived)
CC0-1.0
Archived
2026-10-08T12:43:50.437Z
SHA-256 of the archived text
f9427ec22d5a6f18d875b67fb22dfd934d4d8c50f86562b35cc826e073bd33cd
Stable URL of this page
https://metraipolis.com/documento/dc_a3f29c461e2d

How to cite

Distinguishing graphs with simple spectrum by homomorphism counts — arXiv:2610.09042 — arXiv (en), https://arxiv.org/abs/2610.09042 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a3f29c461e2d (Metraipolis archive dc_a3f29c461e2d, sha256 f9427ec22d5a6f18d875b67fb22dfd934d4d8c50f86562b35cc826e073bd33cd)
BibTeX
@misc{dca3f29c461e2d,
  title = {Distinguishing graphs with simple spectrum by homomorphism counts — arXiv:2610.09042},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09042},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a3f29c461e2d; sha256 f9427ec22d5a6f18d875b67fb22dfd934d4d8c50f86562b35cc826e073bd33cd},
  year = {2026}
}

Archived text

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

We study which graph classes determine every graph with simple spectrum up to isomorphism by homomorphism counts from their members. We show that such a class has unbounded treewidth and Euler genus and contains a graph with the complete graph on seven vertices as a minor. To prove these conditions, we construct pairs of non-isomorphic cospectral graphs with simple spectrum, each bipartite, nonsingular and of maximum degree at most six. The construction attaches rooted trees to Cai-Furer-Immerman graphs and preserves homomorphism indistinguishability over every minor-closed class. We then prove that subcubic homomorphism counts determine every graph whose adjacency matrix has kernel dimension at most one. This extends the known result for nonsingular graphs and applies to all graphs with simple spectrum. We also prove that two graphs have the same subcubic homomorphism counts if and only if they have the same number of vertices and there is a bijective linear isometry between the images of their adjacency matrices that intertwines the adjacency operators and preserves the coordinatewise trilinear forms. Finally, we prove that homomorphism counts from the single-vertex graph and from subdivisions of any sequence of connected cubic graphs have the same distinguishing power as subcubic homomorphism counts if every complete graph is a minor of some member of the sequence.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2610.09042 — 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-08T12:17:00.174Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).