Counterexamples to the Strong Roberson Conjecture
math.CO, cs.DM, cs.LO
Submitted: 2026-10-02
Updated: 2026-11-02
Comments: 24 pages. v2: expanded introduction, related work and conclusion; improved exposition throughout; smaller explicit counterexamples obtained
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a graph class closed under minors and disjoint unions strictly increases the distinguishing power of homomorphism…
Abstract
We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a graph 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 homomorphism 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. The proof introduces a method for deriving exact homomorphism count dependence from modular equivalences. We obtain these modular equivalences for infinitely many primes using prime-order automorphisms and the corresponding orbit quotients. We complete the refutations by proving that suitable circulant graphs with two jump lengths and related cubic bipartite graphs exclude their corresponding orbit quotients as minors and immersions, respectively.
Sources
- Homomorphism counting for immersion-closed classes is not isomorphism
- Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality