配分函数和图多项式的确定性多项式时间近似算法

摘要

在本文中，我们展示了一种构建确定性多项式时间近似算法的新方法，用于计算有界度图上的一大类图多项式的复值评估。 特别是，我们的方法适用于 Tutte 多项式和独立多项式，以及复值自旋和边缘着色模型的配分函数。

更具体地说，我们定义了一大类图多项式 $𝒞$，并证明如果 $p\in 𝒞$，并且在复平面上存在一个以零为中心的圆盘 $D$，使得对于所有有界度图 $G$，$p(G)$ 在 $D$ 上不消失、那么对于 $D$ 内部的每个 $z$ 都存在一个确定的多项式时间近似算法，用于在 $z$ 处评估 $p(G)$ 。 这给出了图多项式不存在零点与有效近似算法的存在之间的明确联系，使我们能够展示众所周知的猜想之间的新关系。

我们的工作建立在 Barvinok [2, 3, 4, 5] 最近发起的一系列工作的基础上，除了现有的马尔可夫链蒙特卡罗方法和相关衰减方法之外，它还提供了一种新的算法方法。问题类型。

关键词：近似算法、Tutte多项式、独立多项式、配分函数、图同态、Holant问题。

MSC：68W25（初级）05C31，（次级）。

1简介

计算计数是计算机科学的一个重要领域，人们寻求找到有效的算法来对某些组合对象进行计数，例如独立集、适当的着色或图中的匹配。 更一般地，每个组合计数问题都有一个关联的生成函数，即独立集的独立多项式、用于适当图着色的彩色多项式和更一般的塔特多项式，以及用于匹配的匹配多项式。 此类图多项式在数学和计算机科学以及统计物理学中都有研究，通常被称为配分函数。 一个基本问题是我们可以有效地近似评估这些多项式的图形和数值。 事实上，计数问题对应于在特定值下评估这些图多项式或配分函数。

众所周知，这些计数问题中的许多问题在#P-困难的意义上是计算困难的，即使限制到最大度数最多为三个 [11, 20] 的图也是如此。 另一方面，通过使用强大的马尔可夫链蒙特卡罗技术，针对其中一些#P-hard 问题存在几种有效的随机近似算法。 在一项重大突破中，Weitz [50] 受到统计物理学思想的启发，开发了所谓的相关衰减方法，使他能够获得第一个有效的确定性近似算法，用于计算最大图中的独立集最多五级。 （对于最大度数大于 5 [44] 的图，预计不会有这样的算法，而以前最著名的（随机）算法仅适用于最大度数最多为 4 的图。） 相关衰减方法随后被改进并应用于各种其他问题；参见例如[1, 24, 36, 43] 及其参考文献。

在本文中，我们考虑一种不同的方法。 该方法非常稳健，因为它可以应用于一大类图多项式，并给出第一个通用多项式时间方法来近似有界度图的复值处的图多项式。 最近，Harvey、Srivastava 和 Vondrák [29] 也考虑了独立多项式特殊情况的复杂评估。 图多项式的复杂计算除了是实际计算的自然扩展之外，还作为有趣的计数问题出现，例如计算受限张力或流动可以建模为复杂自旋系统的配分函数（参见[25])，并且任何固定图的同态数量可以建模为复杂边的配分函数-着色模型（参见[47, 48])。

我们工作的另一个重要方面是强调图多项式的根（不存在复杂的）与评估它的有效算法之间的显式关系。 事实上，在下面的备注 1.3 中，我们给出了索卡尔关于色多项式无零区域的猜想与有效逼近有界度图中正确着色数量的臭名昭著的算法问题之间的明确联系。

我们的方法结合了许多成分，包括稀疏图极限[18]的想法、图多项式零点位置的结果和分区函数[42,41,31,8,9, 40] 以及 Barvinok [2] 的算法开发。 Barvinok 的泰勒逼近技术已用于构建确定性拟多项式时间逼近算法，用于评估许多图划分函数（对于一般图）；参见例如Barvinok [2, 3, 4, 5] 的作品，Barvinok 和 Sobeŕon [8, 9] 以及第二作者 [40] 的作品t2>。 我们参考 Barvinok 最近的书 [7] 了解更多背景。

该方法可以大致描述如下。 首先，评估配分函数或图多项式的问题被转换为评估单变量多项式的问题。 接下来，识别该多项式不消失的区域；因此，在该区域中，多项式的对数可以通过低阶泰勒近似（阶$\log n$，其中$n$为多项式的次数）来很好地逼近。 最后，我们必须通过有效计算多项式的第一个 $O(\log n)$ 系数来计算泰勒近似。 到目前为止，这种方法只能产生在拟多项式时间内运行的算法。 本文的主要技术贡献是一种多项式时间算法，用于在我们处理有界度图时计算（本质上）一大类图多项式的第一个 $O(\log n)$ 系数。定理3.1，我们相信它具有独立的意义。

下面我们将陈述并讨论通过将该方法与图多项式和配分函数的根位置的（已知）结果相结合可以获得的一些具体结果。 特别是，我们获得了新的确定性多项式时间算法（FPTAS），用于评估独立多项式、Tutte 多项式，以及在有界度图的情况下计算自旋和边缘着色模型的配分函数。 在我们陈述算法结果之前，我们首先需要一个定义。 由于我们将以复数值近似多项式，因此我们定义了良好近似的含义。

Definition 1.1。

令$q$和$\xi$为非零复数。 如果 $e^{-\epsilon }\le |q|/|\xi |\le e^{\epsilon }$，并且如果 $\xi$ 和 $q$（在 $ℂ={ℝ}^2$ 中视为向量）之间的夹角至多为 $\epsilon$，我们将 $\xi$ 称为 乘法 $\epsilon$ 近似值 $q$ 。

1.1 独立多项式

图$G=(V,E)$的独立多项式用$Z(G)$表示，定义为

$$Z(G)(\lambda ):=\sum _{\begin{array}{c}I\subseteq V\\ I\text{independent}\end{array}}{\lambda }^{|I|}.$$ (1)

在[50]中，Weitz基于相关衰减方法证明，如果，其中

$${\lambda }_c=\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{(\mathrm{\Delta }-2)}^{\mathrm{\Delta }}},$$

那么存在一个确定性算法，给定最大度数最多为 $\mathrm{\Delta }$ 和 $\epsilon >0$ 的图 $G=(V,E)$，计算乘法 $\epsilon$-在时间 ${(|V|/\epsilon )}^{O(1)}$ 上近似于 $Z(G)(\lambda )$。 Sly 和 Sun [44] 通过证明一旦 $\lambda >{\lambda }_c$ 就无法有效逼近 $Z(G,\lambda )$，除非 NP=RP，从而证明了这是严格的。

在第4节中，我们证明了以下结果，该结果是由 Harvey、Srivastava 和 Vondrák [29] 使用相关衰减方法独立获得的。

Theorem 1.1.

让 $\mathrm{\Delta }\in \mathbb{N}$，并让 $\lambda \in ℂ$ 使得 . 然后存在一种确定性算法，给定最大度数最多为 $\mathrm{\Delta }$ 和 $\epsilon >0$ 的图 $G=(V,E)$，计算乘法 $\epsilon$ -在时间${(|V|/\epsilon )}^{O(1)}$中近似于$Z(G)(\lambda )$。

Remark 1.1.

从定理 1.1 的证明可以看出，运行时间实际上受以下限制：

$${(|V|/\epsilon )}^{\frac{D}{1-|\lambda |/{\lambda }^{\ast }(\mathrm{\Delta })}\ln (\mathrm{\Delta })}{|V|}^{D^{\prime }}$$

对于一些绝对常数$D,D^{\prime }$。

定理1.1实际上也适用于多元独立多项式，我们将在4.2小节中简要解释。

对于正值 $\lambda$，自 ${\lambda }_c>{\lambda }^{\ast }$ 以来，我们的结果弱于 Weitz 的结果。 然而我们的结果是否定的 甚至是复杂的$\lambda$。 案例 是相关的，因为它与 Lovász 局部引理相关，参见。 [41]。 我们在此指出，通过 Peters 和第二作者 [38] 的最新结果证实了 Sokal [45] 的猜想，并通过 4.3 下面，我们可以获得韦茨结果的另一种证明。 我们在8节中对此进行了更多讨论。

定理 1.1 中的 ${\lambda }^{\ast }$ 值源于 Shearer 的一篇论文 [42]（另见 Scott 和 Sokal [41]），其中证明了对于最大度 $\mathrm{\Delta }$ 的图形，在满足 $|\lambda |\le {\lambda }^{\ast }$ 的任何 $\lambda \in ℂ$ 处，独立性多项式都不会消失。 而且 ${\lambda }^{\ast }$ 的值也是紧的，因为存在最大度数最多为 $\mathrm{\Delta }$ 和 的树序列 $T_n$，其中 ${\lambda }_n\to -{\lambda }^{\ast }$ 使得$Z(T_n,{\lambda }_n)=0$，参见。 [41，示例 3.6]。 定理 1.1 也是紧的，最近 Galanis、Goldberg 和 Štefankovič 表明，当 时逼近 $Z_G(\lambda )$ 是 NP 困难的。

作为定理 1.1 的扩展，我们能够在几乎整个复平面上有效地近似特殊类无爪图的独立多项式。 我们利用 Chudnovsky 和 ​​Seymour [17] 的结果指出无爪图的独立多项式只有负实根。 我们在4.3小节中证明了以下结果。

Theorem 1.2.

令 $\mathrm{\Delta }\in \mathbb{N}$ 和 $\lambda \in ℂ$ 使得 $\lambda$ 不是实数负数。 然后存在一种确定性算法，给定最大度至多$\mathrm{\Delta }$和$\epsilon >0$的无爪图$G=(V,E)$，计算乘法$\epsilon$-在时间${(|V|/\epsilon )}^{O(1)}$上近似于$Z(G)(\lambda )$。

请注意，当 $G$ 是某个图 $H$ 的折线图时，我们有 $Z_G(\lambda )$ 等于 $H$ 的匹配多项式。因此，特别是，定理 1.2 隐含了 Bayati、Gamarnik、Katz、Nair 和 Tetali [1] 的结果。 然而，我们的证明与[1]中的证明完全不同。

1.2 塔特多项式

图 $G=(V,E)$ 的 Tutte 多项式的随机聚类公式是一个二变量多项式，用 $Z_T(G)$ 表示，定义为

$$Z_T(G)(q,w):=\sum _{A\subseteq E}{q}^{k(A)}{w}^{|A|},$$ (2)

其中 $k(A)$ 表示图 $(V,A)$ 的组件数量。 特别地，如果$w=-1$，则$Z_T(G)(q,-1)$等于$G$的色多项式。

Jerrum 和 Sinclair [33] 表明，当 $q=2$ 和 $w>0$ 时，存在一种随机多项式时间近似算法，用于计算一般 Tutte 多项式的评估。 在 [27] 中，Goldberg 和 Jerrum 表明，在 $q>2$ 和 $w>0$ 的一般图上近似评估 Tutte 多项式与计算二分中的独立集一样困难图以及在 [28] 中，Goldberg 和 Jerrum 表明，对于实数参数 $(q,w)$ 的几种选择，甚至很难在一般图上近似评估 Tutte 多项式。 Goldberg 和Guo [26] 研究了在复值处近似评估一般图的 Tutte 多项式的复杂性。

当$w=-1$和$q\in \mathbb{N}$时，$Z_T(G)(q,w)$给出$G$的$q$颜色的数量。 Lu和Yin [36]表明，当$q>2.58\mathrm{\Delta }$时，存在一种确定性多项式时间算法，可以在最大次数图上逼近$(q,-1)$处的Tutte多项式大多数$\mathrm{\Delta }$。 有许多上述类型的随机算法，在 $q$ 上有更清晰的界限；参见例如杰鲁姆[32]和维戈达[49]。 据我们所知，有界度图上的 Tutte 多项式尚无通用结果。

通过将 $w$ 视为常数，我们将 Tutte 多项式视为单变量多项式。 在第5节中我们证明了以下结果。

Theorem 1.3.

让 $\mathrm{\Delta }\in \mathbb{N}$ 并让 $w\in ℂ$。 Then there exists a constant $K$ (depending on $\mathrm{\Delta }$ and $w$) such that if $q\in ℂ$ is such that $|q|>K$, then there exists a deterministic algorithm, which, given a loopless multigraph $G=(V,E)$ of maximum degree at most $\mathrm{\Delta }$ and $\epsilon >0$, computes a multiplicative $\epsilon$-approximation to $Z(G)(q,w)$ in time ${(|V|/\epsilon )}^{O(1)}$.

Remark 1.2.

根据定理 1.3 的证明，运行时间实际上受以下限制：

$${(|V|/\epsilon )}^{\frac{D}{1-K/|q|}\mathrm{\Delta }\ln (\mathrm{\Delta })}{|V|}^{D^{\prime }}$$

对于一些绝对常数$D,D^{\prime }$。

上述定理中的常数$K$来自Jackson、Procacci和Sokal的一篇论文[31]，不幸的是需要半页纸才能准确说明。 然而，当$w$满足$|1+w|\le 1$（这包括色多项式）时，常数$K$可以被取为$6.91\mathrm{\Delta }$。

Remark 1.3.

索卡尔[30，猜想21]猜想$Z_T(G)(q,-1)\ne 0$与$\mathrm{\Re }(q)>\mathrm{\Delta }(G)$一样长。 结合我们的结果（以及第 4.3 节中的技术），这一猜想的证实将意味着一种高效的近似算法，可用于计算最大度最多为 $\mathrm{\Delta }$ 的任何图 $G$ 的 $(\mathrm{\Delta }+1)$ 着色数目，这是计算计数中一个臭名昭著的问题。

1.3 自旋模型的配分函数

令 $A\in {ℂ}^{k\times k}$ 为对称矩阵。 在统计物理学的背景下，$A$ 通常被称为自旋模型 cf. [19]。 对于图$G=(V,E)$,$A$的配分函数定义为

$$p(G)(A)=\sum _{\varphi :V\to [k]}\prod _{\{u,v\}\in E}{A}_{\varphi (u),\varphi (v)}.$$ (3)

如果$A$是某个图$H$的邻接矩阵，则$p(G)(H)$等于从$G$到$H$。 [8]中的$p(G)(A)$称为图同态配分函数。

基于 Dyer 和 Greenhill [21] 以及 Bulatov 和 Grohe [12] 发起的一系列研究，完整的二分定理已被证明可以精确计算Cai、Chen 和 Lu 提出的复杂自旋模型的配分函数[13]。 这种二分法实质上是说，除非矩阵 $A$ 具有某种特殊结构，否则精确计算 $A$ 的配分函数是 #P 困难的。

Lu 和 Yin [36]使用相关性衰减方法证明，对于固定的 $\mathrm{\Delta }\in \mathbb{N}$，如果实矩阵 $A$ 与全一矩阵足够接近（即对于所有 ），则存在用于计算乘法 的 时算法。对于所有 $i,j=1,\mathrm{\dots }k$，$|A_{i,j}-1|\le O(1)/\mathrm{\Delta }$），则存在一种 ${(|V(G)|/\epsilon )}^{O(1)}$ 时算法，可以在最大度最多为 $\mathrm{\Delta }$ 的图上计算出 近似于 $P(G)(A)$ 的乘法 $\epsilon$。Barvinok 和 Sobéron [8]证明，对于满足 $|A_{i,j}-1|\le O(1)/\mathrm{\Delta }$ 的所有 $i,j=1,\mathrm{\dots },k$ 的复值矩阵 $A$，存在一种 ${(|V(G)|/\epsilon )}^{O(\ln |V(G)|)}$ 时算法。

基于 Barvinok 和 Sobéron 的工作，我们在第 6 节中证明了以下结果。

Theorem 1.4.

让$\mathrm{\Delta },k\in \mathbb{N}$。 那么存在一个确定性算法，给定一个最大度数最多为$\mathrm{\Delta }$的图$G=(V,E)$，一个（复值）对称$k\times k$矩阵$A$ 使得 $|A_{i,j}-1|\le 0.34/\mathrm{\Delta }$ 对于所有 $i,j=1,\mathrm{\dots },k$ 和 $\epsilon >0$ 计算乘法 $\epsilon$ - 近似于 $p(G)(A)$ 时间 ${(|V|/\epsilon )}^{O(1)}$。

Remark 1.4.

如果$\mathrm{\Delta }\ge 3$，常量$0.34$可以被$0.45$替换，如果$\mathrm{\Delta }$足够大，则可以被$0.54$替换，参见[8]。

在[9]中，Barvinok和Soberón引入了具有多重性的$G$图同态的配分函数，并给出了用于计算某些矩阵的拟多项式时间算法。 在第 6 节中，我们将表明我们的结果也适用于这些配分函数。

1.4边缘着色模型的配分函数

边缘着色模型起源于统计物理学，其配分函数已由 de la Harpe 和 Jones [19] 引入图论界（称为顶点模型）。 我们将任何地图$h:{\mathbb{N}}^k\to ℂ$称为$k$颜色边缘着色模型。 对于图$G=(V,E)$,$h$的划分函数定义为

$$p(G)(h):=\sum _{\varphi :E\to [k]}\prod _{v\in V}h(\varphi (\delta (v))),$$ (4)

其中 $\delta (v)$ 表示与顶点 $v$ 相关的边集，$\varphi (\delta (v))$ 表示顶点 $v$ “看到”的多组颜色，我们用 ${\mathbb{N}}^k$ 中的关联向量来识别它，以便我们可以将 $h$ 应用于它。 明确地，如果对于每个 $i$ 都有 $a_i$ 次出现颜色 $i$，则 $\varphi (\delta (v))$ 被向量 $(a_1,\mathrm{\dots },a_k)\in {\mathbb{N}}^k$ 标识> 在与 $v$ 相关的边之间。

边着色模型的分区函数构成了一类丰富的图参数，包括匹配数（取 $h:{\mathbb{N}}^2\to ℂ$ 如果 ${\alpha }_1\le 1$ 则 $h(\alpha )=1$ 定义，否则 $0$ 定义），以及自旋模型的分区函数，正如 Szegedy [47, 48] 所证明的那样。 这些配分函数可以看作Holant问题；参见例如[15,16,14]。 它们也可以被视为张量网络收缩。 我们建议读者参阅[39]以了解更多背景信息。

正如自旋模型的配分函数一样，为了精确计算 Holant 问题，已经做了很多工作来建立复杂性二分法结果；请参阅[15,16,14]。 除了一些特殊情况外，人们对边缘着色模型的近似配分函数的复杂性知之甚少。 如前所述，Bayati、Gamarnik、Katz、Nair 和 Tetali [1] 找到了一种有效的近似算法，用于计算有界度图中的匹配，Lin、Liu 和 Lu [35] 找到了计算边缘覆盖的有效近似算法。 这两种算法都是基于相关衰减方法。

基于第二作者[40]的工作，我们将在第7节中证明以下结果。

Theorem 1.5.

让$\mathrm{\Delta },k\in \mathbb{N}$。 那么存在一个确定性算法，给定一个最大度数最多为$\mathrm{\Delta }$的多重图$G=(V,E)$，一个$k$-颜色边缘着色模型$h$ 使得 $|h(\varphi )-1|\le 0.35/(\mathrm{\Delta }+1)$ 对于所有 $\varphi \in {\mathbb{N}}^k$ 和 $\epsilon >0$ 计算乘法 $\epsilon$ - 近似于 $p(G)(h)$ 及时${(|V|/\epsilon )}^{O(1)}$。

Remark 1.5.

如果$\mathrm{\Delta }\ge 3$常量$0.35$可以被$0.47$替代，如果$\mathrm{\Delta }$足够大则可以被$0.56$替代；请参阅[40]。 此外，对于熟悉这些配分函数的正交群不变性的读者来说，有趣的是，我们可以使用 [40] 中的推论 6b 来找到一个更大的边缘着色模型族，其中可以有效地近似配分函数。

1.5组织

在下一节中，我们将考虑 Barvinok [2] 提出的算法来近似估计多项式。 3部分包含我们的主要技术贡献：我们将介绍一类图多项式，并给出一种在有界度图上计算其低阶系数的有效算法。 然后，这两种算法（或其变体）将在第 4–7 节中组合起来，以证明上述结果。 这些部分可以相互独立地阅读。 最后，我们在第 8 节中提出一些评论和问题。

2 多项式的近似计算

在本节中，我们提出了一种由 Barvinok [2] 提出的算法，用于近似评估多项式。 为了完整起见，我们采取稍微不同的方法并提供完整的细节。

令 $p\in ℂ[z]$ 为 $d$ 次多项式 $p(z)=a_0+a_{1}z+\mathrm{\cdots }+a_d{z}^d$，并假设开放磁盘中的所有 $z$ 的 $p(z)\ne 0$ $D$ 半径为 $M$。在此磁盘上定义函数 $f$

$$f(z):=\ln p(z),$$ (5)

（其中我们通过将对数的主值固定在 $p(0)$ 处来固定对数的分支）。 回想一下泰勒定理，对于每个 $t\in D$,$f(t)={\sum }_{j=0}^{\mathrm{\infty }}\frac{t^j}{j!}{f}^{(j)}(0)$。 为了在 $t\in D$ 处逼近 $p$，我们将通过截断 $z=0$ 附近的泰勒扩展，在 $t$ 处找到 $f$ 的加法近似值。 对于每个 $m\in \mathbb{N}$，让

$$T_m(f)(t):=f(0)+\sum _{j=1}^m\frac{t^j}{j!}{f}^{(j)}(0).$$ (6)

然后可以将其转换为 $p$ 的乘法近似值。我们使用下面推导的稍微不同的 (6) 形式会更方便。

令 ${\zeta }_1,\mathrm{\dots },{\zeta }_d\in ℂ$ 为 $p$ 的根。然后我们可以写$p(z)=a_d(z-{\zeta }_1)\mathrm{\cdots }(z-{\zeta }_d)$和$f(z)=\ln (a_d)+\ln (z-{\zeta }_1)+\mathrm{\cdots }+\ln (z-{\zeta }_d)$。 由此我们可以看出 $f^{\prime }(z)={(z-{\zeta }_1)}^{-1}+\mathrm{\cdots }+{(z-{\zeta }_d)}^{-1}$ 以及 $j\ge 1$，

$$f^{(j)}(0)=-(j-1)!\sum _{i=1}^d{\zeta }_i^{-j}.$$

因此将$j$第逆幂和定义为$p_j:={\zeta }_1^{-j}+\mathrm{\cdots }+{\zeta }_d^{-j}$我们看到

$$T_m(f)(t)=f(0)-\sum _{j=1}^m\frac{p_j{t}^j}{j}=\ln (a_0)-\sum _{j=1}^m\frac{p_j{t}^j}{j}.$$ (7)

在下一个命题中，我们推导出牛顿恒等式的一个变体，它将逆幂和与多项式的系数联系起来。

Proposition 2.1.

对于上面定义的多项式 $p(z)=a_0+\mathrm{\cdots }+a_d{z}^d$ 及其逆幂和 $p_j$，我们对每个 $k=1,2,\mathrm{\dots }$ 有

$$k{a}_k=-\sum _{i=0}^{k-1}{a}_i{p}_{k-i}.$$

（这里如果$i>d$，我们就采用$a_i=0$。）

证明。

从(7)我们知道对于$z\in D$我们有$\ln (p(z))=\ln (a_0)-{\sum }_{j=1}^{\mathrm{\infty }}\frac{p_j{z}^j}{j}$。 两边求微分并乘以 $p(z)$ 我们得到

$$p^{\prime }(z)=-p(z)\sum _{j=1}^{\mathrm{\infty }}{p}_j{z}^{j-1}$$

所以

$$\sum _{k=1}^{d}k{a}_k{z}^{k-1}=-\sum _{i=0}^d{a}_i{z}^i\sum _{j=1}^{\mathrm{\infty }}{p}_j{z}^{j-1}.$$

比较每一侧的 $z^{k-1}$ 系数即可得出所需的同一性。 ∎

下一个引理表明，近似值 (6) 以及 (7) 的质量取决于 $p$ 复数根的位置。

Lemma 2.2.

给定满足的$M>0$和$t\in ℂ$，存在常数$C=C(t,M)\le {(1-|t|/M)}^{-1}$使得以下成立。 假设$p$是$d$次多项式，在半径$M$的开盘$D$中没有根。那么对于每个 $\epsilon >0$,$\exp (T_m(f)(t))$ 是 $\epsilon$ 的乘法近似 $p(t)$，其中 $m=C\ln (d/\epsilon )$。

证明。

让$q:=|t|/M$。 然后，作为，我们有。 我们将首先证明

$$\left|f(t)-T_m(f)(t)\right|\le \frac{d{q}^{m+1}}{(m+1)(1-q)}.$$ (8)

到 (7) 我们有

$$|f(t)-T_m(f)(t)|\le \left|\sum _{j=m+1}^{\mathrm{\infty }}\frac{p_j{t}^j}{j}\right|\le \frac{1}{m+1}\sum _{j=m+1}^{\mathrm{\infty }}|p_j{t}^j|.$$ (9)

通过假设，我们知道每个 $i=1,\mathrm{\dots },d$ 都有 $|{\zeta }_i|\ge M$。 因此 $|p_j|\le d/M^j$ 和 $|p_j{t}^j|\le d{q}^j$。 将其代入 (9) 并使用 我们得到 (8)。

以 $m=C\ln (d/\epsilon )$ 为例，其中 $C$ 的选择使得 $C\ge {(\ln 1/q)}^{-1}$ 和 $1/m\le 1-q$ （因此很容易检查，例如 $C={(1-q)}^{-1}$ 就足够了）。 那么(8)的右边最多是$\epsilon$。 写入$z=T_m(f)(t)$。 然后我们有 $|e^{f(t)-z}|\le e^{|f(t)-z|}\le e^{\epsilon }$ 和类似的 $|e^{z-f(t)}|\le e^{\epsilon }$。 （这是因为对于复数 $y=a+bi$，我们有 $|e^y|=e^a\le e^{|y|}$。） 此外，$e^z$和$e^{f(t)}$之间的角度以$|\mathrm{\Im }\ln e^{z-f(t)}|\le |\ln e^{z-f(t)}|\le \epsilon$为界。 这表明 $e^z=\exp (T_m(f)(t))$ 是 $\epsilon$ 的乘法近似 $p(t)$。 ∎

根据 (7) 和 Lemma 2.2，如果我们有一种有效的方法来计算从 $j=1$ 到 $O(\ln (\mathrm{deg}(p)))$ 的反幂和 $p_j$（根据命题 2.1 本质上等价于计算 $p$ 的第一个 $O(\ln (\mathrm{deg}(p)))$ 系数），那么我们就有一种有效的方法来近似计算 $p$ 在零点附近圆盘上各点的求值，其中 $p$ 是非消失的。 我们在下面的推论中将其形式化。 在下一节中，我们将展示对于某些类型的图多项式，我们可以有效地计算逆幂和。

Corollary 2.3.

给定满足的$M>0$和$t\in ℂ$，存在常数$C=C(t,M)\le {(1-|t|/M)}^{-1}$使得以下成立。 假设$p$是由$p(z)=a_0+a_{1}z+\mathrm{\cdots }+a_d{z}^d$给出的多项式，在半径为$M$的开盘$D$中没有根。进一步假设我们能够计算每个 $r=1,\mathrm{\dots },d$ 的 $a_0$ 以及时间 $\tau (r)$ 的逆幂和 $p_1,\mathrm{\dots },p_r$。 然后我们可以在时间 $O(\tau (m))$（其中 $m=C\ln (d/\epsilon )$)内计算 $p(t)$ 的乘法 $\epsilon$ 近似值。

证明。

推论直接来自 (6)、(7) 和引理 2.2。 ∎

3 计算图多项式的系数

在本节中，我们将介绍我们的主要技术贡献，这是计算有界度图的一大类图多项式的逆幂和（以及系数）的有效方法。 在整个过程中，我们将重点关注图多项式，其系数可以表示为导出子图计数的线性组合。 请注意，在本节中，我们不对多项式根的位置做出任何假设。 本节中的结果仅针对图给出，但实际上对于多重图有效。 因此读者可以在本节中的任何地方阅读多重图而不是图。 （多重图中顶点的度是与该顶点相关的边的数量，其中循环被计数两次。）

我们从一些定义开始，然后陈述本节的主要结果。 如果存在双射 $f:V_H\to V_G$，从而对于任意 $u,v\in V_H$，当且仅当 $uv\in E_H$ 时，我们有 $f(u)f(v)\in E_G$，则称两个图 $H=(V_H,E_H)$ 和 $G=(V_G,E_G)$ 为 同构。 如果存在一个子集 $S\subseteq V_G$，使得 $H$ 与 $G[S]$（即 $S$ 所诱导的图形）同构，我们就说 $H$ 是 $G$ 的诱导子图。我们将 $\text{ind}(H,G)$ 写为 $S\subseteq V_G$ 中使 $H$ 与 $G[S]$ 同构的集合数（即 $G$ 与 $H$ 同构的诱导子图的个数）。 请注意，如果 $H$ 是空图，则所有 $G$ 都具有 $\text{ind}(H,G)=1$。

通过 $𝒢$ 我们表示所有图的集合，通过 ${𝒢}_k$ 对于 $k\in \mathbb{N}$ 我们表示最多具有 $k$ 个顶点的图的集合。 图不变量是某个集合 $S$ 的函数 $f:𝒢\to S$，它在同构图上采用相同的值。 图多项式是图不变量$p:𝒢\to ℂ[z]$，其中$ℂ[z]$表示复数域上变量$z$中的多项式环数字。 如果对于所有图形 $G_1,G_2$（此处 $G_1\cup G_2$ 表示图形 $G_1$ 和 $G_2$ 的不相交联盟），$f(\mathrm{\varnothing })=1$ 和 $f(G_1\cup G_2)=f(G_1)f(G_2)$ 都是不变的，则称图形 $f$ 为多变的。

Definition 3.1。

令 $p$ 为乘法图多项式，定义为

$$p(G)(z):=\sum _{i=0}^{d(G)}{e}_i(G)z^i$$ (10)

对于每个 $G\in 𝒢$ 和 $e_0(G)=1$。 如果存在满足以下两个条件的常数$\alpha ,\beta \in \mathbb{N}$，我们将$p$称为有界诱导图计数多项式（BIGCP）：

• 对于每个图$G$，系数$e_i$满足

  $$e_i(G):=\sum _{H\in {𝒢}_{\alpha i}}{\lambda }_{H,i}\text{ind}(H,G)$$ (11)

  对于某些${\lambda }_{H,i}\in ℂ$；

• 对于每个$H\in {𝒢}_{\alpha i}$，可以在时间$O({\beta }^{|V(H)|})$中计算系数${\lambda }_{H,i}$。

例如，如果对于每个 $i$， (10) 中的系数 $e_i(G)$ 等于 $G$ 中大小为 $i$ 的独立集合的个数，那么很容易看出 $p$（当然是独立多项式）是一个 BIGCP。 在这种情况下，用于计算 $n$ 顶点图 $G$ 的系数 $e_i(G)$ 的明显强力算法在 $O(n^i)$ 时间内运行（通过检查 $V(G)$ 的所有 $i$ 子集），如果 $i=O(\ln n)$ 则这是拟多项式时间。 本节的主要结果是计算 BIGCP 的逆幂和（以及命题 2.1 的 BIGCP 系数）的通用算法，当应用于本示例时，计算 $e_i(G)$ 即使 $i=O(\ln n)$ 也在多项式时间内，只要 $G$ 的最大次数有界。

Theorem 3.1.

令 $C>0$ 和 $\mathrm{\Delta }\in \mathbb{N}$ 以及 $p(\cdot )$ 为有界诱导图计数多项式。 然后有一个确定性的${(n/\epsilon )}^{O(1)}$-时间算法，给定任何$n$-顶点图$G$，其最大度数最多为$\mathrm{\Delta }$并且任何$\epsilon >0$，计算$m=C\ln (n/\epsilon )$的$p(G)$的逆幂和$p_1,\mathrm{\dots },p_m(G)$。

Remark 3.1.

上述定理中的算法只能通过BIGCP定义中的条件(ii)访问多项式$p$，即它仅依赖于计算复数${\lambda }_{H,i}$的算法>。

Remark 3.2.

假定 $\mathrm{\Delta }\ge 3$，上述定理的证明实际上得到的运行时间为 $n^{C_1}{(n/\epsilon )}^{C_2}={(n/\epsilon )}^{O(1)}$，其中 $C_1$ 可以明确确定（并且不依赖于 $\alpha ,\beta ,C$ 和 $\mathrm{\Delta }$），我们可以粗略地取 $C_2=10C\alpha \ln (\beta \mathrm{\Delta })$，其中 $\alpha$ 和 $\beta$ 是 BIGCP 定义中的常数。

在证明定理 3.1 之前，我们将首先收集一些有关诱导子图计数以及图中出现的固定大小的连接诱导子图的数量的事实，我们将需要这些事实来进行证明。

3.1 归纳子图计数

通过$G\mapsto \text{ind}(H,G)$定义$\text{ind}(H,\cdot ):𝒢\to ℂ$。 因此我们将 $\text{ind}(H,\cdot )$ 视为图不变量。 我们可以采用这些不变量的线性组合和乘积。 特别是，对于两个图 $H_1,H_2$ 我们有

$$\text{ind}(H_1,\cdot )\cdot \text{ind}(H_2,\cdot )=\sum _{H\in 𝒢}{c}_{H_1,H_2}^H\text{ind}(H,\cdot ),$$ (12)

其中对于图 $H$,$c_{H_1,H_2}^H$ 是 $V(H)$、$(S,T)$ 子集的有序对数量，使得 $S\cup T=V(H)$ 和 $H[S]$ 与 $H_1$ 同构，$H[T]$ 与 $H_2$ 同构。 特别是，给定 $H_1$ 和 $H_2$,$c_{H_1,H_2}^H$ 仅对于有限数量的图 $H$ 为非零。

计算参数$\text{ind}(H,G)$通常很困难，但是如果连接$H$（并且$V(H)$不太大）和$G$，则变得更容易具有有限度。

Lemma 3.2。

令 $H$ 为 $k$ 顶点上的连通图，并令 $\mathrm{\Delta }\in \mathbb{N}$。 然后

• 有一个 $O(n{\mathrm{\Delta }}^{k-1})$-时间算法，给定任何 $n$-顶点图 $G$最多具有最大度数$\mathrm{\Delta }$，检查是否$\text{ind}(H,G)\ne 0$;0>

• 有一个 $O(k^2{n}^2{\mathrm{\Delta }}^{2(k-1)})$-时间算法，给定任何 $n$-顶点图 $G$最大度数最多$\mathrm{\Delta }$，计算数字$\text{ind}(H,G)$。0>

请注意，引理 3.2 (i) 使我们能够在 $|V(G)|=|V(H)|$ 时测试有界度图之间的图同构。

证明。

让我们列出 $V(H)$、$v_1,\mathrm{\dots },v_k$ 的顶点，使得 $i\ge 1$ 顶点 $v_i$ 在 $v_1,\mathrm{\dots },v_{i-1}$ 然后，为了将 $H$ 嵌入到 $G$ 中，我们首先为 $v_1$ 选择一个目标顶点，然后假设我们已将 $v_1,\mathrm{\dots },v_{i-1}$ 嵌入到 $i\ge 2$ 对于嵌入 $v_i$ 的位置，最多有 $\mathrm{\Delta }$ 个选择。 经过 $k$ 次迭代后，我们总共最多有 $n{\mathrm{\Delta }}^{k-1}$ 种可能的嵌入 $H$ 的方法，并且在上面的过程中检查每种可能性。 因此，我们确定在 $O(n{\mathrm{\Delta }}^{k-1})$ 时间内 $\text{ind}(H,G)$ 是否为零。

上面的过程给出了所有集合$S\subseteq V(G)$的列表$L$（大小最多为$n{\mathrm{\Delta }}^{k-1}$)，使得$G[S]$与$H$，尽管列表可能包含重复项。 消除重复需要时间$O(k^2{|L|}^2)=O(k^2{n}^2{\mathrm{\Delta }}^{2(k-1)})$（通过比较$L$中的每对元素），结果列表的长度给出$\text{ind}(H,G)$的值。 ∎

接下来我们考虑如何枚举有界度图中所有可能的固定大小的连通归纳子图。 我们需要 Borgs、Chayes、Kahn 和 Lovász [10，引理 2.1] 的以下结果：

Lemma 3.3。

令$G$为最大度$\mathrm{\Delta }$的图。 修复 $G$ 的顶点 $v_0$。那么$G$与$k$顶点包含顶点$v_0$的连通导出子图的数量最多为$\frac{{(e\mathrm{\Delta })}^{k-1}}{2}$。

因此，我们可以有效地枚举有界度图 $G$ 中出现的所有对数大小的连通导出子图。

Lemma 3.4。

有一种 $O(n^2{k}^7{(e\mathrm{\Delta })}^{2k})$ 时算法，在给定 $k\in \mathbb{N}$ 和最大度 $\mathrm{\Delta }$ 的 $n$ 顶点图 $G=(V,E)$ 的情况下，输出 ${𝒯}_k$，即满足 $|S|\le k$ 和 $G[S]$ 连接的所有 $S\subseteq V$ 的集合。

证明。

根据前面的结果，我们知道$|{𝒯}_k|\le nk{(e\mathrm{\Delta })}^{k-1}$对于所有$k$。

我们归纳构造${𝒯}_k$。 对于$k=1$,${𝒯}_k$显然是单例顶点的集合，并且需要时间$O(n)$来输出。

鉴于我们已经找到了 ${𝒯}_{k-1}$，我们计算 ${𝒯}_k$ 如下。 我们首先计算多重集

$${𝒯}_k^{\ast }=\{S\cup \{v\}:S\in {𝒯}_{k-1}\text{and}v\in N_G(S)\}.$$

这里$|N_G(S)|\le |S|\mathrm{\Delta }\le k\mathrm{\Delta }$需要时间$O(k\mathrm{\Delta })$来查找（假设$G$以邻接表形式给出）。 因此计算${𝒯}_k^{\ast }$需要时间$O(|{𝒯}_{k-1}|k\mathrm{\Delta })=O(n{k}^2{(e\mathrm{\Delta })}^k)$，这也是${𝒯}_k^{\ast }$的大小。 最后，我们通过删除 ${𝒯}_k^{\ast }$ 中的重复项（通过将每个元素与所有先前元素进行比较）来计算集合 ${𝒯}_k$，这需要时间 $O(k^2{|{𝒯}_k^{\ast }|}^2)=O(n^2{k}^6{(e\mathrm{\Delta })}^{2k})$。

从${𝒯}_1$开始，我们执行上述迭代$k$次，总共需要运行$O(n^2{k}^7{(e\mathrm{\Delta })}^{2k})$次。

剩下的只是表明 ${𝒯}_k$ 包含我们想要的所有集合。 显然 ${𝒯}_{k-1}\subset {𝒯}_k$ 并通过归纳假设 ${𝒯}_{k-1}$ 包含所有大小为 $k-1$ 且与 $G[T]$ 连接的 $T\subset V$。 给定 $S\subseteq V$，使得 $|S|=k$ 和 $G[S]$ 连接，取 $G[S]$ 的任何树，删除叶子 $v$并将生成的顶点集称为$S^{\prime }$。 那么很明显 $S^{\prime }\in {𝒯}_{k-1}$ 这意味着 $S=S^{\prime }\cup \{v\}\in {𝒯}_k$。 ∎

如果对于每个 $G_1,G_2\in 𝒢$ 我们有 $f(G_1\cup G_2)=f(G_1)+f(G_2)$，我们称图不变 $f:𝒢\to ℂ$ 可加性。 以下引理是 Csikvári 和 Frenkel [18] 引理的变体；这是我们方法的基础。

Lemma 3.5。

令 $f:𝒢\to ℂ$ 为由 $f(\cdot ):={\sum }_{H\in 𝒢}{a}_H\text{ind}(H,\cdot )$ 给出的图不变量。 那么 $f$ 是可加的，当且仅当 $a_H=0$ 对于所有断开连接的图 $H$ 而言。

证明。

让 $H$ 连接起来。 然后对于$G_1,G_2\in 𝒢$，我们有$\text{ind}(H,G_1\cup G_2)=\text{ind}(H,G_1)+\text{ind}(H,G_2)$，因为$H$已连接。 因此 $\text{ind}(H,\cdot )$ 是可加的。 显然，加性图参数的线性组合又是加性的。 这意味着如果连接图支持 $f$，则 $f$ 是可加的。

接下来假设 $f$ 是可加的。 如果 $H$ 已断开连接，我们需要显示 $a_H=0$。 通过前一部分的证明，我们可以假设所有连通图$H$都具有$a_H=0$。现在让 $H=H_1\cup H_2$ 与 $H_1$ 和 $H_2$ 都非空。 我们可以通过归纳假设，对于顺序严格小于 $k:=|V(H)|$ 的所有图 $H^{\prime }$，我们都有 $a_{H^{\prime }}=0$。 现在，通过可加性我们有

$$f(H)=f(H_1)+f(H_2)=\sum _{H^{\prime }:|V(H^{\prime })|\ge k}{a}_{H^{\prime }}(\text{ind}(H^{\prime },H_1)+\text{ind}(H^{\prime },H_2))=0,$$

从 到 $i=1,2$。 另一方面我们有

$$f(H)=\sum _{H^{\prime }:|V(H^{\prime })|\ge k}{a}_{H^{\prime }}\text{ind}(H^{\prime },H)=a_H\text{ind}(H,H).$$

作为$\text{ind}(H,H)\ne 0$，这意味着$a_H=0$并完成证明。 ∎

3.2 定理证明3.1

回想一下，$p(\cdot )$ 是有界归纳图计数多项式 (BIGCP)。 给定一个 $n$ 顶点图 $G$，其最大度数至多 $\mathrm{\Delta }$，我们必须展示如何计算第一个 $m$ 逆幂和时间 ${(n/\epsilon )}^{O(1)}$ 中 $p(G)$ 的 $p_1,\mathrm{\dots },p_m$，其中 $m=C\ln (n/\epsilon )$。 为了减少符号，我们将 写为 $p=p(G)$，将 $p$ 的次数写为 $d=d(G)$，将 $i=0,\mathrm{\dots },d$ 写为 $e_i=e_i(G)$。为 $p$ 的系数（来自 (10)）。 回想一下 $p_k:={\zeta }_1^{-k}+\mathrm{\cdots }+{\zeta }_d^{-k}$，其中 ${\zeta }_1,\mathrm{\dots },{\zeta }_d\in ℂ$ 是多项式 $p(G)$ 的根。

注意到$e_0=1$，命题2.1给出

$$p_k=-k{e}_k-\sum _{i=1}^{k-1}{e}_i{p}_{k-i},$$ (13)

对于每个 $k=1,\mathrm{\dots },d$。 由(11)可知，对于$i\ge 1$,$e_i$可以表示为最多具有$\alpha i$的图的导出子图计数的线性组合> 顶点。 从 $p_1=-e_1$ 开始，这意味着 $p_1$ 也是如此。 通过归纳，(12) 和 (13) 我们得到每个 $k$

$$p_k=\sum _{H\in {𝒢}_{\alpha k}}{a}_{H,k}\text{ind}(H,G),$$ (14)

对于某些但未知的系数$a_{H,k}$。

由于 $p$ 是乘法，因此逆幂和是加法。 因此，引理 3.5 意味着如果 $H$ 未连接，则 $a_{H,k}=0$ 。 用 ${𝒞}_i(G)$ 表示阶数最多为 $i$ 的连通图集合，它们作为 $G$ 中的导出子图出现。这样我们就可以将(14)重写如下：

$$p_k=\sum _{H\in {𝒞}_{\alpha k}(G)}{a}_{H,k}\text{ind}(H,G).$$ (15)

下一个引理表明我们可以有效地计算 $k=1,\mathrm{\dots },m$ 的系数 $a_{H,k}$，其中 $m=C\ln (n/\epsilon )$。

Lemma 3.6。

有一个 ${(n/\epsilon )}^{O(1)}$ 时间算法，给定一个 BIGCP $p$ 和一个有界最大度的 $n$ 顶点图 $G$，计算并列出 (15) 中所有 $H\in {𝒞}_{\alpha k}(G)$ 和所有 $k=1,\mathrm{\dots },m=C\ln (n/\epsilon )$ 的系数 $a_{H,k}$。

证明。

使用引理3.4的算法，我们首先计算由$V(G)$的所有子集$S$组成的集合${𝒯}_{\alpha k}$，使得$|S|\le \alpha k$与$G[S]$相连，为$k=1\mathrm{\dots },m$。 这需要的时间以 ${(n/\epsilon )}^{O(1)}$ 为界。 （请注意，引理 3.4 中的算法计算并列出 $i=1,\mathrm{\dots },\alpha m$ 的所有集合 ${𝒯}_i$。） 接下来，我们通过考虑图集 $\{G[S]\mid S\in {𝒯}_{\alpha k}\}$ 并使用引理 3.2 (i) 删除同构图的副本来计算并列出 ${𝒞}_{\alpha k}(G)$ 中的图来测试同构。 每个 $k$ 最多需要 ${(n/\epsilon )}^{O(1)}$ 时间，因此计算和列出 ${𝒞}_{\alpha k}(G)$ 的总时间受 ${(n/\epsilon )}^{O(1)}$ 限制。

为了证明该 Lemma，让我们固定 $k\le m$，并演示如何计算系数 $a_{H,k}$，假设我们已经计算并列出了所有 的系数 $a_{H,k^{\prime }}$。让我们固定 $H\in {𝒞}_{\alpha k}(G)$。 通过 (13)，足以计算 $i=1,\mathrm{\dots },k$ 的 $p_{k-i}{e}_i$ 中 $\text{ind}(H,\cdot )$ 的系数（其中我们设置 $p_0=1)$. 根据 (11)、(12) 和 (14)，我们知道 $\text{ind}(H,\cdot )$ 在 $p_{k-i}{e}_i$ 中的系数为

$$\sum _{H_1,H_2}{c}_{H_1,H_2}^H{a}_{H_2,(k-i)}{\lambda }_{H_1,i}=\sum _{(S,T):S\cup T=V(H)}{a}_{H[T],(k-i)}{\lambda }_{H[S],i}.$$ (16)

作为$|V(H)|\le \alpha k=O(\ln (n/\epsilon ))$，(16)中的第二个和最多结束$4^{\alpha k}={(n/\epsilon )}^{O(1)}$对$(S,T)$。 对于每个这样的对，我们需要计算 ${\lambda }_{H[S],i}$ 并查找 $a_{H[T],(k-i)}$。 我们可以在 ${\beta }^{|S|}={(n/\epsilon )}^{O(1)}$ 范围内计算 ${\lambda }_{H[S],i}$，因为 $p$ 是一个 BIGCP。

在给定列表中查找 $a_{H[T],(k-i)}$ 需要我们测试 $H[T]$ 与 ${𝒞}_{\alpha (k-i)}(G)$ 中每个图的同构（请注意 $a_{H[T],(k-i)}=0$ 如果 $H[T]\notin {𝒞}_{\alpha (k-i)}(G)$ 由引理3.5)。 使用引理3.2(i)来测试图同构，这最多需要时间

$$O(|{𝒞}_{\alpha (k-i)}(G)|\alpha (k-i){\mathrm{\Delta }}^{\alpha (k-i)-1})=O{(n/\epsilon )}^{O(1)}.$$

这里我们使用引理3.3来绑定$|{𝒞}_{\alpha (k-i)}(G)|$。 总之，所有这些意味着 $p_{k-i}{e}_i$ 中 $\text{ind}(H,\cdot )$ 的系数可以在 ${(n/\epsilon )}^{O(1)}$ 限制的时间内计算出来，因此系数 $a_{H,k}$可以在时间${(n/\epsilon )}^{O(1)}$内计算。 因此，$H\in {𝒞}_{\alpha k}(G)$ 的所有系数 $a_{H,k}$ 都可以在 $|{𝒞}_{\alpha k}(G)|{(n/\epsilon )}^{O(1)}={(n/\epsilon )}^{O(1)}$ 限定的时间内计算并列出。 这可以在时间 ${(n/\epsilon )}^{O(1)}$ 内对每个 $k=1,\mathrm{\dots },m$ 完成。 ∎

为了完成定理的证明，我们通过将所有数字 $a_{H,k}\text{ind}(H,G)$ 添加到所有 $H\in {𝒞}_{\alpha k}(G)$ 上来计算每个 $k=1,\mathrm{\dots },m$ 的 $p_k$。 这可以及时完成

$$O(m|{𝒞}_{\alpha m}(G)|{(\alpha m)}^2{n}^2{\mathrm{\Delta }}^{2(\alpha m-1)})={(n/\epsilon )}^{O(1)},$$

我们使用引理 3.2(ii) 计算 $\text{ind}(H,G)$ 和 $H\in {𝒞}_{\alpha k}(G)$ 需要时间 $O({(\alpha k)}^2{n}^2{\mathrm{\Delta }}^{2(\alpha k-1)})$。

3.3 彩色图的扩展

在本节中，我们将处理彩色图表的情况，稍后我们将需要它。 事实上，所有早期的证明都是针对彩色案例逐行进行的，但为了便于说明，我们选择避免​​过度概括。 在这里，我们重申了彩色情况的各种定义并重申了主要定理。

让我们将自然数 $\mathbb{N}$ 固定为一组颜色。 令 $H=(V_H,E_H)$ 和 $G=(V_G,E_G)$ 为图，其顶点（分别为 边）从集合 $T$ 中着色（不一定正确）。 对于顶点颜色图 $H=(V_H,E_H)$ 和 $G=(V_G,E_G)$，我们将 $H$ 和 $G$ 定义为 颜色同构，如果$H$ 和 $G$ 之间存在颜色同构，即图形同构 $f:V_H\to V_G$，使得 $u$ 和 $f(u)$ 对于每个 $u\in V(H)$ 对于边缘彩色图 $H=(V_H,E_H)$ 和 $G=(V_G,E_G)$，我们将 $H$ 和 $G$ 定义为 颜色同构，如果$H$ 和 $G$ 之间存在颜色同构，即图形同构 $f:V_H\to V_G$，使得 $uv$ 和 $f(uv)$ 的每条边 $uv\in V(H)$ 在顶点和边着色的情况下，如果存在一个子集 $S\subseteq V_G$，使得 $H$ 与 $G[S]$（由 $S$（从 $G$ 的着色中继承颜色）诱导的图形）颜色同构，我们就说 $H$ 是 $G$ 的诱导着色子图。 我们写 ${\text{ind}}_{vc}(H,G)$ （分别是 ${\text{ind}}_{ec}(H,G)$)表示集合 $S\subseteq V_G$ 的数量，使得 $H$ 与 $G[S]$ 颜色同构（即导出的彩色子图的数量$G$ 同构于 $H$)。

然后我们可以以自然的方式将定义扩展到它们的彩色版本。 特别地，$𝒢$、${𝒢}_k$、${𝒞}_k(G)$分别成为所有顶点（分别为）的集合。 边）彩色图，所有顶点的集合（分别是。 边）阶数最多为 $k$ 的彩色图，以及所有连接的顶点（分别为）的集合。 边）对 $G$ 阶数最多为 $k$ 的彩色诱导子图。请注意，${𝒢}_k$ 在彩色设置中变为无限，但在无色设置中变为有限，但这并不重要。 （乘法）图不变量和图多项式的定义以自然的方式扩展到顶点（分别为： 边）彩色图，特别是顶点的 BIGCP（分别是 边）彩色图的定义方式完全相同。 我们只需要注意，虽然 BIGCP 定义的第 (i) 部分中的总和在彩色版本中是无限的，但在评估彩色图 $G$ 的特定选择时，除了有限多项之外，所有项都将为零。现在定理 3.1 的彩色版本如下所示。

Theorem 3.7.

令 $C>0$ 和 $\mathrm{\Delta }\in \mathbb{N}$ 并令 $p(\cdot )$ 为顶点的有界诱导图计数多项式（分别为： 边）彩色图表。 然后有一个确定性的 ${(n/\epsilon )}^{O(1)}$ 时间算法，给定任何 $n$ 顶点（resp. 边）最大度最多为 $\mathrm{\Delta }$ 的彩色图 $G$ 和任意 $\epsilon >0$，计算 $m=C\ln (n/\epsilon )$ 的 $p(G)$ 的反幂和 $p_1,\mathrm{\dots },p_m(G)$ 。

4 独立多项式

4.1 有界度图上的独立多项式

定理证明1.1。

首先请注意 Shearer [42] 的结果，参见。 Scott 和 Sokal [41，推论 5.7]，我们知道 $Z(G)(z)\ne 0$ 对于所有最大度数最多 $\mathrm{\Delta }$ 的所有图 $G$以及所有满足$|z|\le {\lambda }^{\ast }=\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{\mathrm{\Delta }}^{\mathrm{\Delta }}}$的$z\in ℂ$。

现在修复最大度数至多$\mathrm{\Delta }$的$n$顶点图$G$。 设$m=C\ln (n/\epsilon )$，其中$C=C(\lambda ,{\lambda }^{\ast })$是推论2.3中的常数。 由于$Z(G)$的第$k$系数等于$\text{ind}({\bullet }^k,G)$，其中${\bullet }^k$表示由$k$组成的图孤立的顶点，并且由于 $Z(G)$ 显然是乘法并且常数项等于 $1$，因此我们有 $Z(G)$ 是一个 BIGCP（取 $\alpha =\beta =1$ ）。 因此，根据定理 3.1 我们可以看出，对于 $k=1,\mathrm{\dots },m$ 我们可以在 ${(n/\epsilon )}^{O(1)}$ 时间内计算 $Z(G)$ 的第一个 $m$ 逆幂和。 注意到 $Z(G)$ 的次数最多为 $n$，推论 2.3 意味着我们可以计算 $\epsilon$ 的乘法近似值 $Z(G)(\lambda )$ 及时 ${(n/\epsilon )}^{O(1)}$。 证明到此结束。 ∎

计算负值和复数值的独立多项式为我们提供了有关图中独立集分布的新信息，如以下示例所示。 我们用 $Z_e(G)(\lambda )$ 表示多项式，其定义方式与独立多项式相同，只是在和 (1) 中，我们只允许基数为偶数的独立集。

Theorem 4.1.

让 $\mathrm{\Delta }\in \mathbb{N}$ 并让 。 然后存在一种确定性算法，给定最大度数最多为 $\mathrm{\Delta }$ 和 $\epsilon >0$ 的图 $G=(V,E)$，计算乘法 $\epsilon$ -在时间${(|V|/\epsilon )}^{O(1)}$中近似于$Z_e(G)(\lambda )$。

证明。

我们应用定理1.1的算法来计算乘法$\epsilon$-近似值$A(\lambda )$和$A(-\lambda )$到$Z(G)(\lambda )$并且$Z(G)(-\lambda )$分别在时间${(|V|/\epsilon )}^{O(1)}$。 我们有

$$e^{-\epsilon }Z(G)(\lambda )\le A(\lambda )\le e^{\epsilon }Z(G)(\lambda )\text{and}{e}^{-\epsilon }Z(G)(-\lambda )\le A(-\lambda )\le e^{\epsilon }Z(G)(-\lambda ).$$

取这些方程总和的一半并注意 $Z_e(G)(\lambda )=\frac{1}{2}(Z(G)(\lambda )+Z_G(-\lambda ))$，我们发现 $\frac{1}{2}(A(\lambda )+A(-\lambda ))$ 是 $\epsilon$ 的乘法近似 $Z_e(G)(\lambda )$，前提是$Z(G)(\lambda )$和$Z(G)(-\lambda )$具有相同的符号。

显然 $Z(G)(\lambda )>0$ 因为 $Z(G)$ 的系数是非负实数。 另外$Z(G)(-\lambda )>0$因为我们根据Scott和Sokal[41]的结果知道$Z(G)$在区间$[-{\lambda }^{\ast },{\lambda }^{\ast }]$中不会消失，我们知道 $Z(G)$ 在区间 $[0,{\lambda }^{\ast }]$ 内为正，因为 $Z(G)$ 的所有系数都是非负实数。 因此，$Z(G)$ 在整个区间 $[-{\lambda }^{\ast },{\lambda }^{\ast }]$（特别是 $Z(G)(\lambda )>0$)上为正。 ∎

4.2 多元独立多项式

在这里，我们将简要提及我们的结果如何应用于多元独立多项式。 对于图表 $G=(V,E)$ 和每个 $v\in V$ 定义的变量 $z_v$

$$Z(G)({(z_v)}_{v\in V})=\sum _{\begin{array}{c}I\subseteq V\\ \text{independent}\end{array}}\prod _{v\in I}{z}_v.$$

修复我们希望评估多元独立多项式的 $z_v$、$v\in V$ 的复数值。 现在通过 $q(G)(\lambda )=Z(G)({(\lambda z_v)}_{v\in V})$ 定义单变量图多项式 $q(G)$，其中 $q(G)(1)$ 是我们希望估计的值。 $q(G)$ 中 ${\lambda }^k$ 的系数由大小为 $k$ 的所有独立 $G$ 集合的总和给出，其中独立集合$I$与权重${\prod }_{v\in I}{z}_v$一起计数。 虽然我们不能再将其表示为普通诱导子图计数的线性组合，但我们可以将其视为顶点颜色诱导子图计数的线性组合，正如我们现在将解释的那样。

我们将 $q$ 扩展到顶点颜色图，并用 $q_{vc}$ 表示此扩展。 将变量 $z_i$ 与每种颜色 $i=1,2,\mathrm{\dots }$ 关联。 多项式$q_{vc}$的${\lambda }^k$系数表示为${\sum }_H{\alpha }_H{\text{ind}}_{vc}(H,\cdot )$，其中总和在所有带有着色的顶点着色图$H=(V_H,E_H)$上$c:V_H\to \mathbb{N}$ 在 $k$ 顶点上，其中 ${\alpha }_H={\prod }_{u\in V_H}{z}_{c(u)}$ 如果 $H$ 是独立集，否则为零。 那么 $q_{vc}$ 是顶点颜色设置中的 BIGCP，参见。 3.3 小节。

现在假设 $G$ 有 $n$ 个标记为 $1,\mathrm{\dots },n$ 的顶点。 通过为 $i=1,\mathrm{\dots },n$ 指定标记为 $i$ 的顶点颜色 $i$，我们将 $G$ 视为顶点着色图。 然后$q_{vc}(G)=q(G)$。 因此，如果$G$有界度，我们可以通过定理3.7有效地计算$q(G)$的对数阶逆幂和，如上一节所示。

希勒的结果 [42]，参见斯科特和索卡尔的结果 [41，推论 5.7]，也适用于多元独立多项式（即当 对于所有 $v\in V$ 和 $\mathrm{\Delta }(G)\le \mathrm{\Delta }$ 时，$Z(G)({(z_v)}_{v\in V})$ 非零）。 这意味着只要对于某些$M>1$,$q(G)(\lambda )$就非零。 由此可知，如果 $G$ 的最大度最多为 $\mathrm{\Delta }$，并且所有 $z_v$ 都满足 ，那么我们就能有效地近似 $q(G)(1)$，进而近似 $Z(G)({(z_v)}_{v\in V})$。

4.3 无爪图上的独立多项式

在本小节中，我们将说明 Barvinok 的一种技术，通过进行仔细的多项式变换来逼近复平面较大区域上的图多项式。 我们使用这种技术来证明定理1.2，该定理表明我们可以在几乎整个复平面上逼近无爪图的独立多项式。 首先我们需要一些初步知识结果。

Proposition 4.2.

如果 $G$ 是最大阶数为 $\mathrm{\Delta }$ 的无爪图，且 $\zeta$ 是 $G$ 的独立多项式 $Z(G)$ 的根，则 $\zeta \in ℝ$ 与 .

证明。

$\zeta \in ℝ$ 是 Chudnovsky 和 ​​Seymour [17] 的结果。 $\zeta$ 必须为负，因为 $Z(G)$ 的所有系数都是正的。 现在 Shearer [42] 的结果表明

$$|\zeta |\ge {\lambda }^{\ast }(\mathrm{\Delta })=\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{\mathrm{\Delta }}^{\mathrm{\Delta }}}>\frac{1}{e(\mathrm{\Delta }-1)},$$

由此得出命题。 ∎

我们还需要以下 Barvinok [5] 引理。

Lemma 4.3。

对于 $\rho \in (0,1)$ 我们定义

$\alpha =\alpha (\rho )=1-\exp (-{\rho }^{-1}),$ $\beta =\beta (\rho )={\displaystyle \frac{1-\exp (-1-{\rho }^{-1})}{1-\exp (-{\rho }^{-1})}}>1,$

$N=N(\rho )=\lfloor (1+{\rho }^{-1})\exp (1+{\rho }^{-1})\rfloor ,$ $\sigma =\sigma (\rho )={\displaystyle \sum _{i=1}^N}{\displaystyle \frac{{\alpha }^i}{i}}.$

多项式

$$\varphi (z)={\varphi }_{\rho }(z)=\frac{1}{\sigma }\sum _{i=1}^N\frac{{(\alpha z)}^i}{i}$$

具有以下属性：

• $\varphi (0)=0$和$\varphi (1)=1$和$\varphi$有度$N$;

• 如果 $z\in ℂ$ 与 $|z|\le \beta$ 则 ${\varphi }_{\rho }(z)\in S_{\rho }$，其中

  $$S_{\rho }:=\{z\in ℂ\mid -\rho \le \mathrm{\Re }(z)\le 1+2\rho \text{and}-2\rho \le \mathrm{\Im }(z)\le 2\rho \}.$$

Proposition 4.4.

将 $\lambda =r{e}^{i\theta }\in ℂ$ 修复为 $\theta \in (-\pi ,\pi )$。 令 $S_{\rho }$ 与前面的引理相同，并令 ${ℝ}^{-}$ 表示负实数线。 然后

证明。

$S_{\rho }$ 是复平面中与实轴平行的有界条带，因此 $\lambda S_{\rho }$ 是将同一条带放大 $r$ 倍并旋转 $\theta$ 角。 这个命题是从初等三角学得出的。 ∎

定理证明1.2。

回想一下，我们得到了一个最大度为 $\mathrm{\Delta }$ 和 $\lambda \in ℂ$ 的无爪图 $G$，它不是负实数，我们希望找到一个乘法 $\epsilon$-近似于$Z(G)(\lambda )$。

设置$n:=|V(G)|$并让$\lambda =r{e}^{i\theta }$与$\theta \in (-\pi ,\pi )$。 放

并考虑多项式$g(z)=Z(G)(\lambda {\varphi }_{\rho }(z))$。 请注意，$g$ 的度数是 $O(n)$，因为 $Z(G)$ 的度数最多是 $n$，而 ${\varphi }_{\rho }$ 的度数是常数 $N(\rho )$。

我们将使用推论 2.3 来查找时间 ${(n/\epsilon )}^{O(1)}$ 中 $g(1)=Z(G)(\lambda )$ 的乘法 $\epsilon$ 近似值。 为了应用推论2.3得出这个结论，只需检查（i）$g$在磁盘$|z|\le \beta :=\beta (\rho )$中没有根并且（ ii) 可以在${(n/\epsilon )}^{O(1)}$时间内计算出$g$的前$m=C\ln (d/\epsilon )$次幂和，其中$d=O(n)$是$g$和$C=C(\beta ,1)$是推论2.3

仍有待检查 (i) 和 (ii)。 要看到 (i)，首先请注意，根据引理 4.3,${\varphi }_{\rho }$ 将磁盘 $D=\{z\in ℂ\mid |z|\le \beta \}$ 映射到 $S_{\rho }$。 根据命题4.4和我们对$\rho$的选择，我们有$\lambda {\varphi }_{\rho }(D)\cap {ℝ}^{-}\subseteq (-\frac{1}{3(\mathrm{\Delta }-1)},0]$。 根据命题4.2我们知道如果$Z(G)(\zeta )=0$则$\zeta \in ℝ$和。 特别是，这意味着 $g(\cdot )=Z(G)(\lambda {\varphi }_{\rho }(\cdot ))$ 在磁盘 $D$ 中没有根。

对于 (ii)，我们证明我们可以在时间 ${(n/\epsilon )}^{O(1)}$ 内计算 $g$ 的第一个 $m$ 系数，这根据命题 2.1 给定一个多项式$p(z)={\sum }_{i=0}^d{a}_i{z}^i$，写成$p_{[m]}(z):={\sum }_{i=0}^m{a}_i{z}^i$。 然后我们注意到 $g_{[m]}={(Z(G)\circ (\lambda \varphi ))}_{[m]}={(Z{(G)}_{[m]}\circ (\lambda {\varphi }_{[m]}))}_{[m]}$，其中我们关键地使用了以下事实：$\varphi$ 自 $\varphi (0)=0$ 以来没有常数项。 换句话说，为了获得 $g_{[m]}(z)$，我们将 $\lambda {\varphi }_{[m]}(z)$ 替换为 $Z{(G)}_{[m]}(z)$ 并保留前 $m$ 项。 因此，如果我们知道 $Z(G)$ 的第一个 $m$ 系数，我们就可以在 $O(m^3)$ 时间内得到 $g$ 的第一个 $m$ 系数。 由于$Z(G)$是一个BIGCP，我们可以在${(n/\epsilon )}^{O(1)}$时间内计算它的第一个$m$个逆幂和（如定理1.1的证明） >)，由此我们可以根据命题2.1找到其在时间$O(m^2)$上的第一个$m$系数。 至此证明完毕。 ∎

我们注意到，对于上述算法中的${(n/\epsilon )}^{O(1)}$运行时间，指数中的$O(1)$取决于$\lambda$，并且在$r=|\lambda |$ 然而，通过采用 Barvinok [6] 所描述的引理 4.3，可以将这种依赖性降低到 $O({|\lambda |}^{1/2})$。

5 Tutte 多项式

这里给出定理1.3的证明。

定理证明1.3。

根据 Jackson、Procacci 和 Sokal 的一个结果，参见 [31,定理 1.2]（该结果对无环多图有效），我们知道存在一个常数 $K>0$，该常数取决于 $\mathrm{\Delta }$ 和 $w$，从而对于所有具有 $|q|>K$ 的 $q$ 图 ，对于最大度最多为 $\mathrm{\Delta }$ 的所有图 $G$，都有 $Z_T(G)(q,w)\ne 0$。 这与我们需要应用推论 2.3 完全相反，因此让我们定义图形多项式 $p_T$

$$p_T(G)(z):=z^{|V|}{Z}_T(G)(1/z,w),$$ (17)

对于任何图$G=(V,E)$。 请注意，$p_T(G)$ 的度数为 $n:=|V|$，并且如果 $x$ 是 的乘法 $\epsilon$ 近似值 $p_T(G)(1/q,w)$，则$q^{n}x$ 是 $Z_T(G)(q,w)$ 的乘法 $\epsilon$ 近似值，因此找到前者就足够了。

我们将证明，对于任何最大度数至多$\mathrm{\Delta }$的$n$-顶点图$G$，我们可以计算第一个$m$逆幂$p_T(G)$ 在时间 ${(n/\epsilon )}^{O(1)}$ 中的总和，其中 $m=C\ln (n/\epsilon )$ 和 $C=C(1/q,1/K)$ 是推论 2.3 中的常数。 因此，推论 2.3 意味着我们可以计算出 $\epsilon$ 的乘法 $p_T(G)(1/q)$ 近似值，从而在 ${(n/\epsilon )}^{O(1)}$ 时间内计算出 $Z_T(G)(q,w)$ 近似值。

我们将证明 $p_T(G)$ 是一个 BIGCP，因此根据定理 3.1 我们可以得出结论：我们可以在 ${(n/\epsilon )}^{O(1)}$ 时间内计算第一个 $m$ 逆幂和。

由于 Tutte 多项式 $Z_T(G)(z,w)$（作为 $z$ 中的多项式）是一个单调乘性图多项式（次数 $n=|V(G)|$)，我们知道常数项$p_T$ 等于 $1$ 并且 $p_T$ 是乘法。 因此，只需在定义3.1中显示条件（i）和（ii）即可。 $p_T(G)$ 中 $z^k$ 的系数等于 $Z_T(G)(z,w)$ 中 $z^{n-k}$ 的系数，并且根据定义等于 $E$ 的所有子集 $A$ 的总和，这样 $A$ 恰好诱导出一个具有 $n-k$ 分量的图，其中每个子集都以权重 $w^{|A|}$ 计算。 如果图的一个组件由多个顶点组成，我们将其称为非平凡。 假设边 $A\subseteq E$ 的某个子集产生 $n-k$ 分量，其中 $c$ 是重要的。 然后我们有 $n-k-c$ 个孤立的顶点，因此由这些重要组件的并集组成的图 $F$ 具有 $n-(n-k-c)=k+c$ 个顶点和 $k(F)=c$成分。 因此，我们可以在 $E$ 的子集 $A$ 和 $G$ 的子图 $F$ 之间找到对应关系，前者诱导出一个完全由 $n-k$ 组成的图，而后者则没有满足 $k(F)=V(F)-k$ 的孤立顶点。 因此，将子图$F$的最小度写为$\delta (F)$，则$Z_T(G)$中$z^{n-k}$的系数可表示为

$$\sum _{\begin{array}{c}F\subseteq G:\delta (F)\ge 1\\ |k(F)|=|V(F)|-k\end{array}}{w}^{|E(F)|}=\sum _H\sum _{\begin{array}{c}F\subseteq H:\delta (F)\ge 1\\ V(F)=V(H)\\ |k(F)|=|V(F)|-k\end{array}}{w}^{|E(F)|}\text{ind}(H,G).$$ (18)

事实上，第一个总和可以在最多具有 $2k$ 个顶点的图 $H$ 上进行。 这是因为 $V(H)=V(F)$ 和

$$|V(F)|=k(F)+k\le \frac{V(F)|}{2}+k.$$

因为 $F$ 没有孤立的顶点。

从(18)开始，我们可以通过检查时间$O(2^{E(H)})=O(2^{\mathrm{\Delta }|V(H)|})$内$E(H)$的所有子集来计算$\text{ind}(H,G)$的系数。 这意味着 $p_T$ 是一个 BIGCP（采用 $\alpha =2$ 和 $\beta =2^{\mathrm{\Delta }}$)。 ∎

Remark 5.1.

Csikvári 和 Frenkel [18] 引入了有界指数型图多项式，并证明这些多项式在有界度图上有有界根。 这在[40]中被用来给出用于评估这些多项式的拟多项式时间近似算法。 第二个参数固定的 Tutte 多项式就是此类多项式的一个示例。 我们在这里指出，上面给出的 Tutte 多项式的证明也很容易扩展到有界指数类型的图多项式。 因此[40]中的算法可以适应在有界度图上以多项式时间运行。

6 自旋模型的配分函数

在本节中，我们将陈述并证明定理1.4的推广，并将说明我们的方法如何应用于具有多重性的图同态的配分函数。

6.1 边缘彩色图的划分函数

令 $G=(V,E)$ 为图表。 还假设对于每个 $e\in E$ 我们有一个对称的 $k\times k$ 矩阵 $A^e$。 让我们写$𝒜={(A^e)}_{e\in E}$。 然后我们可以将自旋模型的配分函数的定义扩展如下：

$$p(G)(𝒜)=\sum _{\varphi :V\to [k]}\prod _{e=\{u,v\}\in E}{A}_{\varphi (u),\varphi (v)}^e.$$ (19)

我们将$p(G)(𝒜)$称为$𝒜$的配分函数。 在[24]中，这称为马尔可夫随机场（如果$A^e$非负），在[36]中，这称为多自旋系统。 显然，如果所有 $A^e$ 都相同，则这只是简化为自旋模型的配分函数。 我们得到以下结果，这暗示了定理1.4。

Theorem 6.1.

让$\mathrm{\Delta },k\in \mathbb{N}$。 那么存在一种确定性算法，该算法给定一个最大度最多为 $\mathrm{\Delta }$ 的图 $G=(V,E)$、对称矩阵 $k\times k$ $A^e$、$e\in E$、以便对所有 $i,j=1,\mathrm{\dots },k$ 和 $e\in E$ 以及 $\epsilon >0$ 都适用 $|A_{i,j}^e-1|\le 0.34/\mathrm{\Delta }$，在 ${(|V|/\epsilon )}^{O(1)}$ 时间内计算出 与 $p(G)(𝒜)$ 的乘法 $\epsilon$ 近似值。

Remark 6.1.

如果$\mathrm{\Delta }\ge 3$常量$0.34$可以被$0.45$替代，如果$\mathrm{\Delta }$足够大则可以被$0.54$替代；参见[8]。

证明。

令 $J$ 为全 1 矩阵。 对于 $z\in ℂ$，令 $B^e(z):=J+z(A^e-J)$ 并令 ${𝒜}^{\prime }(z):={(B^e(z))}_{e\in E}$。 定义单变量多项式 $q$ 通过

$$q(G)(z)=k^{-|V|}p(G)({𝒜}^{\prime }(z)).$$ (20)

然后是$q(G)(0)=1$和$q(G)(1)=k^{-|V|}p(G)(𝒜)$。 Barvinok 和 Soberón [8, Theorem 1.6]证明，存在一个常数 $\delta >0$，使得所有 $z$ 满足 $|z|\le 1+\delta$ 时，都存在 $q(G)(z)\ne 0$ 。

我们将证明，对于任何最大度数至多$\mathrm{\Delta }$的$n$-顶点图$G$，我们可以计算第一个$m$逆幂$q(G)$ 在时间 ${(n/\epsilon )}^{O(1)}$ 中的总和，其中 $m=C\ln (n/\epsilon )$ 和 $C=C(1,1+\delta )$ 是推论 2.3 中的常数。 注意到 $q(G)$ 的度数最多为 $|E|\le n\mathrm{\Delta }/2$，推论 2.3 意味着我们可以在 ${(n/\epsilon )}^{O(1)}$ 的时间内计算出 $\epsilon$ 的乘法 $q(G)(1)$ 近似值。 因此，剩下的就是证明我们可以计算 $q(G)$ 在时间 ${(n/\epsilon )}^{O(1)}$ 中的第一个 $m$ 逆幂和。

我们将证明我们可以将 $q$ 解释为边缘颜色的 BIGCP，参见。 3.3 小节。 假设 $G$ 有 $\mathrm{\ell }$ 边，标记为 $1,\mathrm{\dots },\mathrm{\ell }$。 使用颜色 $i$ 为 $i=1,\mathrm{\dots },\mathrm{\ell }$ 标记为 $i$ 的边缘着色。 根据定义，$q(G)(z)$ 满足

$q(G)(z)$ $=k^{-n}{\displaystyle \sum _{\varphi :V\to [k]}}{\displaystyle \prod _{e=\{u,v\}\in E}}{(J+(z(A^e-J)))}_{\varphi (u),\varphi (v)}$

$=k^{-n}{\displaystyle \sum _{i=0}^{|E|}}{z}^i\left({\displaystyle \sum _{\begin{array}{c}F\subseteq E\\ |F|=i\end{array}}}{\displaystyle \sum _{\varphi :V\to [k]}}{\displaystyle \prod _{e=\{u,v\}\in F}}{(A^e-J)}_{\varphi (u),\varphi (v)}\right).$ (21)

对于$E$的子集$F$，将$G[F]$定义为由$F$中的边引起的边着色图。 $G[F]$ 的顶点集由与 $F$ 中的边重合的那些顶点组成，因此其大小最多为 $2|F|$。 那么我们看到(21)中$z^i$的系数可以写成如下：

$k^{-n}$ ${\displaystyle \sum _{\begin{array}{c}H\in {𝒢}_{2i}\\ |E(H)|=i\end{array}}}{k}^{n-|V(H)|}\left({\displaystyle \sum _{\varphi :V(H)\to [k]}}{\displaystyle \prod _{e=\{u,v\}\in E(H)}}{(A^e-J)}_{\varphi (u),\varphi (v)}\right){\text{ind}}_{ec}(H,G)$

$=$ ${\displaystyle \sum _{\begin{array}{c}H\in {𝒢}_{2i}\\ |E(H)|=i\end{array}}}\left(k^{-|V(H)|}{\displaystyle \sum _{\varphi :V(H)\to [k]}}{\displaystyle \prod _{e=\{u,v\}\in E(H)}}{(A^e-J)}_{\varphi (u),\varphi (v)}\right){\text{ind}}_{ec}(H,G),$ (22)

我们将 ${𝒢}_{2i}$ 解释为最多 $2i$ 个顶点上的边缘颜色图的集合。 这展示了如何将 $q$ 扩展到边缘彩色图。 (22) 中的内部总和可以在 $O(k^{|V(H)|})$ 时间内计算出来，显然 $q$ 的常数项等于 $1$ 并且它是乘法的。 这意味着 $q$ 到边缘彩色图的扩展是 BIGCP（具有常数 $\alpha =2$ 和 $\beta =k$)，因此定理 3.7 意味着我们可以在 $O{(n/\epsilon )}^{O(1)}$ 范围内计算 $q$ 的第一个 $m$ 逆幂和。 至此证明完毕。 ∎

6.2 具有重数的图同态的配分函数

令 $G=(V,E)$ 为图表。 假设对于每个 $e\in E$ 我们有一个对称的 $k\times k$ 矩阵 $A^e$。 让我们写$𝒜={(A^e)}_{e\in E}$。 让 $n=|V|$ 并让 $\mu =({\mu }_1,\mathrm{\dots },{\mu }_k)$ 和 ${\mu }_i\in {\mathbb{Z}}_{\ge 1}$ 对于每个 $i$ 使得 ${\sum }_{i=1}^k{\mu }_i=n$ 。 我们将这样的$\mu$称为$k$部分中的$n$的组合。 Barvinok 和 Soberón [9] 将具有重数 $\mu$ 的图同态的配分函数定义为

$$p_{\mu }(G)(𝒜)=\sum _{\begin{array}{c}\varphi :V\to [k]\\ |{\varphi }^{-1}(i)|={\mu }_i\end{array}}\prod _{e=\{u,v\}\in E}{A}_{\varphi (u),\varphi (v)}^e.$$ (23)

有关此类配分函数的更多详细信息和背景，请参阅[9]。

基于 Barvinok 和 Soberón [9，第 2 部分] 的结果，并使用与上面完全相同的证明，我们直接建立以下结论：

Theorem 6.2.

让$\mathrm{\Delta },k\in \mathbb{N}$。 那么就存在一种确定性算法，它可以在给定最大度最多为 $\mathrm{\Delta }$ 的图 $G=(V,E)$ 的情况下，在 $k$ 部分中生成 $|V|$ 的组合 $\mu$、对称矩阵 $k\times k$、$A^e$、$e\in E$（使得 $|A_{i,j}^e-1|\le 0.1/\mathrm{\Delta }$ 适用于所有 $i,j=1,\mathrm{\dots },k$ 和 $e\in E$ 以及 $\epsilon >0$），在 ${(|V|/\epsilon )}^{O(1)}$ 时间内计算出 $\epsilon$ 与 $p_{\mu }(G)(𝒜)$ 的近似值。

7 边缘着色模型的配分函数

在本节中，我们陈述并证明定理1.5的推广。 它与上一节中定理1.4的推广是一致的。 证明也遵循同样的思路，但正如我们将在下面看到的，有一些细节不同。

7.1 顶点颜​​色图的划分函数

令 $G=(V,E)$ 为图表。 假设我们为每个 $v\in V$ 都有 $k$-颜色边缘着色模型 $h^v$。 让我们写$\mathscr{H}={(h^v)}_{v\in V}$。 通常，$(G,\mathscr{H})$ 对称为签名网格，参见[15,16,14]。 然后我们可以将边缘着色模型的配分函数的定义扩展如下：

$$p(G)(\mathscr{H})=\sum _{\varphi :E\to [k]}\prod _{v\in V}{h}^v(\varphi (\delta (v))).$$ (24)

我们将$p(G)(\mathscr{H})$称为$\mathscr{H}$的划分函数。 显然，如果所有 $h^v$ 相等，我们就获得了边缘着色模型的普通配分函数。 它也被称为签名网格$(G,\mathscr{H})$的Holant问题 cf. [15,16,14]。 我们得到以下结果，这暗示了定理1.5。

Theorem 7.1.

让$\mathrm{\Delta },k\in \mathbb{N}$。 那么就存在一种确定性算法，在给定最大度最多为 $\mathrm{\Delta }$ 的图 $G=(V,E)$、$k$-彩色边着色模型 $h^v$、$v\in V$、满足 $|h^v(\varphi )-1|\le 0.35/(\mathrm{\Delta }+1)$ 的所有 $\varphi \in {\mathbb{N}}^k$ 和 $v\in V$ 以及 $\epsilon >0$，在 ${(|V|/\epsilon )}^{O(1)}$ 时间内计算出与 $p(G)(\mathscr{H})$ 的乘法 $\epsilon$ 近似值。

Remark 7.1.

如果$\mathrm{\Delta }\ge 3$常量$0.35$可以被$0.47$替代，如果$\mathrm{\Delta }$足够大则可以被$0.56$替代；请参阅[40]。 此外，对于熟悉这些配分函数的正交群不变性的读者，可以使用[40]中的推论6b来找到一个更大的边缘着色模型族，可以有效地近似配分函数。

证明。

让 $J$ 表示常量函数 $J:{\mathbb{N}}^k\to ℂ$（对于所有 $\varphi \in {\mathbb{N}}^k$ 由 $J(\varphi )=1$ 定义）。 设 $z\in ℂ$、$g^v(z):=J+z(h^v-J)$ 和 $\mathscr{H}(z):={(g^v(z))}_{v\in V}$。 考虑以下单变量多项式：

$$q(G)(z):=k^{-|E|}p(G)(\mathscr{H}(z)).$$ (25)

观察 $q(G)(1)=k^{-|E|}p(G)(\mathscr{H})$ 和 $q(G)$ 是次数最多为 $n:=|V|$ 的多项式。 因此，正如上一节中一样，近似配分函数 $p(G)(\mathscr{H})$ 的问题被近似单变量多项式的评估所取代。

根据 [40] 的推论 6a（对于多重图有效），存在 $\delta >0$，使得每当 $|z|\le 1+\delta$ 时 $q(G)(z)\ne 0$ 。 我们将证明（在定理 7.2 中）对于任何最大度数最多为 $\mathrm{\Delta }$ 的 $n$ 顶点图 $G$，我们可以计算 ${(n/\epsilon )}^{O(1)}$ 时间内 $q(G)$ 的第一个 $m$ 逆幂和，其中 $m=C\ln (n/\epsilon )$ 和 $C=C(1,1+\delta )$ 是常数推论2.3 注意到 $q(G)$ 的度数最多为 $n$，推论 2.3 意味着我们可以在 ${(n/\epsilon )}^{O(1)}$ 的时间内计算出 $\epsilon$ 的乘法 $q(G)(1)$ 近似值。

理想情况下，我们希望使用定理 3.1 来完成此操作，就像定理 6.1 的证明一样。 由于边缘着色模型的配分函数是乘性的，因此多项式$q$也是乘性的，并且其常数项等于$1$。 因此，为了能够应用定理 3.1，我们只需检查 $q$ 的系数是否可以表示为（彩色）诱导图计数的线性组合。 事实上，如果所有 $h^v$ 都相等，[40] 中已经证明了这一点，但不清楚 (11) 中的系数 ${\lambda }_{H,i}$ 是否可以高效计算。 因此，我们不必直接应用定理 3.1，而是需要做更多的工作，我们将其推迟到下一节。 ∎

7.2 计算$q(G)(z)$

根据定义，

$q(G)(z)$ $=k^{-|E|}{\displaystyle \sum _{\varphi :E\to [k]}}{\displaystyle \prod _{v\in V}}(J+z(h^v-J))(\varphi (\delta (v)))$

$=k^{-|E|}{\displaystyle \sum _{i=0}^n}{z}^i\left({\displaystyle \sum _{\begin{array}{c}U\subseteq V\\ |U|=i\end{array}}}{\displaystyle \sum _{\varphi :E\to [k]}}{\displaystyle \prod _{u\in U}}(h^u-J)(\varphi (\delta (u)))\right)$

$=k^{-|E|}{\displaystyle \sum _{i=0}^n}{z}^i\left({\displaystyle \sum _{\begin{array}{c}U\subseteq V\\ |U|=i\end{array}}}{k}^{|E\setminus E(U)|}{\displaystyle \sum _{\varphi :E(U)\to [k]}}{\displaystyle \prod _{u\in U}}(h^u-J)(\varphi (\delta (u)))\right),$ (26)

其中对于 $U\subseteq V$,$E(U)$ 表示 $G$ 的一组边，这些边与 $U$ 的至少一个顶点重合。

(26)第三行括号内的第二个和几乎是${(h^u-J)}_{u\in U}$的配分函数，只不过$(U,E(U))$对实际上可能不是图形，因为 $E(U)$ 的某些边没有被 $U$ 跨越。 我们将这种类似图形的结构称为片段，并且$E(U)$中的边缘“伸出”（即不被$U$跨越）作为半边。 形式上，片段是一对$(H,\kappa )$，其中$H$是顶点颜色图，$\kappa$是地图$\kappa :V(H)\to \{0,1,\mathrm{\dots },\mathrm{\Delta }\}$，记录与每个顶点关联的半边的数量。 假设 $G$ 有 $n$ 个顶点，标记为 $1,\mathrm{\dots },n$。 从现在开始，我们将把图 $G$ 视为顶点着色图，其中顶点 $i$ 为 $i=1,\mathrm{\dots },n$ 获取颜色 $i$。 对于 $U\subseteq V$，我们让 $G(U)$ 为片段 $(G[U],\kappa )$，其中 $\kappa (u)$ 等于连接 $u$ 的边数> 与 $V\setminus U$。 请注意，通过将所有 $v\in V(G)$ 的映射 $\kappa :V(G)\to \{0,\mathrm{\dots },\mathrm{\Delta }\}$ 视为 $\kappa (v)=0$，图 $G$ 本身可以被视为片段。

显然，对于大小为 $i$ 的每个 $U$，(26) 第三行的第二个和内的表达式仅取决于片段的同构类$G(U)$。 （从片段$(H,\kappa )$到片段$(H^{\prime },{\kappa }^{\prime })$的同构是底层顶点颜色图的同构$\alpha$，并且这样对于每个 $u\in V(H)$、$\kappa (u)={\kappa }^{\prime }(\alpha (u))$。） 对于片段 $F=(H,\kappa )$，让 $E(F)$ 表示 $F$ 的边集（包括半边），让 $V(F)$ 表示底层的顶点集图$H$。假设对于每个$i=1,2,\mathrm{\dots }$我们有一个$k$-color边缘着色-模型$h^i$并让$\mathscr{H}={(h^i)}_{i\ge 1}$然后定义，

$$p(F)(\mathscr{H}):=\sum _{\varphi :E(F)\to [k]}\prod _{v\in V(F)}{h}^v(\varphi (\delta (v))).$$ (27)

这里我们隐式地用顶点本身来标识 $H$ 顶点的颜色。 定义片段$F=(H,\kappa )$,${\text{ind}}^{\ast }(F,G)$为大小为$|V(F)|$的集合$U$的数量，使得$G(U)$与 $F$ 同构。写$\mathscr{H}-J={(h^i-J)}_{i\ge 1}$，我​​们可以将(26)重写为

$q(G)(z)$ $=k^{-|E|}{\displaystyle \sum _{i=0}^n}{z}^i\left({\displaystyle \sum _{\begin{array}{c}F=(H,\kappa )\\ |V(H)|=i\end{array}}}{k}^{|E|-|E(F)|}p(F)(\mathscr{H}-J){\text{ind}}^{\ast }(F,G)\right)$

$={\displaystyle \sum _{i=0}^n}{z}^i\left({\displaystyle \sum _{\begin{array}{c}F=(H,\kappa )\\ |V(H)|=i\end{array}}}{k}^{-|E(F)|}p(F)(\mathscr{H}-J){\text{ind}}^{\ast }(F,G)\right),$ (28)

其中总和运行在片段上。 这展示了如何将 $q$ 扩展到顶点颜色图。 让我们用$e_i$表示(28)中$z^i$的系数。 [40] 中证明，在所有 $h^i$ 都相等的情况下，${\text{ind}}^{\ast }(F,G)$ 可以表示为某些图形 $H$ 的参数 $\text{ind}(H,G)$ 的线性组合。如上所述，这个表达式中的系数可能不容易计算（至少我们不知道如何计算）。 因此我们必须使用参数 ${\text{ind}}^{\ast }(F,\cdot )$ 来代替。 这不是一个严重的问题，因为本质上如果我们用 ${\text{ind}}^{\ast }$ 替换 (11) 中的 ind，则定理 3.1仍然有效。 事实上，我们有以下定理。

Theorem 7.2.

让 $C>0$ 和 $\mathrm{\Delta }\in \mathbb{N}$。 然后有一个确定性的${(n/\epsilon )}^{O(1)}$-时间算法，给定任何$n$-顶点图$G$，其最大度数最多为$\mathrm{\Delta }$并且任何$\epsilon >0$，计算$m=C\ln (n/\epsilon )$的$q(G)$的逆幂和$p_1,\mathrm{\dots },p_m$。

定理7.2的证明与定理3.1的证明遵循相同的思路。 本质上，我们需要用证明中的片段替换图表，并检查所有内容是否仍然有效。 为了完整起见，我们将给出证明。

我们首先需要注意的是，对于片段 $F_1=(H_1,{\kappa }_1)$，图参数 ${\text{ind}}^{\ast }(F_1,\cdot )$ 可以如下扩展为所有片段的集合：对于片段 $F_2=(H_2,{\kappa }_2)$，我们让 ${\text{ind}}^{\ast }(F_1,F_2)$ 表示集合 $S\subseteq V(H_2)$ 的数量，这样 $H_1$ 与 $H_2[S]$ 作为顶点着色图是同构的，并且对于 $H_1$ 的每个顶点 $v$，我们有 $v$ 在 $V(H_2)\setminus S$ 中的邻居数量等于 ${\kappa }_1(v)-{\kappa }_2(v)$。 然后对于两个片段 $F_1$ 和 $F_2$ 我们有

$${\text{ind}}^{\ast }(F_1,\cdot )\cdot {\text{ind}}^{\ast }(F_2,\cdot )=\sum _F{c}_{F_1,F_2}^F{\text{ind}}^{\ast }(F,\cdot ),$$ (29)

其中，和遍及所有片段 $F$，而对于一个片段 $F$，$c_{F_1,F_2}^F$ 表示 $V(F)$ 的子集 $(S,T)$ 中使 $S\cup T=V(F)$ 和 $F_1=F(S)$ 和 $F_2=F(T)$ 成对的个数。 （这里$F(S)$是由$S$引发的片段，即，如果$F=(H,\kappa )$，那么$F(S)=(H[S],\alpha )$，其中对于$s\in S$我们设置$\alpha (s)={\mathrm{deg}}_H(s)-{\mathrm{deg}}_{H[S]}(s)+\kappa (s)$。） 如果图$H$是连接的，我们称片段$F=(H,\kappa )$已连接。 我们现在调整 3 部分中结果的一些陈述和证明以包含片段。

我们从一些定义开始。 通过 $ℱ$ 我们表示所有片段的集合，通过 ${ℱ}_k$ 对于 $k\in \mathbb{N}$ 我们表示最多具有 $k$ 个顶点的片段的集合。 对于两个片段 $F_1=(H_1,{\kappa }_1)$ 和 $F_2=(H_2,{\kappa }_2)$、$F_1\cup F_2:=(H,\kappa )$，其中 $H=H_1\cup H_2$ 和 $\kappa :V(H_1\cup V(H_2)\to \{0,1,\mathrm{\dots },\mathrm{\Delta }\}$ 是映射，其限制为 $V(H_1)$是${\kappa }_1$，其对$V(H_2)$的限制是${\kappa }_2$。 片段不变量是某个集合$S$的函数$f:ℱ\to S$，它在同构片段上采用相同的值。 如果所有片段 $F_1,F_2$ 的 $f(\mathrm{\varnothing })=1$ 和 $f(F_1\cup F_2)=f(F_1)f(F_2)$ 则调用片段 $f$ multiplicative 的不变量。 片段$F=(H,\kappa )$的最大度等于$\mathrm{deg}(v)+\kappa (v)$超过$v\in V(G)$的最大值。

Lemma 7.3。

令 $F=(H,\kappa )$ 为 $k$ 顶点上的连接片段，并令 $\mathrm{\Delta }\in \mathbb{N}$ 。 然后是一个$O(k^2{n}^2{\mathrm{\Delta }}^{2(k-1)})$-时间算法，给定任何$n$-顶点片段$\widehat{F}$，其最大度数最多为$\mathrm{\Delta }$，计算数字${\text{ind}}^{\ast }(F,\widehat{F})$。

请注意，引理 7.3 使我们能够在 $|V(F)|=|V(\widehat{F})|$ 时测试有界度片段之间的片段同构。

证明。

这直接从引理 3.2 的证明得出。 我们将引理 3.2 的证明应用于底层图，然后删除任何违反顶点着色约束或 $\kappa$ 施加的约束的潜在嵌入。 ∎

如果对于每个 $F_1,F_2\in ℱ$ 我们有 $f(F_1\cup F_2)=f(F_1)+f(F_2)$，我们称片段 $f:ℱ\to ℂ$ additive 为不变量。 由 Csikvári 和 Frenkel [18] 引理的以下变体具有与引理 3.5 完全相同的证明；只需要在证明中的各处用片段替换图即可。

Lemma 7.4.

令 $f:ℱ\to ℂ$ 为 $f(\cdot ):={\sum }_{F\in ℱ}{a}_F{\text{ind}}^{\ast }(F,\cdot )$ 给出的片段的不变量。 那么 $f$ 是可加的，当且仅当 $a_F=0$ 对于所有断开连接的片段 $F$ 而言。

现在我们概述定理7.2的证明。

7.2.1 定理证明7.2

令 ${\zeta }_1,\mathrm{\dots },{\zeta }_d\in ℂ$ 为多项式 $q(G)$ 的根，并回想一下，对于 $\mathrm{\ell }\in \mathbb{N}$,$p_{\mathrm{\ell }}$ 是第 $\mathrm{\ell }$ ${\zeta }_i$ 的逆幂和。 这里$d$表示$q(G)={\sum }_{i=0}^d{e}_i{z}^i$的次数，最多为$n$。由(28)可知，对于$i\ge 1$,$e_i$可以表示为最多具有$\mathrm{\ell }$的片段的诱导片段数的线性组合> 顶点。 从 $e_1=-p_1$ 开始，这意味着 $p_1$ 也是如此。 通过归纳，(29) 和 (13)（使用 $e_0=1$)我们得到每个 $\mathrm{\ell }$

$$p_{\mathrm{\ell }}=\sum _{F\in {ℱ}_{\mathrm{\ell }}}{a}_{F,\mathrm{\ell }}{\text{ind}}^{\ast }(F,G),$$ (30)

对于某些但未知的系数$a_{F,\mathrm{\ell }}$。

由于 $q$ 是乘法，因此逆幂和是加法。 因此，引理 7.4 意味着如果 $F$ 未连接，则 $a_{F,\mathrm{\ell }}=0$ 。 表示为 $$𝒞′ℓ​(G) 连接片段$F$的集合，其顺序最多为$\mathrm{\ell }$，使得${\text{ind}}^{\ast }(F,G)\ne 0$。 这样我们就可以重写(30)如下：

$$p_{\mathrm{\ell }}=\sum _{F\in 𝒞_{}^{\prime }{}_{\mathrm{\ell }}{}^{}(G)}{a}_{F,\mathrm{\ell }}{\text{ind}}^{\ast }(F,G).$$ (31)

下一个引理表明我们可以有效地计算 $\mathrm{\ell }=1,\mathrm{\dots },m$ 的系数 $a_{F,\mathrm{\ell }}$，其中 $m=C\ln (n/\epsilon )$。

Lemma 7.5。

有一个 $O{(n/\epsilon )}^{O(1)}$ 时间算法，给定 $n$ 顶点图 $G$ 和 $\epsilon >0$，计算并列出系数 $a_{F,\mathrm{\ell }}$ 在 (31) 中为所有 $$Fε𝒞′ℓ​(G) 以及所有$\mathrm{\ell }=1,\mathrm{\dots },m=C\ln (n/\epsilon )$。

证明。

使用引理3.4的算法，我们首先计算由$V(G)$的所有子集$S$组成的集合${𝒯}_{\mathrm{\ell }}$，使得$|S|\le \mathrm{\ell }$与$G[S]$相连，为$\mathrm{\ell }=1\mathrm{\dots },m$。 这需要的时间以 ${(n/\epsilon )}^{O(1)}$ 为界。 收藏品 $$𝒞′ℓ​(G) 通过查找每个$S\in {𝒯}_{\mathrm{\ell }}$和每个$v\in S$可以从${𝒯}_{\mathrm{\ell }}$获得$v$在$G\setminus S$中有多少个邻居。 所以计算和列出的总时间 $$𝒞′ℓ​(G) 以${(n/\epsilon )}^{O(1)}$为界。

为了证明该 Lemma，让我们固定 $\mathrm{\ell }\le m$，并演示如何计算系数 $a_{F,\mathrm{\ell }}$，假设我们已经计算并列出了所有 的系数 $a_{F,{\mathrm{\ell }}^{\prime }}$。 让我们修复 $$Fε𝒞′ℓ​(G). 通过恒等式 (13)，足以计算 $i=1,\mathrm{\dots },\mathrm{\ell }$ 的 $e_i{p}_{\mathrm{\ell }-i}$ 中 ${\text{ind}}^{\ast }(F,\cdot )$ 的系数（其中我们设置 $p_0=1)$。 根据 (28)、(29) 和 (30)，我们知道 ${\text{ind}}^{\ast }(F,\cdot )$ 在 $e_i{p}_{\mathrm{\ell }-i}$ 中的系数为

${\displaystyle \sum _{\begin{array}{c}{F}_1\in {ℱ}_i\\ |V(F_1)|=i\end{array}}}{\displaystyle \sum _{F_2\in {ℱ}_{\mathrm{\ell }-i}}}{c}_{F_1,F_2}^F{a}_{F_2,(\mathrm{\ell }-i)}\cdot {\displaystyle \frac{p(F_1)(\mathscr{H}-J)}{k^{|E(F_1)|}}}$

$=$ ${\displaystyle \sum _{\begin{array}{c}S,T\subseteq V(F)\\ S\cup T=V(F)\\ |S|=i,|T|\le \mathrm{\ell }-i\end{array}}}{a}_{F(T),(\mathrm{\ell }-i)}\cdot {\displaystyle \frac{p(F(S))(\mathscr{H}-J)}{k^{|E(F(S))|}}}.$

对于每个这样的对 $(S,T)$，我们需要计算 $p(F(S))(J-\mathscr{H})k^{-|E(F(S))|}$ 并查找 $a_{F(T),(\mathrm{\ell }-i)}$。 我们可以在 $O(k^{\mathrm{\Delta }\mathrm{\ell }})={(n/\epsilon )}^{O(1)}$ 限制的时间内计算 $p(F(S))(J-\mathscr{H})k^{-|E(F(S))|}$。

在给定列表中查找 $a_{F(T),(\mathrm{\ell }-i)}$ 需要我们测试 $F(T)$ 与中每个片段的同构性 $$𝒞′ℓ−i ​(G) （注意 $a_{F(T),(\mathrm{\ell }-i)}=0$ 如果 $$F​(T) ∉𝒞′(ℓ−我)​(G) 由引理7.4)。 使用引理7.3来测试同构，这最多需要时间

$$O(|𝒞_{}^{\prime }{}_{(\mathrm{\ell }-i)}{}^{}(G)|{(\mathrm{\ell }-i)}^2{\mathrm{\Delta }}^{2(\mathrm{\ell }-i-1)})=O{(n/\epsilon )}^{O(1)}.$$

这里我们使用引理 3.3 来绑定 $|$𝒞′(ℓ−我)​(G)|≤|𝒯( ℓ−0>i1>)2>​3>(5>G6>)7>4>|8>. 总之，所有这些意味着 $p_{\mathrm{\ell }-i}{e}_i$ 中 ${\text{ind}}^{\ast }(F,\cdot )$ 的系数可以在 ${(n/\epsilon )}^{O(1)}$ 限制的时间内计算出来，因此系数 $a_{F,\mathrm{\ell }}$可以在时间${(n/\epsilon )}^{O(1)}$内计算。 因此所有系数$a_{F,\mathrm{\ell }}$为 $$Fε𝒞′ℓ​(G) 可以在以下时间范围内计算和列出 $|$𝒞′ℓ​(G)|​(n/ε)O0>​1>(3>14>)5>2>=(n/ε)O0>​1>(3>14>)5>2>. 这可以在时间 ${(n/\epsilon )}^{O(1)}$ 内对每个 $\mathrm{\ell }=1,\mathrm{\dots },m$ 完成。 ∎

为了完成定理的证明，我们通过添加所有数字 $a_{F,\mathrm{\ell }}{\text{ind}}^{\ast }(F,G)$ 来计算每个 $\mathrm{\ell }=1,\mathrm{\dots },m$ 的 $p_{\mathrm{\ell }}$ $$Fε𝒞′ℓ​(G). 这可以及时完成

$$O(m|𝒞_{}^{\prime }{}_m{}^{}(G)|n^2{\mathrm{\Delta }}^{2(m-1)})={(n/\epsilon )}^{O(1)},$$

我们使用计算 ${\text{ind}}^{\ast }(F,G)$ 与 $$Fε𝒞′ℓ​(G) 所花费的时间由引理 7.3 限制为 $O(n^2{\mathrm{\Delta }}^{2(m-1)})$。 至此证明完毕。

8结束语和开放式问题

在本文中，我们提出了一大类图多项式（BIGCP）不存在复根与有效近似评估这些多项式的（确定性）算法的存在之间的直接联系。 我们通过给出确定性多项式时间近似算法来说明其用途，该算法用于评估 Tutte 多项式、独立多项式和从有界度图上复数的自旋和边缘着色模型获得的图多项式。

正如引言中所指出的，定理 1.1 不允许我们有效地近似 的 $\lambda$ 处的独立多项式，但这可以通过相关性来完成衰变方法 cf.韦茨[50]。 然而，为了证实 Sokal [45] 的猜想，Peters 和第二作者 [38] 证明了以下事实：

Theorem 8.1.

让 $\epsilon >0$ 和 $\mathrm{\Delta }\in \mathbb{N}$。 则存在$\delta >0$，使得对于任意图$G=(V,E)$，最大度数最多为$\mathrm{\Delta }$，对于$v\in V$，存在${\lambda }_v\in ℂ$ > 满足

$$|\mathrm{\Im }({\lambda }_v)|\le \delta \text{, and}0\le \mathrm{\Re }(\lambda )\le (1-\epsilon )\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{(\mathrm{\Delta }-2)}^{\mathrm{\Delta }}}$$ (32)

对于所有 $v\in V$，我们有 $Z(G)({({\lambda }_v)}_{v\in V})\ne 0$。

现在将此结果与4.3节中的方法结合起来，得出结论，利用本文中的方法，我们可以有效地近似的$\lambda$处的独立多项式，从而给出了Weitz结果的不同证明。

让我们重申索卡尔的另一个猜想[30，猜想21]，如果该猜想为真，则通过本文的方法意味着我们有一个有效的算法来近似计算$(\mathrm{\Delta }+1)$-任何图中最大次数最多为$\mathrm{\Delta }$的着色。

Question 8.1。

让$\mathrm{\Delta }\in \mathbb{N}$。 对于满足 $\mathrm{\Re }(q)>\mathrm{\Delta }$ 的每个 $q\in ℂ$ 和最大度最多为 $\mathrm{\Delta }$ 的每个图 $G$，$Z_T(G)(-1,q)\ne 0$ 是真的吗？

缺乏复数根和高效近似算法之间的这种联系自然会导致这样的问题：对这些接近（复数）根的图多项式进行近似评估有多困难。 有鉴于此，我们指出在这个问题上已经取得了一些进展。 正如简介中提到的，存在最大度数最多为 $\mathrm{\Delta }$ 和 且 ${\lambda }_n\to -{\lambda }^{\ast }$ 的树序列 $T_n$，使得 $Z(T_n,{\lambda }_n)=0$。 Galanis、Goldberg 和 Štefankovič 利用这一点来表明，当 时，很难近似 $Z_G(\lambda )$ 。

自然出现的另一个问题如下。 Barvinok [2, 5] 发现了基于不存在零的准多项式时间近似算法，用于计算某些矩阵的永久矩阵。 3 节中介绍的计算 BIGCP 在有界度图上的逆幂和的方法似乎不适用于一般矩阵的常量。 找到一种也适用于永久物的更通用的方法将是非常有趣的。

我们在第 3 节中的算法结果可以解释为给出固定参数易处理性结果，用于确定某些图 $H$ 的 $\text{ind}(H,G)$。如果$G$具有有界度，则算法在时间$2^{O(|V(H)|}{|V(G)|}^{O(1)}$内运行。 但是，该算法仅适用于图 $H$，其中 $\text{ind}(H,\cdot )$ 是乘法图多项式的系数。 最近，我们能够将该算法扩展到所有图$H$；请参阅[37]。 一个自然的问题是我们的方法是否可以扩展到其他类别的图，例如平面图。 更具体地说，让我们提出以下问题。

Question 8.2。

是否有一种算法，给定一个平面（或更一般地说，有界属）图 $G$ 和 $k\in \mathbb{N}$，返回大小 $k$ 的独立集合的数量$G$ 在 $2^{O(k)}{|V(G)|}^{O(1)}$ 范围内的时间？

致谢

我们感谢 Alexander Barvinok 激发了讨论、提供了有用的评论并与我们分享了 [6] 中的结果。 我们感谢 Andreas Galanis 告知我们有关 [46] 的信息。 我们感谢 Pinyan Lu 对本文早期版本的一些有用的评论。

我们还感谢匿名审稿人提出的有益的意见和建议，改进了论文的表达。