使用泰勒定理进行近似计数：

一项调查

摘要

在本文中，我们考虑与图相关的某些众所周知的多项式，包括独立多项式和色多项式。 这些多项式对图中的某些对象进行计数：在独立多项式的情况下为独立集，在色多项式的情况下为适当的着色。 它们也被解释为统计物理学中的配分函数。

（大约）计算这些类型的多项式的算法问题已经被研究了近 50 年，特别是使用马尔可夫链技术。 大约八年前，Barvinok 基于泰勒定理设计了一种新的算法方法，用于计算某些矩阵的常量，此后该方法已应用于各种图多项式。 本文旨在对该方法进行简要介绍，并对相关技术和结果进行部分调查。

关键词：近似计数、独立多项式、复零点、色多项式。

1简介

计算计数是理论计算机科学的一个领域，其核心涉及对作为输入给出的某些组合对象内的某些结构进行计数的计算问题。 考虑计算某个逻辑公式的满足分配的数量，或图中独立集合的数量。 通常，要计数的结构具有一些自然加权，并且人们对加权计数感兴趣。

在本文中，我们重点关注图计数问题，特别是寻找有效的算法来（大约）计算某些输入图中感兴趣的对象。 我们这里考虑的计数问题是要计数的对象数量通常是图大小的超多项式并且不能在多项式时间内直接枚举的问题。 例如，图的独立集的数量可以随图的大小呈指数级增长 事实上，（大约）计算图的独立集的问题是一个丰富的研究领域（这里，图中的独立集是没有两个相邻的顶点的子集）。 精确计数问题通常在计算上很困难（独立集 [78, 86, 42] 就是这种情况），因此人们通常对计数问题的近似算法感兴趣。 一个值得注意的例外是计算图的生成树的问题。 生成树的数量通常与图的大小呈指数关系，但可以通过矩阵树定理[62]在多项式时间内对生成树进行计数。 在整篇文章中，我们使用计算图中独立集合的示例来说明我们讨论的各种想法。 事实上，这些想法更广泛地适用于计算许多其他图论对象，包括树、匹配、剪切和适当的着色（我们在文章末尾讨论适当的着色）。

基本的组合计数问题通常不直接处理，而是通过检查其相应的生成函数来更普遍地考虑。 例如，对于独立集，人们对独立多项式感兴趣，对于图$G=(V,E)$，独立多项式被定义为多项式

$$Z_G(\lambda ):=\sum _{S\subseteq V\text{independent}}{\lambda }^{|S|}=\sum _{k\ge 0}{\alpha }_k{\lambda }^k,$$

其中 ${\alpha }_k={\alpha }_k(G)$ 是 $G$ 中大小为 $k$ 的独立集合的个数。这个多项式编码了很多关于 $G$ 中独立集合（大小）的信息。例如，很容易看出 $Z_G(1)$ 给出了 $G$ 中独立集合的数量，而 $Z_G^{\prime }(1)/Z_G(1)$ 给出了 $G$ 中独立集合的平均大小。如果知道 $Z_G(\lambda )$ 在 $\lambda$ 非常大的情况下的值，就可以提取多项式的度数，即最大独立集的大小（已知 $NP$ 很难计算，甚至很难在一个常数因子内近似）。 这已经告诉我们，我们不应该期望能够在所有 $\lambda$ 值处有效地近似独立多项式。

在本文中，我们描述了一种最新技术，即所谓的 Barvinok 泰勒多项式插值方法（首次在 [7] 中介绍），用于设计计算计数问题的近似算法。 我们的目的是向读者介绍该方法背后的想法，并介绍所涉及的数学知识。 我们不打算对使用该技术的结果进行完整的调查，也不打算将我们提出的所有想法完全形式化。 对于后者，我们建议读者参考 Barvinok 的优秀著作[6]和[72]。

泰勒插值方法的一个显着特征是，除了应用于普通计数问题外，它还适用于负数和复数生成函数的评估。 这与早期的技术形成对比。 理解这种复杂评估的一个动机是量子计算[90,26,70,49]，尽管我们不会在这里讨论这一点。 另一个是，复杂的评估有时对于实际计数问题很有用（参见例如[3])，也许最重要的是，将我们的视角扩大到复杂平面可以更深入地理解各种计算的底层计算复杂性。计数问题（有关此问题的更多讨论，请参阅第 5 节）。

设计近似计数算法的其他技术（我们不会讨论）包括马尔可夫链蒙特卡罗方法（有关该领域的精彩介绍，请参阅 Jerrum [62])以及相关衰减方法由 Weitz [89] 以及 Bandyopadhyay 和 Gamarnik [4] 提出（参见例如 [6]第 5 章和第 6 章有介绍）。 最近的一项技术与 Barvinok 插值法密切相关，它基于统计物理学的簇扩展，由 Jenssen、Keevash 和 Perkins 引入[61]。 我们在第 4 节的末尾对此进行了一些说明。

1.1 与统计物理学的联系

我们遇到的计数问题的生成函数经常在统计物理学界进行研究（使用不同的术语）。 例如，独立多项式被称为统计物理学中硬核模型的配分函数。 硬核模型是气体模型。 给定一个处于平衡状态的封闭容器，考虑检查容器内一小部分空间中的气体。 该区域中的（离散）空间由网格图表示，其中图的顶点表示空间中的点。 每个这样的点可以被气体分子占据或未被占据，但由于分子之间的排斥力，空间中的相邻点不能同时被占据。 因此，在任何时刻，气体分子只能在网格中占据独立的集合。 在任何时刻，占据点形成网格的特定独立集合$S$的概率$\mathbb{P}(S)$与${\lambda }^{|S|}$成正比，其中$\lambda \in [0,\mathrm{\infty })$ 是一个类似温度的参数，通常称为逸度。 高温对应于较小的 $\lambda$ 值，正如我们直观地预期的那样，这使得我们不太可能在小空间区域中看到大量 $S$ 占用点。 从$\mathbb{P}(S)\propto {\lambda }^{|S|}$和${\sum }_{S\subseteq V\text{independent}}\mathbb{P}(S)=1$开始，我们看到$\mathbb{P}(S)={\lambda }^{|S|}/Z_G(\lambda )$。 这里我们看到独立多项式$Z_G(\lambda )$（这里称为硬核模型的配分函数）作为概率中的归一化常数出现。 同样，该配分函数不仅仅是一个归一化常数，它还编码了有关系统的大量物理信息。 例如，通过考虑 $\ln Z_G(\lambda )/|V(G)|$ 及其导数对于越来越大的图（通常是网格）的极限行为，这些极限函数的不连续性给出了有关系统中相变的信息，即系统中相变的急剧变化。与系统相关的物理参数表明系统发生质变。 我们引导读者访问[46]，对许多模型的相变进行全面而严格的数学处理，并引导读者访问[81,38,53]，了解更多关于硬-核心模型。 我们不会直接关注统计物理学，但最初由统计物理学家证明的一些结果将用于我们描述的算法方法中。

1.2预赛

我们已经提到了独立多项式作为我们可能希望近似的图多项式的示例。 独立多项式将作为整篇文章的运行示例来说明各种想法。 这里我们提到独立多项式的一些基本属性，让读者对这个对象有一个感受。

回想一下 $Z_G(\lambda )=\sum {\lambda }^{|S|}$，其中总和是 $G$ 的所有独立集合 $S$ 的总和。第一个容易但重要的事实是，空集是一个独立集，因此 $Z_G(0)$ （即多项式中的常数项）始终为 $1$。 另一个重要的事实是，独立性多项式是乘法，即 $Z_{G_1\cup G_2}(\lambda )=Z_{G_1}(\lambda )Z_{G_2}(\lambda )$，其中我们写 $G_1\cup G_2$ 表示图 $G_1$ 和 $G_2$ 的不相交联合。 这是因为 $G_1\cup G_2$ 的每个独立集合 $S$ 都可以唯一地写为 $S=S_1\cup S_2$，其中 $S_i$ 是 $G_i$。 因此${\lambda }^{|S|}={\lambda }^{|S_1|}{\lambda }^{|S_2|}$，它允许我们对总和进行因式分解。 使用这个乘法性质，我们还可以看到，例如，$k$ 孤立顶点的独立多项式是 ${(1+\lambda )}^k$。我们还可以直接看出$k$顶点上的完整图具有独立多项式$1+k\lambda$。

我们现在描述我们理想地希望为我们的图计数问题获得的算法类型。 假设 $p=p(G)$ 是一个图形参数，例如$p(G)$是$G$中独立集合的数量，或者对于某些固定的$\lambda$来说是$p(G)=Z_G(\lambda )$。 请注意，我们允许 $p(G)$ 为复数。 $p$ 的完全多项式时间近似方案（或简称 FPTAS）是一种以图 $G$ 和误差容限 $\epsilon >0$ 并输出一个（复）数 $N$，使得 $N=e^{\epsilon t}p(G)$ 对于某些 $t\in ℂ$ 和 $|t|\le 1$ 的时间多项式 $|G|$($G$的顶点数）和${\epsilon }^{-1}$ 请注意，当 $\epsilon$ 较小时，我们有 $N=e^{\epsilon t}p(G)\approx (1+\epsilon t)p(G)$，因此 $N$ 与 $p(G)$ 的真实值大致在 $\epsilon |p(G)|$ 的距离之内。 因此，我们将此类输出 $N$ 称为乘法 $\epsilon$ 近似（对于 $p(G)$)。 我们还讨论了提供与上述相同的近似值但在 $|G|$ 中运行时间超多项式的算法。

2 Barvinok插值法

在本节中，我们将描述 Barvinok 的泰勒多项式插值方法，该方法可应用于各种计数问题。 考虑一些图多项式，即每个图$G$都有一些关联的多项式$P(z)=P_G(z)$。 与独立多项式一样，我们应该想象 $P_G$ 是不可直接访问的，即至少它的一些系数很难从 $G$ 计算出来。然而，我们假设多项式$P_G$的次数总是以常数乘以$|G|$为界；对于独立多项式来说肯定是这种情况，并且对于人们可能考虑的大多数图多项式来说很容易验证。 我们的目标是（有效地）获得 $z\in ℂ$ 的 $P_G(z)$ 乘法 $\epsilon$ 近似值。

巴维诺克的见解是利用关于平滑函数的幂级数近似的泰勒定理来获得所需的近似值。 乍一看，我们似乎从泰勒定理中没有得到任何好处，因为多项式的泰勒级数只是多项式本身。 但是，请注意（非多项式）函数的截断泰勒级数给出了函数的加法 $\epsilon$-近似值，而我们感兴趣的是乘法 $\epsilon$-近似值。 因此，我们实际上不应该考虑 $P_G(z)$ 的泰勒级数，而应该考虑 $g(z):=\ln P_G(z)$ 的泰勒级数，然后对结果取指数以获得所需的近似值。

为此，考虑 $g(z)$ 的泰勒级数为零：

$$g(z)=\sum _{k=0}^{\mathrm{\infty }}\frac{g^{(k)}(0)}{k!}{z}^k,$$

其中$g^{(k)}$表示$g$的$k$阶导数。不幸的是，函数的泰勒级数通常不会对所有 $z\in ℂ$ 收敛。 我们很快就会回到收敛问题，但现在让我们假设泰勒级数对于我们感兴趣的值 $z$ 确实收敛到 $g(z)$。 在这种情况下，如果我们为上面 $g$ 的泰勒级数的前 $m$ 项编写 $T_m(z)$，那么对于 $m$ 足够大，我们将得到 ，即 $T_m(z)=g(z)+\epsilon t$ 对于某些 $t\in ℂ$ 和 。 取等式两边的指数，我们得到 $\exp (T_m(z))=\exp (\epsilon t)P_G(z)$，即 $\exp (T_m(z))$ 的乘法 $\epsilon$ - $P_G(z)$ 的近似值。

这为我们提供了所需的近似值，但仍然存在几个问题。 首先，存在上面提到的趋同问题。 其次，如果泰勒级数确实收敛，那么$m$必须有多大才能保证？ 最后，我们如何实际计算 $T_m(z)$ 以便计算 $P_G(z)$ 的近似值 $\exp (T_m(z))$ ？ 请注意，我们无法直接访问数字$g^{(k)}(0)$；这些必须以某种方式计算。

对于第一个问题的收敛性，泰勒定理指出，对于任何 $R>0$,$g$ 的泰勒级数在圆盘 $D_R:=\{z\in ℂ:|z|\le R\}$ 内收敛，前提是 $g$ 在 $D_R$ 内部进行解析。 在我们的例子中，这为所有 $z\in D_R$ 提供了 $P_G(z)\ne 0$。 因此泰勒级数将收敛于不包含 $P_G(z)$ 根的最大圆盘内。 为特定图多项式建立此类零自由度结果将是第 4 节的主题。

第二个问题涉及$g$泰勒级数的收敛速度。这里我们利用$g$的特殊形式作为多项式的对数。 如果 ${\eta }_1,\mathrm{\dots },{\eta }_d$ 是（复）根 $P_G(z)$ 然后我们可以写 $P_G(z)=a{\prod }_{i=1}^d(1-\frac{z}{{\eta }_i})$，其中 $a=P_G(0)$ 被假定为非零。 然后两边取对数，我们有

$$g(z)=\ln (a)+\sum _{i=1}^d\ln (1-(z/{\eta }_i)).$$

利用的$\ln (1-z)=-z-\frac{z^2}{2}-\frac{z^3}{3}-\mathrm{\cdots }$的泰勒级数，我们得到$g$的泰勒级数为

$$g(z)=\ln (a)-\sum _{i=1}^d\sum _{k=1}^{\mathrm{\infty }}\frac{{(z/{\eta }_i)}^k}{k}$$

对于（正是上面提到的零自由度的条件）。 假设 $|z|\le \delta {\min }_i|{\eta }_i|$ 对于某些 $\delta \in (0,1)$，这给出

$$|g(z)-T_m(z)|\le \sum _{i=1}^d\sum _{k=m}^{\mathrm{\infty }}\left|\frac{{(z/{\eta }_i)}^k}{k}\right|\le \sum _{i=1}^d\sum _{k=m}^{\mathrm{\infty }}{\delta }^k=\frac{d{\delta }^m}{1-\delta }.$$

为了通过 $\epsilon$ 绑定最后一个表达式，根据 $\delta$ 将 $m\ge C\ln (d/\epsilon )$ 用作某个常量 $C$ 就足够了。 对于这样的 $m$，我们知道 $\exp (T_m(z))$ 是 $P_G(z)$ 的乘法 $\epsilon$ 近似值。

实际计算 $T_m(z)$ 的最后一个问题更加微妙，在这里和下一节中只会部分解决。 我们将证明，如果我们知道 $P_G(z)$ 的前 $m=C\ln (d/\epsilon )$ 系数的值，那么我们可以计算时间 $\mathrm{poly}(m)$ 的导数 $g^{(0)},g^{(1)},\mathrm{\dots },g^{(m)}$ 。 然而，我们通常无法立即访问图多项式的第一个 $m$ 系数。 For example, in the case of the independence polynomial $Z_G(\lambda )$, the coefficient ${\alpha }_k$ of ${\lambda }^k$ is the number of independent sets of size $k$ in $G$: computing this naively with a brute force approach of checking every $k$-tuple of vertices takes time $n^k$ (where $n=|G|$) and so computing ${\alpha }_m$ takes time $n^m=n^{O(\ln n)}$ (noting that the degree of $Z_G$ i.e. the size of the largest independent set could be and often is linear in $n$). 在下一节中，我们将展示如何在 $\mathrm{poly}(n)$ 时间内计算 ${\alpha }_0,\mathrm{\dots },{\alpha }_m$，并且该想法可以推广到许多其他感兴趣的图多项式。 现在，以下是如何在给定 $P_G(z)$ 的第一个 $m$ 系数的情况下计算 $T_m(z)$。

假设$P(z)=P_G(z)=a_0+a_{1}z+\mathrm{\cdots }+a_d{z}^d$。 我们定义了$g(z)=\ln P_G(z)$。 我们知道$g^{(0)}(0)=g(0)=\ln (a_0)$。 如果我们微分一次并重新排列，我们得到$g^{(1)}(z)P(z)=P^{(1)}(z)$。 如果我们现在重复微分这个表达式，我们得到以下表达式：

$P^{(1)}$ $=g^{(1)}{P}^{(0)}$

$P^{(2)}$ $=g^{(2)}{P}^{(0)}+g^{(1)}{P}^{(1)}$

$\mathrm{⋮}$

$P^{(r)}$ $=g^{(r)}{P}^{(0)}+\left({\displaystyle \genfrac{}{}{0pt}{}{r-1}{1}}\right)g^{(r-1)}{P}^{(1)}+\left({\displaystyle \genfrac{}{}{0pt}{}{r-1}{2}}\right)g^{(r-2)}{P}^{(2)}+\mathrm{\cdots }+\left({\displaystyle \genfrac{}{}{0pt}{}{r-1}{r-1}}\right)g^{(1)}{P}^{(r-1)}.$

将这些表达式评估为零，并注意 $P^{(r)}(0)=r!a_r$，我们得到

$a_1$ $=a_0{g}^{(1)}(0)$

$2a_2$ $=a_0{g}^{(2)}(0)+a_1{g}^{(1)}(0)$

$\mathrm{⋮}$

$r{a}_r$ $=a_0{g}^{(r)}(0)+{\displaystyle \frac{(r-1)!}{(r-1)!}}{a}_1{g}^{(r-1)}(0)+{\displaystyle \frac{(r-1)!}{(r-2)!}}{a}_2{g}^{(r-2)}(0)+\mathrm{\cdots }+{\displaystyle \frac{(r-1)!}{1!}}{a}_{r-1}{g}^{(1)}(0).$

我们看到，如果我们知道 $a_0,\mathrm{\dots },a_r$ 并且计算了 $g^{(0)}(0),\mathrm{\dots },g^{(r-1)}(0)$，那么我们可以使用上面的 $r$ 方程来计算 $g^{(r)}(0)$时间$O(r)$。 因此，给定$a_0,\mathrm{\dots },a_m$，我们可以在$O(m^2)$时间内计算$T_m(z)$。

下面总结了我们在本节中所展示的内容，也是泰勒多项式插值方法的本质。

Theorem 2.1.

假设 $𝒢$ 是一组（无限）图，对于每个 $G\in 𝒢$,$P_G(z)$ 是与 $G$ 关联的多项式，其中

$$P_G(z)=\sum _{i=0}^{d(G)}{a}_i(G)z^i$$

假设存在 $R>0$ 和一个具有以下属性的函数 $T:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$

• $P_G(z)\ne 0$ 每当 $|z|\le R$ 对于所有图表 $G\in 𝒢$ 和

• 我们能够在 $T(|G|,i)$ 范围内计算 $a_i(G)$，为了方便起见，我们假设 $T$ 两个参数都是非递减的。

然后有一个算法，给定输入 $G\in 𝒢$、$\epsilon >0$ 和 $z\in ℂ$ 以及 ，计算乘法 $\epsilon$ - 时间 $mT(n,m)+O(m^2)$ 中 $P_G(z)$ 的近似值，其中 $n=|G|$ 和 $m:=C\ln (d(G)/\epsilon )$（如前面所定义）。

有些评论是有顺序的。 该定理是针对一般类图 $𝒢$ 而不是所有图制定的，因为通常我们只能对某些类型的图（通常是有界度图）有效地建立条件 (i) 和 (ii) 。 通过将上述结果应用于独立多项式可以最好地说明这一点。

对于独立多项式，如果我们将$𝒢$视为所有图的集合，则不存在正半径的零自由盘 所以我们只能在条件(i)中取$R=0$。 但是，如果我们将 $𝒢$ 限制为最大度 $\mathrm{\Delta }$ 的图，我们将在第 4 节中看到我们可以采用 $R={(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}/{\mathrm{\Delta }}^{\mathrm{\Delta }}$。 类似地，对于条件 (ii)，如果我们将 $𝒢$ 视为所有图，那么前面提到的强力方法本质上是计算 $Z_G(\lambda )$ 系数的唯一方法，给出 $T(n,k)=O(n^k)$：总体而言，这给出了$mT(n,m)+O(m^2)=n^{O(m)}+O(m^2)=n^{O(\ln (n/\epsilon ))}$的超多项式运行时间。 这样的拟多项式运行时间已经非常有前途，因为它明显优于暴力算法的指数运行时间。 然而，在下一节中，我们将看到，对于最大度数为 $\mathrm{\Delta }$ 的图，我们可以更快地计算系数并采用 $T(n,k)=\mathrm{poly}(n){\mathrm{\Delta }}^{O(k)}$，从而建立总体多项式运行时间$T(n,m)=\mathrm{poly}(n){\mathrm{\Delta }}^{O(m)}=\mathrm{poly}(n){\mathrm{\Delta }}^{O(\ln (n/\epsilon ))}={(n/\epsilon )}^{O(\ln \mathrm{\Delta })}$。 因此，结合接下来两部分的结果将给出一个 FPTAS，用于在提供 的情况下在最多 $\mathrm{\Delta }$ 的最大度图上计算 $Z_G(\lambda )$。

最后，我们指出，实际上可以放宽条件（i）以包括不一定是圆盘的区域，前提是该区域在某种意义上是“厚”的并且包含点$0$。 具体来说，我们应该考虑实数区间或扇形区域的一个小邻域。 对非盘区域的松弛条件(i)是通过对$P_G$进行适当的多项式变换来实现的；详情请参阅[6]和[10]第2.2.2节。

3 有界度图的多项式运行时间

在上一节中，我们了解了如何使用泰勒定理来设计算法来近似图多项式。 令 $P=P_G$ 为图形多项式。 检查定理2.1，我们需要两个成分来建立近似算法来计算$P_G(z)$。 首先我们需要为$P_G$建立一个零空闲磁盘；这将在下一节中详细讨论。 其次，我们需要能够有效地计算 $P_G$ 的第一个 $O(\ln |G|)$ 系数，我们将在此处详细讨论。 通常有一种简单、直接的方法来计算这些系数，从而产生拟多项式时间算法，但对于 FPTAS 来说速度不够快。 我们已经在上一节的独立多项式中看到了这一点，我们看到简单地计算系数会导致 $n^{O(\ln n)}$ 时间算法。 在本节中，我们将展示如何更有效地计算有界度图的独立多项式的系数。 该技术可推广到许多其他图多项式，但通过独立多项式的具体示例可以最好地理解所有关键思想。 我们在本节的末尾给出了一般图多项式的陈述。

值得注意的是，除了少数例外，有界度图的设置通常是感兴趣的设置。 例如，如果我们对 $G$ 没有限制，那么计算 $Z_G(z)$ 的乘法 $\epsilon$ 近似值的问题对于所有复杂 $z\ne 0$ 来说都是难以计算的；参见 [84,51,23]。

3.1 高效计算独立多项式的系数

回想一下，独立多项式 $Z_G(\lambda )$ 由下式给出

$$Z_G(\lambda )=\sum _{k\ge 0}{\alpha }_k{\lambda }^k,$$

其中${\alpha }_k={\alpha }_k(G)$是$G$中大小为$k$的独立集合的数量。在本节中，我们重点关注有界度图，并为最大度数最多为 $\mathrm{\Delta }$ 的图集编写 ${𝒢}_{\mathrm{\Delta }}$。 如果我们将定理 2.1 应用于 $Z_G(\lambda )$（含 $G\in {𝒢}_{\mathrm{\Delta }}$），假设我们有一些合适的无零磁盘，其中包含 $\lambda$，那么定理 2.1 给出了在 $mT(n,m)+O(m^2)$ 时间内计算 $Z_G(\lambda )$ 的乘法 $\epsilon$ 近似值的算法，其中 $T(n,i)$ 是计算 $n$ 顶点图 $G\in {𝒢}_{\mathrm{\Delta }}$ 和 $m\le C\ln (n/\epsilon )$ 的 ${\alpha }_i(G)$ 所需的时间。 我们将草拟以下证明。

Theorem 3.1.

对于 $G\in {𝒢}_{\mathrm{\Delta }}$，我们可以用 $\mathrm{poly}(|G|){\mathrm{\Delta }}^{O(i)}$ 的时间计算 ${\alpha }_i(G)$，也就是说，对于最大度最多为 $\mathrm{\Delta }$ 的 $n$ 顶点图，我们可以用 $T(n,i)=\mathrm{poly}(n){\mathrm{\Delta }}^{O(i)}$ 的时间计算。

利用上面的定理，定理 2.1 为我们提供了具有运行时间的独立多项式的近似算法

$$mT(n,m)+O(m^2)=\mathrm{poly}(\mathrm{n}){\mathrm{\Delta }}^{O(\ln (n/\epsilon )}=\mathrm{poly}(\mathrm{n}){(n/\epsilon )}^{O(\ln (\mathrm{\Delta }))}.$$

我们看到这个运行时间是完全多项式时间近似方案所需的形式。 现在我们概述定理3.1的证明。

定理3.1的草图证明

我们首先概括我们感兴趣的算法问题。 我们感兴趣的是计算${\alpha }_k(G)$，即$G\in {𝒢}_{\mathrm{\Delta }}$时$G$中大小为$k$的独立集合的数量。 等价地，${\alpha }_k(G)$是图$I_k$在$G$中的诱导副本数，其中$I_k$是由$k$ 有顶点，没有边。 一般对于图$H$和$G$，写$\text{ind}(H,G)$为诱导副本数 $G$ 中的 $H$。然后${\alpha }_k(G)=\text{ind}(I_k,G)$。

第一个观察结果是，虽然我们不知道如何有效地计算 $\text{ind}(I_k,G)$，但当 $H$ 连接时，有效地计算 $\text{ind}(H,G)$ 并不难。

Observation 3.1。

我们可以在 $\mathrm{poly}(n){\mathrm{\Delta }}^{O(k)}$ 时间内计算 $\text{ind}(H,G)$，其中 $G\in {𝒢}_{\mathrm{\Delta }}$、$n=|G|$ 和 $k=|H|$。

为了看到这一点，我们首先选择 $H$ 中的任何生成树 $T$ （即 $H$ 的子图，它是一棵树并且使用所有 $k$ $H$ 的顶点）。 这样的生成树之所以存在，是因为$H$是相连的。 我们的想法是找到 $G$ 中 $T$ 的所有（不一定是诱导的）副本，并检查 $T$ 的哪些副本扩展到 $H$ 的诱导副本。这说明了 $H$ 的所有诱导副本，因为 $G$ 中 $H$ 的每个诱导副本都包含 $G$ 中 $T$ 的一个（不一定是诱导的）副本。

$G$ 中只有相对较少的（不一定是诱导的）$T$ 副本。事实上，首先我们以广度优先顺序 $v_1,v_2,\mathrm{\dots },v_k$ 枚举 $T$ 的顶点。 我们按顺序一次将 $T$ 嵌入 $G$ 一个顶点。 有 $n$ 个选项可以选择嵌入 $v_1$ 的位置。 $T$ 的每个后续顶点最多有 $\mathrm{\Delta }$ 嵌入 $G$ 的可能性，因为当我们嵌入 $v_i$ 时，其在 $T$ 中的父顶点（例如 $v_{i^{\prime }}$）已被嵌入为 $G$ 中的某个顶点 $x_{i^{\prime }}$，因此 $v_i$ 的嵌入必须是 $x_{i^{\prime }}$ 在 $G$ 中的邻接。因此，在 $G$ 中，$T$ 的嵌入最多有 $n{\mathrm{\Delta }}^{k-1}$，我们将检查 $T$ 的每个嵌入是否给出了 $H$ 的诱导副本。

从观察 3.1 中，我们看到当 $H$ 连接时我们可以计算 $\text{ind}(H,G)$，但是我们感兴趣的图 $H$ ，即 $I_k$，非常不连贯。 如果我们能够用 $\text{ind}(H,G)$ 来表达连接的 $H$ 的 $\text{ind}(I_k,G)$，那将会很有用。一个简单的例子是 $\text{ind}(I_2,G)=\left(\genfrac{}{}{0pt}{}{n}{2}\right)-\text{ind}(e,G)$，其中 $e$ 是两个顶点上的图，两个顶点之间有一条边。 这只是说明 $n$ 顶点图中的边和非边的数量总和为 $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$。 通过更多的工作，我们可以用连通图的归纳计数来表达 $\text{ind}(I_3,G)$ ，如下所示。 三个顶点上有四个图，分别为 $I_3$、表示为 $T$ 的三角形、表示为 $P_3$ 的三个顶点上的路径以及一条边和一条边的不相交并集。顶点表示为$e+I_1$。 通过枚举 $G$ 在三个顶点上的所有导出子图，我们有

$$\text{ind}(I_3,G)=\left(\genfrac{}{}{0pt}{}{n}{3}\right)-\text{ind}(T,G)-\text{ind}(P_2,G)-\text{ind}(e+I_1,G).$$

右侧唯一断开的图是$e+I_1$，通过简单的计数，不难看出

$$\text{ind}(e+I_1,G)=(n-2)\text{ind}(e,G)-2\text{ind}(P_3,G)-3\text{ind}(T,G).$$

将第二个公式代入第一个公式，给出了用连通图的归纳计数表示的 $\text{ind}(I_3,G)$ 表达式。

这些计算表明，可以用连通图$H$的诱导计数$\text{ind}(H,G)$来表达$\text{ind}(I_k,G)$，但计算和公式会变得繁琐。 需要一种新的想法来以系统且可管理的方式解决这个问题。 接下来的观察是克服这一障碍的关键见解，也是定理 3.1 证明的核心。 被Csikvári和Frenkel[36]证明；证明很短，也可以在[72]中找到。

Observation 3.2。

假设$\tau (G)$是一个加性图属性，意味着它满足以下两个属性。

• $\tau (G)$ 可以写为归纳图计数的乘积之和，即对于所有 $G$

  $$\tau (G)=\sum _{i=1}^r{\mu }_i\prod _{H\in {\mathscr{H}}_i}\text{ind}(H,G),$$

  其中 ${\mathscr{H}}_i$ 是一组（有限）图形，${\mu }_i\in ℂ$ 是每个 $i=1,\mathrm{\dots },r$ 的常量，并且

• $\tau (G_1\cup G_2)=\tau (G_1)+\tau (G_2)$ 适用于所有图表 $G_1$ 和 $G_2$。

那么 $\tau$ 实际上是一种更简单的形式，即对于所有图 $G$，我们有

$$\tau (G)={\lambda }_1\text{ind}(H_1,G)+\mathrm{\cdots }+{\lambda }_s\text{ind}(H_s,G),$$

其中$H_1,\mathrm{\dots },H_s$是连接的图和${\lambda }_1,\mathrm{\dots },{\lambda }_s\in ℂ$。

上面的观察表明，每个加性图参数都是 $\text{ind}(H_i,G)$ 的线性组合 connected $H_i$，因此通过观察 3.1 ，可以有效地计算此类加性图参数。 我们的任务现在简化为用加性图参数来表达 ${\alpha }_k(G)=\text{ind}(I_k,G)$ 的任务。 为了做到这一点，我们现在从 ${\alpha }_k(G)$ 的组合角度切换到多项式角度。

回想一下，${\alpha }_k(G)$ 是独立多项式 $Z_G$ 的系数，即 $Z_G(\lambda )={\alpha }_0+{\alpha }_1\lambda +\mathrm{\cdots }{\alpha }_d{\lambda }^d$。 假设${\eta }_1,\mathrm{\dots },{\eta }_d$是$Z_G$的根。 注意到常数项${\alpha }_0$是1，我们可以写成$Z_G(\lambda )=(1-{\eta }_1^{-1}\lambda )\mathrm{\cdots }(1-{\eta }_d^{-1}\lambda )$。 虽然我们无法直接计算 ${\eta }_i$，但我们可以通过扩展上面的乘积将它们与系数 ${\alpha }_k$ 联系起来。 我们看到${\alpha }_k$是${\eta }_i^{-1}$中的初等对称多项式，即

另一类重要的对称多项式是幂和。 让我们定义$i$次方和$p_i$为

$$p_i={\eta }_1^{-i}+\mathrm{\cdots }+{\eta }_d^{-i}.$$

众所周知，幂和可以使用牛顿恒等式与初等对称多项式相关。 这些恒等式有几个简短的派生。 在我们的问题中，牛顿恒等式给出了以下与 ${\alpha }_i$ 和 $p_i$ 相关的表达式。

$-{\alpha }_1$ $={\alpha }_0{p}_1$

$-2{\alpha }_2$ $={\alpha }_0{p}_2+{\alpha }_1{p}_1$

$-3{\alpha }_3$ $={\alpha }_0{p}_3+{\alpha }_1{p}_2+{\alpha }_2{p}_1$

$\mathrm{⋮}$

$-t{\alpha }_t$ $={\alpha }_0{p}_t+{\alpha }_1{p}_{t-1}+\mathrm{\cdots }+{\alpha }_{t-1}{p}_1.$

由此很容易看出，如果我们知道$p_i$的值，那么我们就可以归纳计算${\alpha }_i$。 事实上，如果我们知道 $p_1,\mathrm{\dots },p_t$ 的值，并且我们也知道（通过归纳）${\alpha }_1\mathrm{\dots },{\alpha }_{t-1}$ 的值，然后使用 $t^{th}$ 恒等式，我们可以计算 ${\alpha }_t$。 因此，有效计算${\alpha }_i$的问题就简化为有效计算$p_i$的问题。 可以有效地计算幂和，因为正如读者可能已经猜到的那样，幂和是加性图参数。

Observation 3.3。

上面定义的功率和$p_i=p_i(G)$具有作为加性图参数的属性。

很容易验证 $p_i$ 满足图形参数可加性的第二个属性，即对于任何图形 $G_1$ 和 $G_2$ $p_i(G_1\cup G_2)=p_i(G_1)+p_i(G_2)$ 。 事实上，由于$Z_{G_1\cup G_2}=Z_{G_1}{Z}_{G_2}$（参见第1.2节），如果${\eta }_1,\mathrm{\dots },{\eta }_d$是$Z_{G_1}$和${\nu }_1,\mathrm{\dots },{\nu }_{d^{\prime }}$的根> 是 $Z_{G_2}$ 的根，那么 ${\eta }_1,\mathrm{\dots },{\eta }_d,{\nu }_1,\mathrm{\dots },{\nu }_{d^{\prime }}$ 是 $Z_{G_1\cup G_2}$ 的根，因此

$$p_i(G_1\cup G_2)={\eta }_1^{-i}+\mathrm{\cdots }+{\eta }_d^{-i}+{\nu }_1^{-i}+\mathrm{\cdots }+{\nu }_{d^{\prime }}^{-i}=p_i(G_1)+p_i(G_2).$$

对于第一个属性，我们使用牛顿恒等式。 请注意，从${\alpha }_0=1$开始，我们可以重新排列$t^{\mathrm{th}}$身份并将$p_t$表示为$p_1,\mathrm{\dots },p_{t-1}$和${\alpha }_1,\mathrm{\dots },{\alpha }_t$。 我们知道 ${\alpha }_i$ 是归纳图计数，如果我们通过归纳假设 $p_1,\mathrm{\dots },p_{t-1}$ 也是归纳图计数的乘积之和，那么我们会看到 $p_t$ 也是导出图计数的乘积之和，因此满足加法图参数的属性 (i)。

现在我们已经掌握了解释如何有效计算 ${\alpha }_k$ 的所有要素。 我们可以有效地计算功率和$p_i$。 这是因为幂和是加性图参数（观察3.3)，因此它们是连通图的诱导计数的线性组合（观察3.2 ）。 由于 $H$ 已连接，因此当 $G$ 具有有界度时，可以有效地计算此线性组合中的每个导出图计数 $\text{ind}(H,G)$（观察 3.1)从而使我们能够有效地计算功率和。 一旦我们计算了幂和$p_1,p_2,\mathrm{\dots }$，我们就可以使用牛顿恒等式归纳计算${\alpha }_i$。

这给出了论证的主要思想，尽管我们忽略了一些微妙之处。 主要的一个问题是，我们能否有效地计算功率和$p_i(G)$（即在时间$\mathrm{poly}(|\mathrm{G}|){\mathrm{\Delta }}^{O(i)}$内）并不十分明显。 而$p_i(G)$可以表示为连通图的诱导计数的线性组合

$$p_i(G)={\lambda }_1\text{ind}(H_1,G)+\mathrm{\cdots }+{\lambda }_s\text{ind}(H_s,G),$$

我们还没有说如何找到$H_1,\mathrm{\dots },H_s$和${\lambda }_1,\mathrm{\dots },{\lambda }_s$。 可以想象，$s$在$i$中可能是超指数的，或者$H_i$在$i$中可能是超线性的；无论哪种情况，我们都不会自动获得所需的运行时间。 然而，通过更仔细地使用牛顿恒等式，并利用 $G$ 有界度这一事实，克服这些技术障碍并不是太困难。 所有详细信息可以在[72]中找到。

3.2 高效计算其他图多项式的系数

在第 3.1 节中，我们介绍了如何高效计算有界度图 $G$ 的独立性多项式 $Z_G$ 的第一个 $\ln |G|$ 系数的主要思路。 这些想法可以推广到适用于许多其他感兴趣的图多项式。

我们在定理 3.1 的草图证明中使用的独立多项式 $Z_G$ 的关键属性是什么？ 整个证明基于操纵诱导图计数，因此我们当然需要 $Z_G$ 的系数是诱导图计数（的函数）。 我们还非常需要 $Z_G$ 是乘法的，这使我们能够得出幂和是加法的结论，从而使我们能够有效地计算它们。

在[72]中，我们证明了如果一个图多项式 $P=P_G$ 满足下面给出的某些性质，那么它的系数可以高效地计算有界度图，即 $P_G$ 的 $i$ 次系数可以在 $\mathrm{poly}(n){\mathrm{\Delta }}^{O(i)}$ 时间内计算，其中 $G$ 是一个最大度最多为 $\mathrm{\Delta }$ 的 $n$ 顶点图。 与独立多项式一样，这足以使用 2 节中的泰勒多项式插值方法来给出计算 $P_G(z)$ 的近似算法（假设 $z$ 为在合适的零可用磁盘中）以及 FPTAS 所需的运行时间。

假设$P=P_G$是由$P_G(z)=a_0+a_{1}z+\mathrm{\cdots }+a_d{z}^d$给出的图多项式。 假设对于某个固定常量 $\alpha >0$,$P$ 满足以下属性：

• 对于每个$\mathrm{\ell }$,$P$的第$\mathrm{\ell }$系数可以表示为诱导图计数的“$\alpha$有界”线性组合，即对于所有 $G\in {𝒢}_{\mathrm{\Delta }}$

  $$a_{\mathrm{\ell }}(G)=\sum _H{\zeta }_{H,\mathrm{\ell }}\text{ind}(H,G),$$

  其中总和是在最多具有 $\alpha \mathrm{\ell }$ 个顶点的图 $H$ 上进行的，并且 ${\zeta }_{H,\mathrm{\ell }}\in ℂ$ 是常量（独立于 $G$)；

• 在属性 (i) 中，对于每个 $H$，我们可以在 $\exp (O(|H|)$ 时间内计算 ${\zeta }_{H,\mathrm{\ell }}$；和

• $P_G$ 是乘法，即 $P_{G_1\cup G_2}=P_{G_1}{P}_{G_2}$。

然后我们可以在$\mathrm{poly}(|G|){\mathrm{\Delta }}^{O(i)}$时间内计算$a_i(G)$。 再次，使用泰勒多项式插值方法，这会导致 FPTAS 近似 $G\in {𝒢}_{\mathrm{\Delta }}$ 的 $P_G(z)$，前提是我们建立一个包含 $z$ 的合适的无零磁盘。

请注意，在独立多项式的情况下，属性 (i) 和 (ii) 是微不足道的，我们看到很容易验证属性 (iii)。 这些属性也适用于各种其他图多项式，包括匹配多项式、色多项式和 Tutte 多项式。我们不会在这里检查这些，但请感兴趣的读者参考[ 72]。 还值得注意的是，本节中描述的技术可以适用于超出满足上述属性 (i)-(iii) 的多项式；请参阅[68,15,70]。

在第 2 节中，我们解释了如何使用泰勒定理设计近似图多项式的算法。 在本节中，我们展示了如何使这些算法对许多图多项式有效（具有 FPTAS 的运行时间），前提是我们将注意力限制在有界度图上。 我们在第 2 节中看到，所有这些算法的关键是在复平面中为所讨论的图多项式建立合适的无零盘或无零区域。 我们对算法的讨论到此结束，在下一节中，我们将注意力完全转向建立这些零自由区域的独立问题。

4 证明不存在零的技术

在前面的章节中，我们概述了如何在复平面区域中近似评估图多项式（特别是独立多项式）的问题简化为确定多项式在该区域中没有零点的问题。 证明有关图多项式和配分函数的零点位置的此类结果有着悠久的历史。 所使用的技术通常起源于统计物理学，但现在已被理论计算机科学界采用并扩展。 在本节中，我们将讨论三种不同的技术。

4.1 递归和比率

许多图多项式满足递归，其中给定图的多项式可以用较小图的多项式来表示。 这种递归使我们能够通过归纳证明图多项式的属性，例如不存在零。 然而，与直接使用多项式相比，使用相关量通常会更有效率。 我们通过独立多项式的运行示例来说明这种方法，并在本节的末尾指导读者进一步使用该技术。

我们的目标是根据 Shearer [83]、Dobrushin [38] 以及 Scott 和 Sokal [81] 得出以下结果的证明:

Theorem 4.1.

令$G=(V,E)$为最大度$\mathrm{\Delta }\ge 2$的图，并令$\lambda \in ℂ$满足$|\lambda |\le {\lambda }^{\ast }(\mathrm{\Delta }):=\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{\mathrm{\Delta }}^{\mathrm{\Delta }}}$。 然后$Z_G(\lambda )\ne 0$。

在深入研究证明之前，让我们先简单讨论一下这个结果。 首先，回想一下，通过泰勒多项式插值方法（特别是定理 2.1 和定理 3.1)，该结果立即意味着用于计算 $Z_G(\lambda )$ 的 FPTAS $G\in {𝒢}_{\mathrm{\Delta }}$ 在 给出的零空闲磁盘内。 其次，请注意，如果我们只对零空闲磁盘感兴趣，那么就无法改进定理4.1，因为我们无法增加常数${\lambda }^{\ast }(\mathrm{\Delta })$。 事实上，我们可以证明存在一系列最大度 $\mathrm{\Delta }$ 和负数 ${\lambda }_n$ 的图 $G_n$（实际上是树），使得 $Z_{G_n}({\lambda }_n)=0$ 和 ${\lambda }_n\to -{\lambda }^{\ast }(\mathrm{\Delta })$ [81]。 然而，最近人们对建立非磁盘区域的零自由度产生了很大的兴趣。 最值得注意的是，最近[74]表明，每当$G\in {𝒢}_{\mathrm{\Delta }}$和$\lambda \in R\subseteq ℂ$（其中$R$)时，$Z_G(\lambda )\ne 0$包含区间 $[0,{\lambda }_c(\mathrm{\Delta }))$ 和 ${\lambda }_c(\mathrm{\Delta }):={(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}/{(\mathrm{\Delta }-2)}^{\mathrm{\Delta }}$ 的开集。 ${\lambda }_c(\mathrm{\Delta })$的一个重要意义在于它是实参数$\lambda$的算法阈值：使用插值方法，[74]中的结果意味着存在一个FPTAS 每当$G\in {𝒢}_{\mathrm{\Delta }}$和$\lambda \in [0,{\lambda }_c(\mathrm{\Delta }))$时计算$Z_G(\lambda )$，而对于$\lambda >{\lambda }_c(\mathrm{\Delta })$，已知不存在这样的FPTAS，除非$P=NP$ [84, 51]。

现在我们讨论定理4.1的证明。 令$G=(V,E)$为图并固定顶点$v\in V$。 我们可以通过将总和拆分为不包含 的独立集合和包含 $v$ 的独立集合来写出 $Z_G(\lambda )={\sum }_{S\subseteq V\text{independent}}{\lambda }^{|S|}$ 的递归，以获得

$$Z_G(\lambda )=Z_{G-v}(\lambda )+\lambda Z_{G\setminus [N[v]}(\lambda ),$$ (1)

其中 $G-v$ （分别为 $G\setminus N[v]$)表示通过删除 $v$ 从 $G$ 获得的图（resp. $v$ 及其邻居 $G$)。 如前所述，事实证明，使用相关量的递归比直接使用 $Z_G$ 的递归更有用。 定义比率、$R_{G,v}$，如下

$$R_{G,v}(\lambda ):=\frac{\lambda Z_{G\setminus N[v]}(\lambda )}{Z_{G-v}(\lambda )}.$$ (2)

观察一下，提供了 $Z_{G-v}(\lambda )\ne 0$，当且仅当 $R_{G,v}(\lambda )=-1$ （使用 (1)）时，我们才有 $Z_G(\lambda )=0$。 因此，为了证明不存在零，只需归纳证明比率避免 $-1$ 即可。

接下来我们为这些比率建立递归。 令 $G$ 为具有固定顶点 $u_0$ 的图，并令 $\lambda \in ℂ$ 。 令 $u_1,\mathrm{\dots },u_d$ 为 $G$ 中 $u_0$ 的邻居（以任何顺序）。 设置$G_0=G-u_0$并定义$i=1,\mathrm{\dots },d$、$G_i:=G_{i-1}-u_i$（因此$G_d=G\setminus N[u_0]$)。 假设 $Z_{G_i}(\lambda )\ne 0$ 代表所有 $i=0,\mathrm{\dots },d$。 然后我们使用'telescoping'来写

$$\frac{R_{G,u_0}(\lambda )}{\lambda }=\frac{Z_{G_d}(\lambda )}{Z_{G_0}(\lambda )}=\frac{Z_{G_1}(\lambda )}{Z_{G_0}(\lambda )}\cdot \frac{Z_{G_2}(\lambda )}{Z_{G_1}(\lambda )}\mathrm{\cdots }\frac{Z_{G_d}(\lambda )}{Z_{G_{d-1}}(\lambda )}.$$

将 (1) 应用于每个分母，经过一些重新排列后，我们最终得到以下恒等式：

$$R_{G,u_0}(\lambda )=\frac{\lambda }{{\prod }_{i=1}^d(1+R_{G_{i-1},u_i}(\lambda ))}.$$ (3)

上面的恒等式捕获了我们需要的独立集合的所有相关组合，其余的证明本质上可以归结为证明有关上述递归的属性。

定理证明4.1。

我们可以假设 $G$ 是连通的（如果 $G$ 具有连通分量 $H_1,\mathrm{\dots },H_k$，则 $Z_G(\lambda )=Z_{H_1}(\lambda )\mathrm{\cdots }{Z}_{H_k}(\lambda )$，因此足以证明该定理每个$H_i$)。

修复$v_0\in V$。 我们将通过归纳证明以下内容适用于所有 $U\subseteq V\setminus \{v_0\}$：

• $Z_{G[U]}(\lambda )\ne 0$，

• 如果$u_0\in U$在$V\setminus U$中有邻居，则。

事实上，如果 $|U|=0$ 则这很简单，所以假设 $|U|>0$。 那么由于$G$已连接，因此$u_0\in U$有一个邻居$v\in V\setminus U$。 让我们写成$H=G[U]$，并让$u_1,\mathrm{\dots },u_d$成为$H$中$u_0$的邻居。让 $H_0=H-u_0$ 和 $H_i=H_{i-1}-u_i$ 代表 $i>0$。 然后，通过归纳$Z_{H_i}(\lambda )\ne 0$和（因为$u_{i+1}$在$U\setminus V(H_i)$中有一个邻居，即$u_0$)。 因此我们可以使用 (3) 得出结论

$|R_{H,u_0}(\lambda )|={\displaystyle \frac{|\lambda |}{{\prod }_{i=1}^d|1+R_{H_{i-1},u_i}(\lambda )|}}$

$\le |\lambda |{\left({\displaystyle \frac{\mathrm{\Delta }-1}{\mathrm{\Delta }}}\right)}^{-(\mathrm{\Delta }-1)}=1/\mathrm{\Delta },$ (4)

我们使用了 $d\le \mathrm{\Delta }-1$ （因为 $u_0$ 在 $V\setminus U$ 中有一个邻居）和 $|\lambda |\le {\lambda }_{\mathrm{\Delta }}$。 这表明 (ii)。 然后，我们还看到 $R_{H,u_0}(\lambda )\ne -1$ 和 $Z_H(\lambda )\ne 0$，显示 (i)。 这样就完成了归纳。

为了得出定理的证明，我们再次对 $R_{G,v_0}$ 应用相同的技巧。 然后，我们从 (4) 获得边界 ，因为 $v_0$ 可能有 $d=\mathrm{\Delta }$ 邻居，而不是 $d\le \mathrm{\Delta }-1$ 。 同样，我们有 $R_{G,v_0}(\lambda )\ne 1$ 和 $Z_G(\lambda )\ne 0$，根据需要。 ∎

证明本质上包括两个步骤。 首先用较小图的比率来表达适当选择的比率。 其次，使用这个表达式归纳表明这些比率被“捕获”在复平面的某个合适区域（上面证明中半径为 $1/\mathrm{\Delta }$ 的开盘）。 当然，真正的独创性在于找到正确的“捕获区域”。

这种方法可以追溯到 Dobrushin [38] 的工作，甚至可能更早。 近年来，这种方法出现了许多变化和改进，导致了定理 4.1 [74, 19, 21] 的显着扩展以及永久元素的无零区域 [ 7, 8, 11]，对于图同态配分函数[17, 16]，对于Ising和Potts模型的配分函数[67, 69, 75, 13, 22, 35]，对于 Holant 问题 [76] 以及各种其他图多项式 [5, 9, 15, 14, 12, 64] 。

4.2 多元多项式的稳定性

在本小节中，我们简要提及多项式稳定性技术，但不涉及太多细节。 这里的基本思想是，对多项式进行某些运算可以保留某些有用的属性。 如果可以使用这些操作从“基本”多项式构造一些所需的图多项式或配分函数，我们就可以建立图多项式/配分函数的有用属性。 该方法通常对于多元多项式最有效，并且实际上许多图多项式都有多元多项式。

对于我们运行的示例，独立多项式、多元对应项定义如下。 令 $G=(V,E)$ 为一个图，并将每个顶点 $v$ 关联到一个变量 $x_v$。 多元独立多项式定义为

$$Z_G((x_v))=\sum _{\begin{array}{c}S\subseteq V\\ \text{independent}\end{array}}{x}^S,$$

我们使用简写符号 $x^S:={\prod }_{v\in S}{x}_v$。 请注意，如果我们将所有变量设置为等于 $\lambda$，那么我们将恢复原始（单变量）独立多项式。 多变量独立多项式是一个多仿射多项式，这意味着它在每个变量中都是仿射的（也就是说，如果我们固定除一个变量 $x_v$ 以外的所有变量，它就会变成 $x_v$ 中的一个阶数为 $1$ 的多项式）。 不难看出，对于某些常数 $a_S$，任何多参数多项式 $f$（相同变量 ${(x_v)}_{v\in V}$）都可以写成 $f={\sum }_{S\subseteq V}{a}_s{x}^S$。

对于两个多重仿射多项式$P={\sum }_{S\subseteq V}{p}_S{x}^S$和$Q={\sum }_{S\subseteq V}{q}_S{x}^S$，它们的Schur积、$P\ast Q$被定义为多重仿射多项式，其中$x^S$的系数为$p_S\cdot q_S$，即$P\ast Q={\sum }_{S\subseteq V}{p}_S{q}_S{x}^S$。 我们可以使用更简单多项式的 Schur 积来构建多项式 $Z_G$，如下所示。 假设 $H_1$ 和 $H_2$ 是同一顶点集 $V$ 上的图，$G$ 是并集 $H_1$和$H_2$的边缘（即$G$的边缘恰好是$H_1$的边缘以及$H_2$ 然后

$$Z_G=Z_{H_1}\ast Z_{H_2}.$$

这一点很容易理解，因为我们知道 $S$ 是 $G$ 的独立集合，当且仅当 $S$ 是 $H_1$ 和 $H_2$ 的独立集合，并且舒尔积具有相应的性质，即 $x^S$ 的系数是 $Z_{H_1}\ast Z_{H_2}$ 中的 $1$ ，当且仅当它是 $Z_{H_1}$ 和 $Z_{H_2}$ 中的 $1$ 。 例如 $4$-cycle $C_4$ ，其顶点集 $\{1,2,3,4\}$ 和边 $\{1,2\}$、$\{2,3\}$、$\{3,4\}$ 和 $\{4,1\}$ 是两个匹配 $M_1$ 与边 $\{1,2\},\{3,4\}$ 和 $M_2$ 与边 $\{1,3\},\{2,4\}$ 的并集>。 使用乘法性质，我们知道

$$Z_{M_1}=(1+x_1+x_2)(1+x_3+x_4)\text{and}{Z}_{M_2}=(1+x_2+x_3)(1+x_1+x_4)$$

并使用 Schur 产品属性，可以检查

$$Z_{C_4}=Z_{M_1}\ast Z_{M_2}=(1+x_1+x_2+x_3+x_4+x_1{x}_3+x_2{x}_4).$$

Schur 乘积与独立多项式的图并集完美对应，但它保留了任何有用的属性吗？ 将$𝔻$写入$ℂ$中的开单位圆盘，我们说多重仿射多项式$P={\sum }_{S\subseteq V}{p}_S{x}^S$是$𝔻$-稳定的，如果$P({(x_v)}_{v\in V})\ne 0$ 每当$x_v\in 𝔻$时，对于所有$v\in V$。 众所周知（参见[6])，如果$P$和$Q$是$𝔻$稳定的，那么$P\ast Q$。 这对我们来说似乎很有希望，但不幸的是，匹配的独立多项式或实际上单个边缘（我们从中构建所有其他独立多项式）的独立多项式不是$𝔻$稳定的，例如$Z_{M_1}(-\frac{1}{2},-\frac{1}{2},0,0)=0$。 然而，如果所有参数都位于半径 $1/2$ 的开放圆盘中，则匹配的独立多项式不为零。 现在，利用 ${𝒢}_{\mathrm{\Delta }}$ 中的每个图最多是 $\mathrm{\Delta }+1$ 匹配项的并集（Vizing 定理）并应用简单的缩放参数这一事实，人们仍然可以使用 $𝔻$-Schur 产品的稳定性，表明如果所有参数都位于半径小于 $1/2^{\mathrm{\Delta }+1}$ 的圆盘中，则 $Z_G$ 不为零，其中 $G\in {𝒢}_{\mathrm{\Delta }}$。

这是一个比上一小节中的定理 4.1 弱得多的界限，但给出它只是为了说明稳定性的想法。 大约五十年前，浅野[2]率先提出了使用多重仿射多项式和保持零自由度的运算的想法，为著名的李杨定理提供了简短而优雅的证明（另请参阅[6] 使用 Schur 产品进行证明。） 该定理指出，伊辛模型的配分函数（就顶点活动而言）本质上是图中边割的生成函数，在适当的条件下其所有零点都在单位圆上；我们选择不在这里介绍相关背景。 到目前为止，该技术有多种变体，其中一些使用 Grace-Szëgo-Walsh 定理，并且它们已应用于多个模型和图多项式的配分函数 [80, 80, 88, 54, 54, 20]。

4.3聚合物法

我们在上一小节中介绍了多元独立多项式来说明多项式稳定性的思想。 事实证明，许多其他图多项式和配分函数可以表示为特定类型的多元独立多项式的评估。 因此，人们对理解和证明保证此类多元独立多项式的零自由度的条件产生了很大的兴趣。 首先将配分函数/图多项式重写为多元独立多项式的评估，然后检查已知文献中的条件以保证后者的评估不为零，这种想法是源自统计物理学的强大技术。 在那里，多元独立多项式有时称为聚合物模型的配分函数，我们描述的技术有时称为聚合物方法。

我们将给出一个将这个想法应用于色多项式的例子，色多项式是一个用于计算图形正确着色的图形多项式，我们将很快介绍它。 我们草拟了 Férnandez 和 Procacci [44] 以及 Jackson、Procacci 和 Sokal [59] 关于色多项式零自由度结果的证明。 在本小节的末尾，我们列出了基于该技术的一些最新结果，并指出了如何直接使用该技术的变体来设计有效的算法来近似图多项式，而无需使用插值方法。

4.3.1 色多项式

对于图形 $G=(V,E)$ 和整数 $q$,$G$ 的正确 $q$ 着色是 $q$ 颜色的分配（通常标记为$1,\mathrm{\dots },q$)到顶点，使得相邻顶点接收不同的颜色。 这尤其意味着分配了某种固定颜色 $i$ 的所有顶点形成一个独立的集合。 函数 ${\chi }_G$ 计算 $G$ 的正确 $q$ 颜色的数量，即对于每个 $q\in \mathbb{N}$、${\chi }_G(q)$ 被定义为$G$ 的正确$q$ 颜色的数量。例如，三角形的固有 $q$ 颜色数为 $q(q-1)(q-2)$，因为在任意排序顶点后，第一个顶点可以接收任何 $q$ 颜色，第二顶点可以接收除第一顶点的颜色之外的任何颜色，第三顶点可以接收除了前两个顶点的颜色（不同的）之外的任何颜色。 更一般地，$K_r$的正确$q$着色的数量，$r$顶点上的完整图是$q(q-1)\mathrm{\cdots }(q-r+1)$，即${\chi }_{K_r}(q)=q(q-1)\mathrm{\cdots }(q-r+1)$ 对于每个 $q\in \mathbb{N}$。 对于$r$顶点上的任何树$T$，对于所有$q\in \mathbb{N}$,${\chi }_T(q)=q{(q-1)}^{r-1}$，因为如果我们以广度优先顺序为顶点着色，那么第一个顶点可以接收任何 $q$ 颜色，而每个后续顶点可以接收除其父顶点之外的任何颜色。 当然，确定 ${\chi }_G(q)$ 通常并不那么容易，因为确定 $G$ 是否有一个正确的 $q$ 着色是 NP 完全的，即 ${\chi }_G(q)$ 是否为正。 尽管如此，正如上面的例子所表明的，${\chi }_G(q)$始终是$q$中的多项式，我们很快就会看到，${\chi }_G$被称为$G$。

色多项式由 Birkhoff 于 1912 年引入，试图证明四色定理。 它有着悠久的历史，并且连同其影响深远的概括图特多项式（参见[40, 43]的全面阐述），从多个角度进行了研究。

现在，由于 Fortuin 和 Kasteleyn，我们为色多项式建立了一个非常有用的公式，称为随机聚类模型（参见 [45])；它有时被用作色多项式的定义。 形式上，图 $G=(V,E)$ 的正确 $q$ 着色是一个函数 $f:V\to \{1,\mathrm{\dots },q\}=:[q]$，使得 $f(u)\ne f(v)$ 每当 $\{u,v\}\in E$ 。 然后我们可以写

$${\chi }_G(q)=\sum _{f:V\to [q]}\prod _{\{u,v\}\in E}{\mathrm{𝟙}}_{f(u)\ne f(v)},$$

其中 ${\mathrm{𝟙}}_{f(u)\ne f(v)}$ 是 $f(u)\ne f(v)$ 的指示函数（因此，当且仅当所有边都正确着色时，产品才是 $1$)。 将 ${\mathrm{𝟙}}_{f(u)\ne f(v)}$ 替换为 $(1-{\mathrm{𝟙}}_{f(u)=f(v))})$ 并展开，我们得到

${\chi }_G(q)={\displaystyle \sum _{f:V\to [q]}}{\displaystyle \prod _{\{u,v\}\in E}}(1-{\mathrm{𝟙}}_{f(u)=f(v))})$ $={\displaystyle \sum _{f:V\to [q]}}{\displaystyle \sum _{F\subseteq E}}{(-1)}^{|F|}{\displaystyle \prod _{\{u,v\}\in F}}{\mathrm{𝟙}}_{f(u)=f(v)}$

$={\displaystyle \sum _{F\subseteq E}}{(-1)}^{|F|}{\displaystyle \sum _{f:V\to [q]}}{\displaystyle \prod _{\{u,v\}\in F}}{\mathrm{𝟙}}_{f(u)=f(v)}.$

最后一个表达式中的内部总和等于 $q^{k(F)}$，其中 $k(F)$ 是图 $(V,F)$ 的组件数量。 原因是，当且仅当 $F$ 的每条边在 $f$ 中都是单色的时，对于分配 $f$，乘积是 $1$，其中意味着 $f$ 必须为 $(V,F)$ 的每个组件分配单一颜色。 正是有 $q^{k(F)}$ 方法可以做到这一点。 因此

$${\chi }_G(q):=\sum _{F\subseteq E}{q}^{k(F)}{(-1)}^{|F|},$$ (5)

因此我们看到 ${\chi }_G$ 确实是一个多项式（尽管有更简单的方法来显示这一点）并且具有次数 $|G|$。

我们的目标是证明色多项式的以下零自由度结果。

Theorem 4.2 ([44, 59]).

令 $G$ 为任意图。 那么${\chi }_G$的所有零点都包含在复平面中以$0$为中心、半径为$6.91\mathrm{\Delta }(G)$的圆盘中。

常数$6.91$很可能可以改进，但尚不清楚最优值可能是多少；进一步讨论请参见[79，脚注4]。 通过泰勒多项式插值方法，定理4.2几乎立即暗示每当$G\in {𝒢}_{\mathrm{\Delta }}$和$|q|\ge 6.92\mathrm{\Delta }$时逼近${\chi }_G(q)$的FPTAS。 诀窍是将插值方法应用于多项式$q^{|V|}{\chi }_G(1/q)$，该多项式在半径$\frac{1}{6.91\mathrm{\Delta }}$ 的圆盘中没有零点。 从组合的角度来看，这意味着 FPTAS 每当 $q>6.91\mathrm{\Delta }$ 时都会计算任何图 $G\in {𝒢}_{\mathrm{\Delta }}$ 的正确 $q$ 颜色的数量。 人们相信，每当 $q>\mathrm{\Delta }$ 时，都会有一个 FPTAS 来计算正确的 $q$ 颜色，这是一个活跃的研究领域。 通过证明不同多项式（Potts 模型的配分函数）的零自由度结果，Liu、Sinclair 和 Srivastava [66] 表明，当 $q\ge 2\mathrm{\Delta }$ 时存在 FPTAS >，这是目前最先进的技术。

现在我们概述定理4.2的证明。 如前所述，我们需要再次使用（多元）独立多项式并为其使用合适的零自由度结果。

4.3.2 色多项式作为多元独立多项式

我们的第一个引理展示了如何将图 $G$ 的色多项式表示为关联图的多元独立多项式的评估。 为此我们需要一些符号。 令 $G=(V,E)$ 为图表。 定义一个新图 $\mathrm{\Gamma }$，其顶点是 $V$ 的子集 $S$，大小至少为 2。 （在聚合物方法的上下文中，这些集合称为聚合物。） 当且仅当$S\cap T\ne \mathrm{\varnothing }$时，其中两个集合$S,T$通过边连接。 请注意，图 $\mathrm{\Gamma }$ 独立于 $G$ 的边。

我们现在将权重与 $\mathrm{\Gamma }$ 的顶点关联起来，如下所示；这些将取决于 $G$ 和 $q$ 的边缘（色多项式中的变量）。 对于$\mathrm{\Gamma }$的每个顶点$S$，即$S\subseteq V$和$|S|\ge 2$，定义

$${\lambda }_S:=\sum _{\begin{array}{c}F\subseteq E(S)\\ \text{connected}\end{array}}{(-1)}^{|F|}{q}^{|S|-1}.$$ (6)

现在，具有（复）顶点权重 ${\lambda }_S$ 的 $\mathrm{\Gamma }$ 多元独立多项式由下式给出

$$Z_{\mathrm{\Gamma }}(({\lambda }_S))=\sum _{\begin{array}{c}I\subseteq V(\mathrm{\Gamma })\\ \text{independent}\end{array}}\prod _{S\in I}{\lambda }_S.$$ (7)

Lemma 4.3。

使用上面的符号我们有

$$q^{|V|}{\chi }_G(1/q)=Z_{\mathrm{\Gamma }}(({\lambda }_S)).$$

证明。

我们首先使用 (5) 扩展左侧

$q^{|V|}{\chi }_G(1/q)$ $={\displaystyle \sum _{F\subseteq E}}{(-1)}^{|F|}{q}^{|V|-k(F)}={\displaystyle \sum _{F\subseteq E}}{\displaystyle \prod _{C\text{component}ofF}}{(-1)}^{|C|}{q}^{|V(C)|-1}.$

接下来，我们将 $F\subseteq E$ 上的总和分解为 $F$ 的组件结构，如下所示。 我们对所有具有 $k$ 与顶点集 $S_1,\mathrm{\dots },S_k$ 连接的组件的 $F$ 求和，然后对 $S_1,\mathrm{\dots },S_k$ 的所有可能选择求和$k$ 的所有可能选择。事实上，我们可以忽略由单个顶点（无边）组成的组件，因为它们对上述乘积贡献了 $1$ 因子。 这样（交换和与积后）我们得到

$$q^{|V|}{\chi }_G(1/q)=\sum _{k\ge 0}\sum _{\begin{array}{c}{S}_1,\mathrm{\dots },S_k\subseteq V\\ S_i\cap S_j=\mathrm{\varnothing }\text{for}i\ne j\\ |S_i|\ge 2\end{array}}\prod _{i=1}^k\sum _{\begin{array}{c}{F}_i\subseteq E(S_i)\\ (S_i,F_i)\text{connected}\end{array}}{(-1)}^{|F_i|}{q}^{|S_i|-1}.$$

通过构造任何对这个总和有贡献的集合$\{S_1,\mathrm{\dots },S_k\}$的集合，在图$\mathrm{\Gamma }$中形成大小$k$的独立集合。 权重被精确构建，以便最后一个表达式为 $Z_{\mathrm{\Gamma }}(({\lambda }_S))$，如所需。 ∎

4.3.3 零自由条件及其验证

在这里，我们提出了 Biascot、Férnandez 和 Procacci [25] 的结果，该结果提供了有用的条件，保证我们的多元独立多项式（对于 $\mathrm{\Gamma }$ 类型的图）不会计算为零。 然后我们将根据我们的情况验证这些条件。 让 $G=(V,E)$ 和 $\mathrm{\Gamma }$ 与之前一样。

Theorem 4.4 ([25]).

对于任何复数${({\lambda }_S)}_{S\in V(\mathrm{\Gamma })}$和任何$a>1$，如果对于每个$v\in V$，它成立

$$\sum _{\begin{array}{c}S\mid v\in S\\ |S|\ge 2\end{array}}|{\lambda }_S|a^{|S|}\le a-1,$$ (8)

然后$Z_{\mathrm{\Gamma }}(({\lambda }_S))\ne 0$。

该定理可以按照与定理4.1的证明相同的思路来证明。 请参阅[25，命题 3.1]，了解这些线索的证明以及如何将此条件与其他类似条件（包括 Kotécky-Preis 条件 [63] 和 Dobrushin 条件）进行比较的讨论条件[38]。

为了验证定理 4.4 中的条件，我们需要对 (6) 中给出的权重 ${\lambda }_S$ 进行限制。 我们朝这个方向迈出的第一步是去掉 (6) 中的“交替符号”。 例如，可以使用 Tutte 多项式的众所周知的属性来证明下面的引理；参见例如[43] 了解这些属性，请参阅 [73, 85] 了解直接证明。

Lemma 4.5。

令$H$为连通图，并用$\tau (H)$表示$H$中生成树的数量。然后

$$\left|\sum _{\begin{array}{c}F\subseteq E(H)\\ (V(H),F)\text{connected}\end{array}}{(-1)}^{|F|}\right|\le \tau (H).$$

对于图$G=(V,E)$、顶点$v\in V$和变量$x$，我们定义树生成函数：

$$T_{G,v}(x):=\sum _{\begin{array}{c}T\subseteq E(G)\\ (V(T),T)\text{is a tree,}v\in V(T)\end{array}}{x}^{|T|}.$$

我们现在可以根据树生成函数绑定 ${\sum }_{S\mid v\in S,|S|\ge 2}|{\lambda }_S|a^{|S|}$ ，如下所示：

${\displaystyle \sum _{S\mid v\in S,|S|\ge 2}}|{\lambda }_S|a^{|S|}$ $={\displaystyle \sum _{S\mid v\in S,|S|\ge 2}}\left|{\displaystyle \sum _{\begin{array}{c}F\subseteq E(S)\\ \text{connected}\end{array}}}{(-1)}^{|F|}{q}^{|S|-1}\right|a^{|S|}$

$\le {\displaystyle \sum _{S\mid v\in S,|S|\ge 2}}\left|{\displaystyle \sum _{\begin{array}{c}F\subseteq E(S)\\ \text{connected}\end{array}}}{(-1)}^{|F|}\right|{|q|}^{|S|-1}{a}^{|S|}$

$\le {\displaystyle \sum _{S\mid v\in S,|S|\ge 2}}\tau (G[S]){|q|}^{|S|-1}{a}^{|S|}$

$=a{T}_{G,v}(a|q|)-a.$ (9)

下一个引理展示了如何绑定树生成函数。 我们给出的证明比[59]中给出的证明稍短，并且据我们所知是新的。

Lemma 4.6 ([58]).

令$G=(V,E)$为最大次数至多$\mathrm{\Delta }\ge 1$的图，并令$v\in V$。 修复任何 $\alpha >1$。 然后

$$T_{G,v}\left(\frac{\ln \alpha }{\alpha \mathrm{\Delta }}\right)\le \alpha .$$

证明。

证明是通过对 $G$ 的顶点数进行归纳来得出的。如果$|V|=1$，则该陈述显然是正确的。 接下来假设$|V|\ge 2$。 给定一棵树 $T$，使得 $v\in V(T)$ 令 $S$ 为 $V(T)$ 中 $v$ 的邻居集合。 从 $T$ 中删除 $v$ 后，树分解为 $|S|$ 树的不相交并集，每个树都包含来自 $S$ 的唯一顶点。因此，写$c=\frac{\ln \alpha }{\alpha \mathrm{\Delta }}$，我们有

$$T_{G,v}(c)\le \sum _{S\subseteq N_G(v)}{c}^{|S|}\prod _{s\in S}{T}_{G-v,s}(c),$$

通过归纳法，其边界为

$$\sum _{S\subseteq N_G(V)}{(c\alpha )}^{|S|}\le {(1+(\ln \alpha )/\mathrm{\Delta })}^{\mathrm{\Delta }}\le e^{\ln \alpha }=\alpha .$$

至此证明完毕。 ∎

现在我们结合所有的成分来完成定理4.2的证明。 修复$\mathrm{\Delta }\ge 2$。 要确定 $a>1$，请定义 $\alpha =\alpha (a)=2-1/a$。 那么如果

$$|q|\le \frac{\ln \alpha }{a\alpha \mathrm{\Delta }}=\frac{\ln (2-1/a)}{(2a-1)\mathrm{\Delta }},$$

对于任何最大次数最多为$\mathrm{\Delta }$的图，我们有${\chi }_G(1/q)\ne 0$。 事实上，对于 $q\ne 0$ 这样的值，我们有 $|aq|\le \frac{\ln \alpha }{\alpha \mathrm{\Delta }}$，因此通过 (9) 和前面的引理

$$\sum _{S\mid v\in S,|S|\ge 2}|{\lambda }_S|a^{|S|}\le a(T_{G,v}(a|q|)-1)\le a(\alpha -1)=a(1-1/a)=a-1,$$

因此根据定理4.4和引理4.3我们有${\chi }_G(1/q)\ne 0$。 换句话说，如果 $|q|\ge \mathrm{\Delta }\frac{2a-1}{\ln (2-1/a)}$ 我们就有 ${\chi }_G(q)\ne 0$。 可以确定

其中最小值在 $a\cong 1.588$ 处达到。 定理4.2的证明草图就完成了。

4.3.4 配方以及与集群扩展的关系

我们证明定理 4.2 所采取的步骤提出了使用聚合物方法证明不存在零的“秘诀”：

• 将图多项式表示为关联图的多元独立多项式的评估。

• 使用定理 4.4 中的条件（或其他条件）来保证评估不为零。

• 使用组合参数验证这些条件。

这个“秘诀”的大多数组合应用都包括色多项式的各种扩展和变体。 有关此方向的一些示例，请参阅 [85, 44, 39, 60, 59, 41, 36, 35]。

从统计物理学的角度来看，定理4.2和定理4.1都是关于所谓的高温模型的陈述（在定理4.1的情况下，高温度意味着独立多项式的$\lambda$的小值）。 令人惊讶的是，对于某些受限的图族，上述“配方”有时也可以在低温下使用（例如，统计物理学中的[28, 46])。 例如，它已与插值方法结合使用，设计了高效的逼近算法，以逼近整数格${\mathbb{Z}}^d$的某些子图上的大$\lambda$独立多项式。 57]，而且也适用于二部扩展图[61]。 事实上，[61]稍微修改了[57]的方法。 这个想法是使用定理4.4中的条件来显示簇展开的绝对收敛，这是$Z_{\mathrm{\Gamma }}(({\lambda }_S))$对数的形式幂级数，并将余数截断到合适的深度后对其进行限制。 这避免了插值方法的使用，有时可能会导致更快的算法，但除此之外在精神上非常相似。 请参阅[27, 30, 65, 55, 31, 71, 50, 47, 56, 32]，了解受此启发并基于此的一些结果。

5结束语

我们已经展示了零的缺失如何允许人们设计有效的算法来使用巴维诺克插值方法近似计算图多项式的评估。 该方法的关键部分是确定所讨论的图多项式不存在零。 剩下的一些自然问题是：其他近似计数方法如何与零的缺失相关，以及零的存在对于设计有效的近似算法的可能性意味着什么。 在本节中，我们将简要讨论这两个问题，引导感兴趣的读者查阅相关文献。

5.1 缺少零和其他算法方法

正如简介中提到的，还有两种其他（和较旧的）方法用于设计近似算法来计算图多项式的评估：基于马尔可夫链的采样方法和相关衰减方法。 我们不会在这里讨论这些方法的工作原理，但我们会提到这些方法与插值方法的关系，或者更确切地说，它们与零缺失的关系。

最近的研究表明，证明相关性衰减的标准技术可以转变为证明实轴[82, 66]附近不存在零点。 另一方面，一些结果表明零的缺失可用于建立某种形式的相关性衰减[52, 77]。 也许更令人惊讶的是，在 [1, 34] 中表明，如果多项式的多元版本在正实轴附近没有零点，则相关的格劳伯动力学（局部马尔可夫链经常用于近似计数和采样）快速混合。 这些结果表明，虽然没有复零对于插值方法至关重要，但它在其他两种近似计数方法中也发挥着关键作用（尽管是伪装的）。

5.2 零的存在

在本节中，我们讨论零点的存在与近似硬度的关系。 我们将再次专门讨论独立多项式，并在本节末尾给出其他多项式结果的一些参考。 在下文中，我们将看到零的存在意味着逼近独立多项式的难度。

让我们首先陈述所讨论的精确算法问题。 设$\lambda \in \mathbb{Q}[i]$（实部和虚部均为有理数的复数集合）并设$\mathrm{\Delta }\in \mathbb{N}$。 考虑以下计算问题。

• #Hard-CoreNorm($\lambda ,\mathrm{\Delta })$

• 最大次数至多$\mathrm{\Delta }$的图$G$。

• 如果$Z_G(\lambda )\ne 0$，算法必须输出一个有理数$N$，使得$N/1.001\le |Z_G(\lambda )|\le 1.001N$。 如果$Z_G(\lambda )=0$，算法可以输出任何有理数。

很容易证明，用任何其他常量 $C>1$ 替换常量 $1.001$ 不会改变问题的复杂性。

对于计算计数问题，硬度的典型概念是#P-完整性/硬度。 我们不正式介绍这个概念，只是想让大家印象深刻的是，人们并不期望针对 #P 完全计数问题使用多项式时间算法（就像人们不期望针对 NP 完全问题使用多项式时间算法一样） 。 例如，精确计算最大度 $\mathrm{\Delta }$ 的图的独立集的数量的问题对于任何已知都是 #P-complete [78, 86, 42] $\mathrm{\Delta }\ge 3$。

回到问题#Hard-CoreNorm($\lambda ,\mathrm{\Delta }$)，我们定义集合

${𝒫}_{\mathrm{\Delta }}$ $=\{\lambda \in \mathbb{Q}[i]\mid \text{\#Hard-CoreNorm(}\lambda ,\mathrm{\Delta }\text{) is \#P-hard}\},$

${𝒵}_{\mathrm{\Delta }}$ $=\{\lambda \in ℂ\mid Z_G(\lambda )=0\text{for some graph}G\in {𝒢}_{\mathrm{\Delta }}\}.$

在[23]的基础上，[37]中显示集合${𝒵}_{\mathrm{\Delta }}$的闭包包含在集合${𝒫}_{\mathrm{\Delta }}$，意味着任意接近任何零$\lambda \in {𝒵}_{\mathrm{\Delta }}$，都存在一个参数${\lambda }^{\prime }\in \mathbb{Q}[i]$，使得#Hard-CoreNorm(${\lambda }^{\prime },\mathrm{\Delta })$是#P-hard 。 （如果希望近似 $Z_G(\lambda )$ 的参数而不是近似范数，则类似的结果成立。） 回想一下，定理 4.1 给出了包含点 $0$ 的独立多项式的无零区域。 如果可以证明有界度图的独立多项式的最大无零区域是连通的，那么这将导致基本上完全理解在复杂参数下逼近独立多项式的难度。有界度图[37]。 我们注意到，最近表明，在 $\mathrm{\Delta }\to \mathrm{\infty }$ 限制中这是正确的 [18]，但不幸的是，这并没有为我们提供任何有限 $\mathrm{\Delta }$ 的信息> 还没有。

对于某些模型/多项式，例如匹配多项式 [24] 和铁磁 Ising 模型（作为外部场的函数）[29]，我们知道不存在/存在有界度图上的零点恰好对应于近似的容易性/困难性。 对于其他模型，例如 Ising 模型（作为边缘相互作用的函数）[48]，已经建立了部分对应关系。 这提出了一项研究计划，以了解更多模型的这种联系，并从总体上了解这种现象。

插值方法显然是建立快速逼近算法以评估复杂参数下的图多项式的强大技术，但更重要的是，它通常似乎捕捉了参数之间的二分法，其中近似计算容易和困难。