OpenAlex ·
Counterexamples to the Strong Roberson Conjecture
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.03550
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Conformal Bootstrap for surfaces with boundary in Liouville CFT. Part II: spectral resolution and bootstrap
Sharp Riesz capacity inequalities and the Pólya--Szegő conjecture
On the Definition and Smooth Examples of Weakly Kähler--Finsler Metrics
Long-time existence of the Calabi flow on Kähler surfaces with bounded Sobolev constants
Resolving Erdős-Ulam Monochromatic Union-Closed Family Conjectures
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.