PaperlayerView exact revision on arXiv

Source-linked AI summary

Counterexamples to the Strong Roberson Conjecture

Arnar Á. Kristjánsson

arXiv:2610.03550v1math.COcs.DMcs.LO

TL;DR

The paper asks whether adding any graph outside a minor- and disjoint-union-closed source class always increases homomorphism-count distinguishing power. It refutes the strong conjectures for minors and immersions using modular count dependence and prime-order automorphisms. Explicit infinite families, including cubic bipartite graphs, provide counterexamples for both relations.

  • Problem

    The Strong Roberson Conjecture asks whether every minor- and disjoint-union-closed source class is homomorphism distinguishing closed.

    Source: §1 · p. 2

  • Method

    For infinitely many primes, prime-order automorphisms yield modular homomorphism-count equivalences from graphs whose orbit quotients are excluded as minors or immersions.

    Source: §1.1 · p. 4, §3.1 · p. 9

  • Results

    The paper refutes the strong conjectures for minors and immersions with explicit infinite families, including cubic bipartite counterexamples for both relations.

    Source: §1.1 · p. 4, §4.2 · p. 12, §7 · p. 20

  • Takeaways & Limitations

    The strong conjectures fail for minors and immersions, but hold for their transitive closure, the split-off minor relation [11].

    Source: §1.1 · p. 4

    The Weak Roberson Conjecture remains open for proper classes closed under minors and disjoint unions.

    Source: §7 · p. 20

Abstract

from arXiv · show

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.

1 Introduction

Homomorphism counts can retain the same distinguishing power even when a source class is enlarged, motivating the Strong Roberson Conjecture that every minor- and disjoint-union-closed class is homomorphism distinguishing closed. This paper refutes that conjecture and its immersion analogue with connected excluded graphs.

1 Introduction

  • Homomorphism distinguishing closure contains the graphs whose counts are determined by the class, and a class is h.d.-closed when it equals that closure.A positive Strong Roberson Conjecture would make the minor-closed class representing a relation unique after disjoint-union closure.Source: §1 · p. 2
  • The Strong Roberson Conjecture says every class closed under minors and disjoint unions is homomorphism distinguishing closed.If true, it would make comparison of distinguishing relations equivalent to inclusion for such classes.Source: §1 · p. 2
  • The minor and immersion conjectures are separate because their containment relations are incomparable, while the split-off-minor analogue holds [11].Earlier oddomorphism methods did not establish the conjectured separations, and a counterexample to that proof strategy left the conjecture open.Source: §1 · p. 3

1.1 Our contributions

  • The paper refutes both strong conjectures using connected graphs whose homomorphism counts are determined by counts from graphs excluding them as minors or immersions.The resulting forbidden-source classes are closed under the respective containment relation and disjoint unions, yet are not h.d.-closed.Source: §1.1 · p. 3
  • For infinitely many primes, modular congruences from graphs in the source class yield exact homomorphism-count dependence on the excluded graph.The congruences come from prime-order automorphisms whose orbit quotients are the excluded graphs.Source: §1.1 · p. 4
  • Explicit circulant and cubic bipartite graph families exclude their orbit quotients as minors; the cubic examples exclude them as immersions too.One minor example is a 101-vertex circulant, and a related 202-vertex cubic bipartite graph supplies both counterexamples.Source: §1.1 · pp. 3–4

2 Preliminaries

The preliminaries establish the paper’s graph conventions, homomorphism indistinguishability and its distinguishing closure, the minor and immersion relations, and treewidth terminology.

2 Preliminaries

  • Graphs are finite, simple, undirected, and loopless unless stated otherwise; the empty graph is allowed and classes are closed under isomorphism.Closure under disjoint unions means closure under finite disjoint unions.Source: §2 · p. 4

2.1 Homomorphism indistinguishability

  • Graphs X and Y are indistinguishable over a source class when every source graph has equal homomorphism counts to both targets.The homomorphism distinguishing closure consists of graphs whose counts agree on every such indistinguishable target pair; h.d.-closed means equality with that closure.Source: §2.1 · p. 5

2.2 Minors and immersions

  • Minor-free and immersion-free source classes are closed under their respective relations and disjoint unions when the excluded graph is connected.For cubic H in a subcubic host G, every immersion model of H forms a subdivision of H.Source: §2.2 · p. 6

2.3 Tree decompositions

  • Treewidth is the minimum, over tree decompositions, of the largest bag size minus one, and it is minor-monotone.Deleting a vertex set S permits a decomposition of G to be extended by adding S to every bag, increasing width by at most |S|.Source: §2.3 · pp. 6–7

3 Homomorphism count dependence from equivalence modulo m

The section turns homomorphism-count congruences modulo infinitely many moduli into exact dependence on counts from a graph class. Prime-order automorphisms provide those congruences through orbit quotients, while shift lifts describe the relevant graph structure.

3 Homomorphism count dependence from equivalence modulo m

  • If hom(F_m, X) and hom(H, X) are congruent modulo m for every target X for all but finitely many m in an infinite set, then H belongs to Cl(F).For graphs indistinguishable by F, their hom(H, ·) difference is divisible by infinitely many moduli and must be zero.Source: §3 · p. 7
  • An automorphism of prime order p makes hom(F, X) congruent to hom(F/⟨σ⟩, X) modulo p for every target X.Fixed homomorphisms correspond to maps from the orbit quotient; all other group orbits have size p.Source: §3 · pp. 7–8
  • If every prime in an infinite set has a graph F_p in F with an order-p automorphism whose quotient is H, then H belongs to Cl(F).This combines the prime-order congruence with the criterion for exact homomorphism-count dependence.Source: §3 · p. 8

3.1 Shift lifts and cyclic automorphisms

  • An m-shift lift replaces each base vertex with an independent m-vertex fibre and each base edge with a perfect matching; shifting sheet coordinates gives an order-m automorphism with the base as quotient.The matching is specified by edge voltages in Zm.Source: §3.1 · p. 8
  • For a prime-order automorphism, the subgraph on size-p orbits contains a spanning invariant p-shift lift of their adjacency graph.A vertex fixed by the automorphism is adjacent either to every vertex of a size-p orbit or to none.Source: §3.1 · p. 9
  • The paper needs one fixed base graph with minor-excluding shift lifts for infinitely many primes; the cited random-lift range for a fixed clique base supplies only finitely many primes.The authors instead construct deterministic families using two-jump circulants and their cubic splits.Source: §3.1 · pp. 9–10

4 The graph families and the counterexamples

The paper constructs two graph families and uses prime-order symmetries plus exclusion results to produce counterexamples for minors and immersions. The resulting failures include explicit cubic bipartite witnesses, while the split-off minor relation remains a positive variant.

4.1 Two graph families

  • The families are built from D(r), a connected 4-regular circulant with jumps ±1 and ±r, and B(r), a connected cubic bipartite graph formed by splitting its vertices.In B(r), contracting each spoke recovers D(r); the incoming and outgoing edges attach to separate split vertices.Source: §4.1 · p. 10

4.2 The counterexamples

  • For every prime in the specified infinite residue set, the constructed graphs have order-p rotations with the corresponding base graphs as orbit quotients.The prime set consists of primes coprime to r and not congruent to ±1 modulo r; the quotient construction supplies the class memberships used in the counterexamples.Source: §4.2 · pp. 11–12
  • For the stated parameters, the forbidden-graph classes yield counterexamples to the Strong Roberson Conjecture and its immersion analogue.Theorem 12 requires r ≥ 3, q ≡ 1 (mod r), q > 4r^2 − 2, gcd(m, r) = 1, and m not congruent to ±1 modulo r; Theorem 14 gives the counterexample classes under its stated conditions.Source: §4.1 · p. 11, §4.2 · p. 12
  • For every p in Pr, the cubic family provides the same witnesses for both exclusions: the graph B(r) is excluded neither as a minor nor as an immersion.Source: §4.2 · p. 12
  • The witnesses separate minors and immersions from their transitive closure: the base is a split-off minor even when it is neither a minor nor an immersion of the lift.The split-off minor relation allows a sequence of minor and immersion steps with intermediate multigraphs.Source: §4.2 · p. 13
  • The Strong Roberson Conjecture already fails for a class restricted to pathwidth at most 10.For H = D(5), the class F10 is minor closed and closed under disjoint unions, yet H belongs to its homomorphism-distinguishing closure and not to F10.Source: §4.2 · p. 13

5 Treewidth bounds

The section establishes matching treewidth bounds for circulant and cubic graph families, including robust lower bounds that survive deletion of a short edge. It also supplies pathwidth bounds after deleting specified vertex sets or edges.

5.1 Upper bounds for the circulants

  • For D(r)_n, deleting a long edge decreases treewidth, whereas deleting a short edge leaves it unchanged.The section also bounds pathwidth after deleting r consecutive vertices or a long edge.Source: §5 · p. 13
  • Deleting r consecutive vertices from D(r)_n or r consecutive vertices of either type from B(r)_n leaves pathwidth at most r.The bounds follow from sliding-window path decompositions.Source: §5.1 · p. 13, §5.3 · p. 15

5.2 A robust lower bound

  • For r ≥ 3 and q > 4r^2 − 2, deleting a short edge from D(r)_q leaves treewidth 2r, with no gcd or congruence restriction on q.The lower bound uses a separator argument and matches the upper bound.Source: §5.2 · pp. 14–15

5.3 Bounds for the cubic graphs

  • For B(r)_n, deleting any spoke or long edge leaves pathwidth at most 2r − 1.The construction first uses width at most r after removing a block of vertices, then adds that block to every bag.Source: §5.3 · p. 15
  • For r ≥ 3 and q > 4r^2 − 2, deleting a short edge from B(r)_q also leaves treewidth 2r.Contracting spokes transfers the circulant lower bound, while the cubic upper bound completes the equality.Source: §5.3 · p. 16

6 Excluding the base graphs as minors

The section constrains the form of any minor model in the two graph families, then uses distances along specified Hamilton cycles to rule out the models for the chosen parameters. The argument yields minor exclusions for both families and an immersion exclusion for the cubic family.

6 Excluding the base graphs as minors

  • Under the stated treewidth and pathwidth conditions, every minor model uses all host vertices and has branch sets that are cyclic intervals ordered as on the base Hamilton cycle, up to reversal and starting point.Edges of the host cycle between distinct branch sets correspond to adjacent base-cycle vertices.Source: §6 · p. 16
  • For D(r) and B(r), every minor model partitions the specified host Hamilton cycle into intervals in base-cycle order, and host edges representing short base edges are themselves short.The applicable cycles are the long-edge cycle for D(r) and the spoke-and-long-edge cycle for B(r).Source: §6 · p. 17
  • The proof assigns coordinates that make long edges consecutive and express short-edge endpoint distances as d_r(n) for D(r) and b_r(n) for B(r).These distances lead to necessary inequalities by comparing a host arc spanning branch intervals with the cyclic distance between its endpoints.Source: §6 · pp. 17–18
  • For r = 5, q = 101, and N = 101m with m ≡ 2 (mod 5), both necessary inequalities fail: d_5(N) + 1 = (202m + 6)/5 > 21m and b_5(N) + 1 = (404m + 2)/5 > 42m.The passage presents this as an example; the proof extends the conclusion to the parameters of Theorem 12.Source: §6 · p. 19
  • The parameter choices in Theorem 12 violate the necessary inequalities, proving both minor exclusions; the cubic graph exclusion also gives an immersion exclusion.The stated parameters have q ≡ 1 (mod r), q > 4r^2 − 2, and N = qm with gcd(m,r) = 1 and m not congruent to ±1 modulo r.Source: §6 · p. 19

7 Conclusion

The paper concludes that it refutes the Strong Roberson Conjecture and its immersion analogue, and presents a modular method for establishing homomorphism-count dependence. It leaves the Weak Roberson Conjecture open and identifies further research directions.

7 Conclusion

  • The paper refutes the Strong Roberson Conjecture and its immersion analogue using explicit graph families and a modular method for homomorphism-count dependence.The method uses shift lifts with prime-order automorphisms to obtain equivalences modulo p.Source: §7 · p. 20
  • The Weak Roberson Conjecture remains open: whether every proper class closed under minors and disjoint unions fails to distinguish some pair of non-isomorphic graphs.The passage notes an oddomorphism-based approach that would suffice to establish the conjecture.Source: §7 · p. 20
  • The conclusion proposes investigating whether CFI constructions are complete, in a suitable sense, for proving homomorphism distinguishing closedness for certain graph classes.In the examples discussed, failure of the CFI approach reflects an actual homomorphism-count dependence.Source: §7 · p. 20
Loading 2610.03550v1…