Metraipolis › archive › dc_6cdfdd2efca4

Counterexamples to the Strong Roberson Conjecture — arXiv:2610.03550

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.03550
License (as archived): CC0-1.0
Archived: 2026-10-06T08:25:32.843Z
SHA-256 of the archived text: f5eb7f4a116bcc025eee4730f280bbfb1b9b8b5fba3db9ba85f9c7acdb8e3886
Stable URL of this page: https://metraipolis.com/documento/dc_6cdfdd2efca4

How to cite

Counterexamples to the Strong Roberson Conjecture — arXiv:2610.03550 — arXiv (en), https://arxiv.org/abs/2610.03550 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6cdfdd2efca4 (Metraipolis archive dc_6cdfdd2efca4, sha256 f5eb7f4a116bcc025eee4730f280bbfb1b9b8b5fba3db9ba85f9c7acdb8e3886)

BibTeX

@misc{dc6cdfdd2efca4,
  title = {Counterexamples to the Strong Roberson Conjecture — arXiv:2610.03550},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.03550},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6cdfdd2efca4; sha256 f5eb7f4a116bcc025eee4730f280bbfb1b9b8b5fba3db9ba85f9c7acdb8e3886},
  year = {2026}
}

Archived text

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

We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a class closed under minors and disjoint unions strictly increases the distinguishing power of homomorphism counts from that class. More precisely, we construct connected graphs $H$ for which counts from graphs excluding $H$ as a minor determine the number of homomorphisms from $H$ to any target graph. We also refute the analogous conjecture with immersions in place of minors. We give explicit infinite families of excluded graphs, including cubic bipartite graphs that yield counterexamples for both relations. The proof introduces a method for deriving exact homomorphism count dependence from modular equivalences. We obtain these equivalences for infinitely many primes using prime-order automorphisms of graphs that exclude their orbit quotients as minors or immersions.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.03550 — 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-06T08:18:48.318Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).