CS Paper Radar

Distinguishing graphs with simple spectrum by homomorphism counts

Takanori Maehara

cs.DM math.CO ·submitted 2026-10-06 19:43 UTC · v2
theory

Abstract

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.

Comment
32 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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.70
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

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.69
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

Counterexamples to the Strong Roberson Conjecture

cs.DM math.COcs.LO ·2026-10-02 ·Arnar Á. Kristjánsson
similarity 0.67
Abstract · 24 pages. v2: expanded introduction, related work and conclusion; improved exposition throughout; smaller explicit counterexamples obtained

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.

0.45

A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability

cs.LO cs.CCmath.CO ·2026-08-13 ·Radu Curticapean, Daniel Neuen, Amir Nikabadi, Tim Seppelt, Ben Young
theory similarity 0.66
Abstract

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if they admit the same number of homomorphisms from every graph in $\mathcal{F}$. A wide range of relaxations of graph isomorphism arise this way: isomorphism itself over the class of all graphs [Lovász, Acta Math. Hung. 1967], equivalence under the $k$-dimensional Weisfeiler-Leman algorithm over the graphs of treewidth $\leq k$ [Dvořák, J. Graph Theory 2010], and quantum isomorphism over planar graphs [Mančinska-Roberson, FOCS 2020]. Since the class $\mathcal{F}$ is typically infinite, it is not clear a priori whether homomorphism indistinguishability over $\mathcal{F}$ is decidable; for planar graphs it is undecidable. Every class for which decidability was previously known is sparse. We give the first decidability results for dense graph classes: We introduce the dense Weisfeiler-Leman algorithm that decides homomorphism indistinguishability over the class of graphs of cliquewidth $\leq k$, the dense counterpart of treewidth. This relation was not previously known to be decidable. The algorithm colors $k$-tuples of vertex subsets rather than $k$-tuples of vertices. Beyond the class of all graphs of cliquewidth $\leq k$, we prove a general meta-theorem: homomorphism indistinguishability over every $\mathsf{CMSO}_1$-definable graph class of bounded cliquewidth is decidable, in randomized exponential time. For classes of bounded linear cliquewidth the bound improves to $\mathsf{PSPACE}$, and we show this is tight by exhibiting such a class for which the problem is $\mathsf{PSPACE}$-complete. These are the first general algorithms for homomorphism indistinguishability over dense graph classes.

0.33

An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability

cs.DM ·2026-11-02 ·Moritz Lichter, Harry Vinall-Smeeth
theory similarity 0.65
Abstract · 66 pages

One way to compare two graphs $G_1, G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not equal to that from $H$ to $G_2$. This is the field of homomorphism distinguishability which has gained a lot of traction in recent years. In this paper, we study the case where $\mathcal{H}$ is the class of graphs of treewidth $k$. This has connections to important concepts in logic, machine learning, combinatorial optimization and proof complexity. In particular, Dvořák showed that $G_1$ and $G_2$ can be distinguished by a homomorphism count from a graph of treewidth $k$ iff $G_1$ and $G_2$ are distinguishable by the $k$-dimensional Weisfeiler-Leman algorithm. While the relation between the iteration number of this algorithm and the depth of the tree-decomposition of a distinguishing graph is understood, our understanding of the \emph{size} of $H$ is limited. We show a $2^{Ω(n^{k/2})}$ lower bound on the size of a graph of treewidth $k$ required to distinguish two graphs of order $n$. This bound is proved via a new combinatorial game along with a construction which uses a recent compression technique for CFI graphs. It is almost tight to the known $2^{O(n^{k+1})}$ upper bound and is an exponential improvement on the previous best known lower bound.

0.25

Asymptotic dimension of graphs excluding an induced or fat minor

cs.DM math.CO ·2026-10-15 ·Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak
theory similarity 0.63
Abstract

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph $H$, the class of graphs excluding $H$ as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding $H$ as an induced minor. We substantially expand the range of graphs $H$ for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is $χ$-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.

0.24

Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width

cs.DM math.COcs.LO ·2026-10-07 ·Antonios Kalampakas
theory similarity 0.63
Abstract · 44 pages. Includes ancillary verification code

The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to $d$-tuples of vertices and iteratively refining the colouring according to neighbourhood configurations until it stabilizes. Increasing $d$ allows the test to detect finer structural differences between graphs, but the computational cost grows exponentially with $d$. The central question is which dimension allows us to distinguish nonisomorphic graphs. We relate a sufficient such dimension to the structure of a graph $G$ through a rank decomposition over $\mathbb F_2$. The two parameters governing the bound are the maximum cut rank $w$ and the fork load $\ell$, which is the largest sum of the parent and two child cut ranks at a fork in the decomposition tree. We prove that WL in dimension $\max\{\ell+1,2w+2\}$ distinguishes every finite nonempty vertex-coloured graph $G$ with such a decomposition from every graph not isomorphic to $G$. Consequently, for $k\geq1$, graphs of rank width at most $k$ can be distinguished from every nonisomorphic graph in dimension $3k+1$, graphs of linear rank width at most $k$ in dimension $2k+2$, and edgeless graphs in dimension one. Uncoloured Cai-Fürer-Immerman (CFI) constructions give linear lower bounds for both width parameters, so the upper bounds are tight up to constant factors.

0.29

Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

cs.DM math.CO ·2026-09-21 ·Romain Bourneuf, Raphael Steiner, Stéphan Thomassé, Yuval Wigderson
theory similarity 0.62
Abstract

We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that $δ_{\mathrm{hom}}(\{C_3,C_5\},\{C_3\})=\frac{1}{9}$. Equivalently, for every $\varepsilon>0$, every $n$-vertex graph of odd girth at least $7$ and minimum degree at least $(1/9+\varepsilon)n$ admits a homomorphism to a triangle-free graph of size bounded by a function of $\varepsilon$, while there exist graphs of odd girth at least $7$ and minimum degree at least $(1/9-\varepsilon)n$ for which no such bounded-size triangle-free homomorphic image exists. More generally, for every $t\geq 3$, we prove $δ_{\mathrm{hom}}(\{C_3,C_5\},\{K_t\})=\frac{1}{3t}$. In particular, for every proper monotone class $\mathcal C$ of graphs, the threshold for graphs of odd girth at least $7$ to admit a homomorphism to a bounded-size graph in $\mathcal C$ is positive. We further extend this phenomenon to arbitrary odd girth: for every $k\geq 2$ and every proper monotone subclass $\mathcal C$ of the class of graphs of odd girth at least $2k-1$, the threshold for graphs of odd girth at least $2k+3$ to admit a homomorphism to a bounded-size graph in $\mathcal C$ is positive. These results disprove conjectures of Gishboliner, Hurley and Wigderson and exhibit a sharp contrast with the corresponding zero chromatic-threshold results. Our lower-bound constructions are based on high-dimensional Borsuk graphs, while the matching upper bounds use regularity arguments to recover the structure underlying these constructions.

0.21