CS Paper Radar

Counterexamples to the Strong Roberson Conjecture

Arnar Á. Kristjánsson

cs.DM math.COcs.LO ·submitted 2026-10-02 16:33 UTC · v2

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.

Comment
24 pages. v2: expanded introduction, related work and conclusion; improved exposition throughout; smaller explicit counterexamples obtained

Closest papers

Nearest neighbours by meaning across the whole index.

Distinguishing graphs with simple spectrum by homomorphism counts

cs.DM math.CO ·2026-10-06 ·Takanori Maehara
theory similarity 0.67
Abstract · 32 pages, 8 figures

We study which graph classes determine every graph with simple spectrum up to isomorphism by homomorphism counts from their members. We show that such a class has unbounded treewidth and Euler genus and contains a graph with the complete graph on seven vertices as a minor. To prove these conditions, we construct pairs of non-isomorphic cospectral graphs with simple spectrum, each bipartite, nonsingular and of maximum degree at most six. The construction attaches rooted trees to Cai-Furer-Immerman graphs and preserves homomorphism indistinguishability over every minor-closed class. We then prove that subcubic homomorphism counts determine every graph whose adjacency matrix has kernel dimension at most one. This extends the known result for nonsingular graphs and applies to all graphs with simple spectrum. We also prove that two graphs have the same subcubic homomorphism counts if and only if they have the same number of vertices and there is a bijective linear isometry between the images of their adjacency matrices that intertwines the adjacency operators and preserves the coordinatewise trilinear forms. Finally, we prove that homomorphism counts from the single-vertex graph and from subdivisions of any sequence of connected cubic graphs have the same distinguishing power as subcubic homomorphism counts if every complete graph is a minor of some member of the sequence.

0.27

Realizing graph automorphisms as geometric symmetries of straight line drawings

cs.CG math.COmath.GR ·2026-10-26 ·Saul D. Freedman, Melissa Lee, Dragan Marušič, Tomaž Pisanski
similarity 0.66
Abstract · 20 pages, comments welcome

Given a finite graph $G$, we characterize the automorphisms and automorphism groups of $G$ that can be realized as geometric symmetries and symmetry groups of straight line drawings of $G$ in the plane. In doing so, we correct a previous version of this characterization from the literature. As an application, we show that the graphs recently constructed by the first two authors to disprove the Polycirculant Conjecture, which have orders $16{,}464^k$ for each positive integer $k$, are the first known vertex-transitive graphs with no non-trivial realizable geometric symmetries. We also construct infinite families of graphs that exhibit all possible kinds of geometric symmetry.

0.22

Graphs with Long Pseudosimilarity Chains under Consecutive Vertex Deletions

cs.DM math.CO ·2026-08-31 ·Sergey Ivanov
hot direction similarity 0.65
Abstract

Pseudosimilar vertices are vertices in distinct automorphism orbits whose deletions produce isomorphic graphs. Classical work has studied the existence, group-theoretic origin, and construction of large sets of such vertices. We ask a different recursive question: how long can one repeatedly delete a vertex that is pseudosimilar at the moment of deletion? We define the pseudosimilarity depth of a graph and construct connected graphs in which this process continues through all but a sublinear number of vertices. A two-clock construction gives a square-root deficit uniformly in the order, while a Chinese-remainder construction with many cyclic clocks yields an infinite family of asymmetric graphs with only a polylogarithmic number of vertices left outside the active chain. The mechanism realizes pseudosimilarity by breaking a long hidden automorphism orbit and enlarging the break one vertex at a time. Thus pseudosimilarity can persist through an asymptotically full sequence of vertex deletions, even though every graph encountered in the main construction is asymmetric.

0.54

Structural Characterizations and Algebraic Realizations of a Family of Regular Integral Graphs

cs.DM math.COmath.GR ·2026-09-22 ·Tapa Manna, Supriyo Dutta, Baby Bhattacharya
theory similarity 0.64
Abstract · Comments are welcome!

All the eigenvalues of an integral graphs are integers. Integral graphs are extremely rare. They form an asymptotically vanishing fraction $2^{-Ω(n)}$ among all graphs on $n$ vertices. It makes the construction of a new family of integral graphs a challenging task. Also, most of the known infinite family of integral graphs rely on Cayley graphs over Abelian groups. In this article, we introduce a new family of integral graphs obtained from the groups. The construction of our graphs from groups is different from the construction of Cayley graphs. A spectral uniqueness theorem is established, which shows that each member of the infinite family is determined by its adjacency spectrum among all finite simple graphs. We also present recursive constructions that generates larger members of the family from smaller ones, providing a scalable class of integral graphs. Finally, we investigate algebraic realizations of these graphs as complements of Proper Prime Order Element Graphs of finite $2$-groups and obtain conditions characterizing such realizations. We also observe that the graphs obtained from different non-isomorphic groups have cospectral graphs.

0.18

Integral saturation of adjacency-degree lattices

cs.DM math.CO ·2026-11-01 ·Zhipeng Lu
theory similarity 0.63
Abstract

Let $A$ be the adjacency matrix of $G\sim G(n,1/2)$, let $D=\operatorname{diag}(A\mathbf{1})$, and let $Λ_G=\mathbb{Z}\langle A,D\rangle\mathbf{1}$. We prove $\Pr[Λ_G\ne\mathbb{Z}^n]\le n^{-3/20+o(1)}$. Thus two dependent graph operators generate the entire vertex lattice from the constant vector, simultaneously over every prime field. Adjacency alone has a modulo-two rank obstruction for every simple graph of order greater than one, even though its rational word span is typically full. The proof first constructs words containing at most two adjacency operations whose integer span contains $Δ_G^3\mathbb{Z}^n$, where $Δ_G$ is the product of the pairwise differences between distinct degree values. This confines all possible arithmetic obstructions to a finite prime range on a single event. We then remove the remaining obstructions using conditional alternating forms, symmetric random-matrix code estimates, and uniform counts of degree-graded invariant subspaces. We connect the integer lattice to graph reconstruction through pointed moments. Saturation forces every pointed orthogonal AD intertwiner to be a vertex permutation. The short-word construction also shows that a fixed polynomial-size family of ordinary caterpillars, of diameter at most seven and order $O(\sqrt{n\log n})$, identifies almost every graph among all finite simple graphs. For nonsaturated full-rank lattices, we give an exact description of the moment fibre by admissible unimodular overlattices; at index two, the only possible ambiguity is a specified four-vertex Godsil--McKay switch.

0.28

Topological and Geometric Perspectives on Homomorphism Indistinguishability

cs.DM math.COcs.LO ·2026-10-06 ·Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson, Tim Seppelt, Gian Luca Spitzer +1 more
similarity 0.62
Abstract

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if, for every graph $F \in \mathcal{F}$, the number of homomorphisms from $F$ to $G$ is equal to the number of homomorphisms from $F$ to $H$. Lovász (Acta Mathematica Academiae Scientiarum Hungarica, 1967) showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs. Subsequently, homomorphism indistinguishability relations of a long list of natural graph classes have been equated with natural graph isomorphism relaxations. Given the wealth of such results, Atserias, Kolaitis, & Wu (LICS 2021) asked for an axiomatic characterisation of homomorphism indistinguishability relations. By exhibiting topological and geometric structure associated with homomorphism indistinguishability, we derive such an axiomatic characterisation. Here, a central ingredient is a novel characterisation of graph parameters of the form $\hom(F, \star)$ for some graph $F$ alternative to a previous result of Lovász & Schrijver (JCTA 2010). Moreover, we investigate the topology of homomorphism indistinguishability and discuss repercussions for the Ulam--Kelly Reconstruction Conjecture.

0.34

What remains of the planar induced minor conjectures?

cs.DM cs.CCcs.DSmath.CO ·2026-11-06 ·Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski
similarity 0.61
Abstract · 26 pages, 7 figures

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

0.15

Homomorphic-core phase transition threshold in Erdős--Rényi random graphs

cs.CC math.COcs.DMcs.DS+1 ·2026-08-25 ·Jiaheng Wang
similarity 0.61
Abstract · 18 pages, AI-assisted

It is shown in this manuscript that a random graph $G$ drawn from the Erdős--Rényi model $\mathcal{G}(n,p)$ with \[ p=p(n)\leq 1/2, \qquad \lim_{n\to+\infty}(np-\log n-\log\log n)=+\infty, \] is a homomorphic core, i.e., every homomorphism from $G$ to itself is an automorphism. This implies tight ETH-based lower bounds of the subgraph isomorphism problem for almost all $k$-vertex patterns with polynomial average degree.

0.19