Skip to content
DraconiticResearch
Search Sources API
190,860 studies31 sourcesUpdated 48 min ago
PreprintCC BY-NC-ND 4.0arXiv

Counterexamples to the Strong Roberson Conjecture

  • Arnar Á. Kristjánsson
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Strong counterexamples to Mubayi's supersaturation conjecture in every uniformity
    Heng Li, Hong Liu, Xizhi Liu +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Counterexamples to the Tensorization Property of Strong Data Processing Inequalities for Quantum Divergences
    Yu Cao
    arXivPreprintarXiv licenceFull textMathematical physicsQuantum physics & quantum informationarXiv
  3. Counterexamples to the Monotone Completeness Conjecture
    Jananan Arulseelan, James E. Hanson
    arXivPreprintarXiv licenceFull textAnalysis & PDEsLogic & foundationsarXiv
  4. Counterexamples to the ordinary Fried conjecture near hyperbolic metrics
    Simon Becker, Benjamin Lawton
    arXivPreprintCC0Full textAnalysis & PDEsDynamical systemsarXiv
  5. Counterexamples to the inhomogeneous Duffin-Schaeffer Conjecture
    Manuel Hauke-Treuer, James Maynard, Andrew Pollington
    arXivPreprintCC BY-NC-SA 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{kristjansson2026counterexamples,
  title = {{Counterexamples to the Strong Roberson Conjecture}},
  author = {Arnar Á. Kristjánsson},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.03550},
  eprint = {2610.03550},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.03550},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - Counterexamples to the Strong Roberson Conjecture
AU  - Arnar Á. Kristjánsson
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.03550
UR  - https://arxiv.org/abs/2610.03550
AB  - 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.
ER  -