论文标题
所有#CSP实例的平等均通过插值和互换产生约束功能同构
Equality on all #CSP Instances Yields Constraint Function Isomorphism via Interpolation and Intertwiners
论文作者
论文摘要
图形同态研究的一个基本结果是，洛瓦斯的定理是，当且仅当它们接受每个图中相同数量的同态数量时，两个图是同构的。最近，CAI和Govorov封顶了一条将Lovász的结果扩展到更通用的图形类型的工作线，他们表明它适用于具有特征性0的顶点和边缘权重的图表0。在这项工作中，我们从图形同构中概括了同性恋 - 与单个Binary函数的特殊情况 - 从一般的#css $ c $ c $ cys $ c.当我们仅当我们用$ \ Mathcal {g} $中的这些函数替换$ \ Mathcal {f} $时，任意约束函数的$ \ MATHCAL {G} $是同构的。我们给出了两个截然不同的证据。首先，我们通过将其扩展到一般#CSP来演示CAI和Govorov的简单Vandermonde插值技术的功能。其次，我们使用约束函数集的自动形态组的互换者提供了证明，这是紧凑型组的表示理论的概念。该证明是对Mančinska和Roberson最新证明的经典版本的概括，该证明是由平面图与量子同构和同构的相关性的。
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. A line of work extending Lovász's result to more general types of graphs was recently capped by Cai and Govorov, who showed that it holds for graphs with vertex and edge weights from an arbitrary field of characteristic 0. In this work, we generalize from graph homomorphism -- a special case of #CSP with a single binary function -- to general #CSP by showing that two sets $\mathcal{F}$ and $\mathcal{G}$ of arbitrary constraint functions are isomorphic if and only if the partition function 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 demonstrate the power of the simple Vandermonde interpolation technique of Cai and Govorov by extending it to general #CSP. Second, we give a proof using the intertwiners of the automorphism group of a constraint function set, a concept from the representation theory of compact groups. This proof is a generalization of a classical version of the recent proof of the Lovász-type result by Mančinska and Roberson relating quantum isomorphism and homomorphisms from planar graphs.
