Equality on all #CSP Instances Yields Constraint Function Isomorphism via Interpolation and Intertwiners

Ben Young¹

¹University of Wisconsin-Madison

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

A fundamental result in the study of graph homomorphisms is Lovász's theorem that two graphs are isomorphic if and only if they admit the same number of homomorphisms from every graph. Cai and Govorov capped a line of work extending Lovász's result to more general types of graphs by showing that it holds for graphs with vertex and edge weights from an arbitrary field of characteristic zero. Counting graph homomorphisms is a counting constraint satisfaction problem (#CSP) parameterized by a single constraint function of arity two. In this work, we extend Lovász's theorem to general #CSP by showing that any two sets $\mathcal{F}$ and $\mathcal{G}$ of constraint functions are isomorphic if and only if they are #CSP-indistinguishable -- that is, the partition function value of any #CSP instance is unchanged when we replace the functions in $\mathcal{F}$ with those in $\mathcal{G}$. We give two very different proofs of this result. First, we give a proof for complex-valued constraint functions using the intertwiners of the automorphism group of a constraint function set, a concept from the representation theory of compact groups, in the style of Mančinska and Roberson's proof of the equivalence between quantum isomorphism and homomorphism indistinguishability over planar graphs. Second, we demonstrate the power of the simple Vandermonde interpolation technique of Cai and Govorov by extending it to general #CSP, giving a constructive proof for constraint functions with entries from any field of characteristic zero.

Détail

DOI : 10.37236/13879