Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
Daniel Neuen Technische Universität Dresden, Tim Seppelt IT-Universitetet i København · 2026
Read Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs by Daniel Neuen Technische Universität Dresden, Tim Seppelt IT-Universitetet i København (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18602.txt.
Description
Daniel Neuen and Tim Seppelt ask how few kinds of test graphs one needs to tell two graphs apart. A famed claim says two graphs are the same in form if and only if each test graph sends the same count of maps into both. That claim needs all test graphs at once, which is a huge set. Work since then asks if thin sets of test graphs can do the same job.
The pair look at sparse test graphs, ones with few links for their size. Sparse tests are cheap to count, so a thin set that still tells graphs apart would be a win. Their work maps which graph pairs sparse tests can split and which they blur. That map feeds the maths of graph form, a base for checks on nets and on code that sorts them.
Catalog record
| CREATOR | Daniel Neuen Technische Universität Dresden, Tim Seppelt IT-Universitetet i København |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-18602