Graphs excluded from minors may not increase homomorphism power
Counterexamples to the Strong Roberson Conjecture
Discrete MathematicsLogic in Computer Science
Summary
The paper challenges a widely held idea called the Strong Roberson Conjecture, which suggested that adding any new graph outside a certain class would always make it easier to tell graphs apart by counting certain patterns. The authors show that this is not always true by finding special connected graphs where excluding them as minors doesn’t add any power to these counts. They also demonstrate similar counterexamples using a related concept called immersions. Their work uses precise mathematical methods involving prime numbers and symmetries in graphs to prove these surprising results.
What this means in practice
- •For graph algorithm developers: Avoid expecting new minor exclusions to always help distinguish graphs via homomorphism counts when designing graph classification algorithms.
- •For coding theory engineers: Use insights from homomorphism count dependencies on graph symmetries for designing error-correcting mechanisms relying on graph structures.
A theory result. No direct application yet.
Authors
Arnar Á. Kristjánsson
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.