通过图容器近似计算二分图中的独立集

摘要。

通过实现 Sapozhenko 的图容器方法的算法版本，我们给出了用于近似二部图中独立集数量的新算法。 我们的第一个算法适用于$d$-满足弱扩展条件的正则二分图：当$d$是常数，并且图是二分$\mathrm{\Omega }({\log }^{2}d/d)$-扩展器时，我们获得了独立集数量的 FPTAS。 以前，只有满足随机二分图更强的展开条件的图才能知道 $d>5$ 的这种结果。 该算法也适用于加权独立集：对于$d$-常规、二分$\alpha$-扩展器，其中$\alpha >0$固定，我们给出硬-的FPTAS逸度$\lambda =\mathrm{\Omega }(\log d/d^{1/4})$处的核心模型配分函数。 最后，我们提出了一种适用于所有 $d$ - 正则二分图的算法，在 $\exp \left(O\left(n\cdot \frac{{\log }^{3}d}{d}\right)\right)$ 时间内运行，并输出 $(1+o(1))$ - 独立数量的近似值套。

1. 介绍

令$ℐ(G)$表示图$G$的独立集的集合，$i(G)=|ℐ(G)|$表示$G$的独立集的数量。计算$i(G)$是一个#P-hard问题，即使限制在有界度、二部图[47]时也是如此。 即使近似 $i(G)$ （到一个常数甚至次指数因子）仍然是 NP 困难的，即使限制为 $d$ - 具有 $d\ge 6$ 的常规图[53 ]。

直观上，人们可能认为在二分图类上近似 $i(G)$ 的问题会更容易；其一，有一种多项式时间算法可以在二分图中找到最大尺寸的独立集，而相应的问题对于一般图来说是 NP 困难的。 Dyer、Goldberg、Greenhill 和 Jerrum [11] 定义了计数问题 #BIS（二部独立集），并表明一些自然组合计数问题与 #BIS 一样难以近似。 这些问题包括计算稳定匹配、近似铁磁 Potts 模型配分函数 ($q\ge 3$) [24, 15]、计算中 $q$ 着色的数量二分图 ($q\ge 3$)，并用非均匀外场近似铁磁 Ising 模型划分 [23]。

利用二分结构的$i(G)$近似算法的搜索通常分为两类。 第一种方法找到存在多项式时间近似算法的图类。 Liu 和 Lu [41] 给出了第一个这样的算法，为二分图中的独立集的数量提供了 FPTAS，其中一侧的度以 $5$ 为界，而度另一边不受限制。 这个方向的另一项工作包括[31]，其中为有界度、二分的硬核划分函数$Z_G(\lambda )$（计算加权独立集）给出了近似算法扩展图，基于统计物理学的两种工具：聚合物模型和簇扩展（遵循[28])。 这项工作之后进行了多项改进、扩展和概括，包括 [40, 5, 7, 13, 12, 14, 8]。 所有这些算法都是“低温”算法：它们利用了这样一个事实：在具有足够扩展的二分图上，大多数（加权）独立集在二分一侧几乎没有顶点；也就是说，它们接近由一侧的所有子集组成的两个基态之一。 相比之下，Weitz [55]（最大度数最多$5$图中$i(G)$的FPTAS）以及Liu和Lu 的算法[41] 是“高温”算法，利用 $ℐ(G)$（或更普遍的是加权独立集的硬核模型）上小顶点度数均匀分布的相关衰减特性。

第二类二分近似算法是那些适用于所有二分图的算法，其运行时间比已知的一般图要短。 这个方向的主要成果是 Goldberg、Lapinskas 和 Richerby [25] 的算法，它为二分图提供了 $ϵ$ 相对于 $i(G)$ 的近似，在时间 $O(2^{.2372n}{(1/ϵ)}^{O(1)})$ 内运行，击败了同一篇论文中 $O(2^{.268n}{(1/ϵ)}^{O(1)})$ 一般图的最著名运行时间（相比之下，一般图精确计数算法的最著名运行时间是$O(2^{.3022n})$ [21])。

1.1. 主要结果

在本文中，我们使用组合学的工具，即 Sapozhenko 的图容器方法，为二部图中的独立集提供新的近似计数算法。 我们的第一个结果是 $i(G)$ 的 FTPAS，用于弱扩展，$d$-正则二分图，对于常量 $d$。

对于$z>0$，如果$(1-ϵ)\le z/\widehat{z}\le (1+ϵ)$，我们说$\widehat{z}$是$ϵ$相对于$z$的近似值。 完全多项式时间近似方案 (FPTAS) 是一种算法，对于每个 $ϵ>0$ 输出 $ϵ$ 相对于 $i(G)$ 的近似值，并以时间多项式运行 $|V(G)|$ 和 $1/ϵ$。 我们让 ${\mu }_G$ 表示 $ℐ(G)$ 上的均匀分布。 ${\mu }_G$ 的多项式时间采样方案在 $|V(G)|$ 和 $1/ϵ$ 中的时间多项式中运行，并输出分布 $\widehat{\mu }$ 的独立集合 $ϵ$${\mu }_G$的总变化距离。

对于$\alpha >0$，我们说具有二分$X,Y$的$d$-正则二分图$G$是二分$\alpha$-expander 如果对于大小最多为 $|X|/2$ 的每个 $A\subseteq X$ 和 $A\subseteq Y$，我们有

(1) $|N(A)|\ge (1+\alpha )|A|.$

Theorem 1。

存在一个常数 $C_1>0$，因此对于固定且足够大的 $d$ 和 $\alpha =\frac{C_1{\log }^{2}d}{d}$，存在 $i(G)$ 的 FPTAS 和多项式- $d$ 类的 ${\mu }_G$ 的时间采样方案 - 常规二部 $\alpha$ - 扩展图。

先前关于扩展图的结果包括 $i(G)$ 的 FPTAS，在 $G$ 是典型 $d$ 的情况下 - 规则、随机二分图 [31, 40 ，8]。 这些算法利用了随机图满足的非常强的扩展条件：二分区每一侧的大小 $\tilde{O}(n/d)$ 的集合扩展了一个因子 $\tilde{\mathrm{\Omega }}(d)$。

计算独立集概念的一个自然而有力的概括是以硬核模型配分函数（也称为独立多项式）的形式考虑加权独立集

$$Z_G(\lambda )=\sum _{I\in ℐ(G)}{\lambda }^{|I|}.$$

独立集上相应的概率测度（称为硬核模型）由下式给出

$${\mu }_{G,\lambda }(I)=\frac{{\lambda }^{|I|}}{Z_G(\lambda )}.$$

采用 $\lambda =1$ 得到 $i(G)$ 和 ${\mu }_G$。 在之前的工作中，对于比$1$大得多的$\lambda$，获得了有界度、二分$\alpha$-expanders的$Z_G(\lambda )$的FPTAS，特别是 $\lambda \ge K{\mathrm{\Delta }}^{c/\alpha }$ 表示常量 $c,K>1$ [31, 7, 12]。 特别是，在定理1的展开条件下，这些算法需要$\lambda \ge {\mathrm{\Delta }}^{\tilde{\mathrm{\Omega }}(\mathrm{\Delta })}$。

我们的下一个结果采用定理 1 的算法，以适用于远小于 $1$ 的 $\lambda$ 的二分 $\alpha$-扩展器。

Theorem 2.

对于每个 $\alpha >0$ 都存在一个常量 $C_2>0$，因此对于 $d\ge 3$ 和 $\lambda >\frac{C_2\log d}{d^{1/4}}$ 存在一个用于 $Z_G(\lambda )$ 的 FPTAS以及用于 $d$ 类的 ${\mu }_{G,\lambda }$ 的多项式时间采样方案 - 常规二分 $\alpha$ - 扩展器。

事实上，在证明定理 1 和 2 时，我们可以在两种情况之间进行插值，让 $\lambda$ 的下界随着扩展条件变强而缩小。 得到的更一般的条件与Galvin和Tetali[20]给出的格劳伯动力学慢混合条件本质上相同。

我们的下一个结果是所有（不一定扩展）$d$-正则二分图$G$的$i(G)$的近似算法，其中$d$可以要么是恒定的，要么随着图表的大小而增长，$n$。当$d\to \mathrm{\infty }$与$n\to \mathrm{\infty }$相同时，算法以次指数时间运行。 该算法通过分离二分两侧的非扩展集和扩展集的贡献来估计$i(G)$，并使用定理1的扩展算法作为子程序。

Theorem 3.

对于每个 $c>0$，有一个随机算法，给定 $d$-正则、$n$-顶点二分图 $G$ 输出 $n^{-c}$-$i(G)$ 的相对近似值，概率至少为 $2/3$ 并且及时运行

$$\exp \left(O\left(\frac{n{\log }^{3}d}{d}\right)\right).$$

请注意，虽然定理 3 的算法比定理 1 的算法应用更广泛，但算法保证在某些方面较弱（除了运行时间较慢之外）：算法使用随机性，精度仅限于$n$中的多项式小值。而且我们没有为定理3提供相应的采样算法；对于常规图来说，该问题是不可自简化的，因此不存在将近似采样直接简化为计数的问题。 然而，我们可以利用聚合物模型的自还原性来克服定理 1 中的这个问题。

1.2. 背景

独立集的研究在组合学中起着核心作用，因为广泛的问题可以用图（更普遍的是超图）中的独立集来表达。 容器方法是研究独立集的最强大的组合工具之一。 在高层次上，容器方法利用独立集表现出的聚类现象，该现象通常可用于推断给定图或超图中典型独立集的有用结构信息。 对于图，该方法由 Kleitman 和 Winston [35, 36] 于 1980 年代初开发，并由 Sapozhenko 独立发现，他使用该方法枚举正则图中的独立集[49, 50]。 有关背景和示例，请参阅 Samotij [48] 的调查。 直到最近，随着 Saxton 和 Thomason [52] 以及 Balogh、Morris 和 Samotij [4] 开发的超图环境的强大推广，容器方法的全部潜力才变得明显。 。 这些发展使容器方法成为现代组合学中最有影响力的工具之一。

在本文中，我们只需要来自图容器理论的想法，我们的处理与 Sapozhenko [49] 的处理最为密切相关。 Sapozhenko 版本的容器方法的典型应用是他证明 $d$ 维超立方体中独立集合的数量 $Q_d$ 渐近等于 $2\sqrt{e}\cdot 2^{2^{d-1}}$（最初由 Korshunov 和 Sapozhenko [38] 证明的结果）。 另请参见 Galvin 对 Sapozhenko 证明的阐述[18]。

最近，Jenssen 和 Perkins [32] 将 Sapozhenko 的图形容器用于 $Q_d$（以及 Galvin 对加权独立集 [17] 的扩展）以及理论聚合物模型和簇扩展，以推导出$Q_d$中独立集的精确计数估计和详细概率信息。 他们认为的聚合物模型与 Jenssen、Perkins 和 Keevash [31] 用于设计二部扩展图中的近似计数算法的聚合物模型非常相似。 然而，超立方体 $Q_d$ 的扩展器比 [31] 中考虑的图弱得多，排除了直接应用簇扩展方法。 为了克服这个障碍，他们表明容器方法作为证明集群扩展收敛性的工具自然而然地出现了。 这种簇扩展和容器方法的综合现在已经在组合学中的枚举问题中得到了许多应用[30,33,9,3]。

事实上，图容器之前已经在理论计算机科学的许多成果中使用过，包括[20,16,19]。 这些结果使用 Sapozhenko 的技术来证明一种负面的算法结果：用于在具有足够扩展的二分图中采样独立集（或 $q$-着色）的格劳伯动力学（局部马尔可夫链）表现出迟钝的混合；也就是说，混合时间随图的大小呈指数级增长。

在本文中，我们回到算法背景来证明积极的结果，表明容器方法可以通过算法实现来为广泛的二部图设计有效的近似计数和采样算法。 事实上，上面迟钝的混合结果和当前的算法结果之间存在联系：使用聚合物模型和簇扩展作为算法来近似计算二分图中的独立集的关键步骤表明，大多数（加权）独立集可以是由两个聚合物模型之一来解释，该模型捕获完全包含在二分一侧的独立集合的小偏差。 这一步（下面的引理16)相当于证明了一种迟钝的混合结果，与Galvin和Tetali的结果密切相关，他们证明了$d$-正则二分$\alpha$-expanders，用于 $\alpha =\mathrm{\Omega }({\log }^{3}d/d)$ [20，推论 1.3]，类似于定理 1 适用的图类。

虽然定理 1 为比以前的方法更大类别的二部扩展图提供了高效的近似计数和采样算法，但它并没有过多说明 #BIS 的易处理性，除了排除一类难以处理的图之外例子。 在另一个未确定复杂性的突出近似问题中，Unique Games 问题，扩展图 [2, 37, 44] 的高效近似算法后来通过图分解为扩展片段来利用，以找到次指数时间算法所有实例[1]。 这表明寻找更快的算法来近似 #BIS 是一个非常自然的目标。

Question 1。

#BIS 是否有次指数时间近似算法？

定理 3 朝这个方向迈出了一小步，为增长程度的正则图提供了次指数时间算法，使用扩展器算法作为子例程来解释对 $i(G)$ 的贡献扩展集。 非扩展集也是单独考虑的，也使用了图形容器的想法。 人们很容易认为算法图分解结果（例如 [45, 6])可以与 #BIS 的扩展算法结合使用，但我们不清楚如何使用绑定的结果扩展块之间的边数以获得 #BIS 的改进近似算法，因此这仍然是未来研究的一个有趣方向。

1.3. 大纲

在第 2 节中，我们进行了简短的热身，以展示如何使用图形容器中的想法来近似计算图形中的独立集。 在第 3 节中，我们介绍了主要算法结果所需的图形容器结果。 在第 4 节中，我们定义了一个聚合物模型，我们将使用它来近似扩展图中独立集的数量。 在第5节中我们证明定理1。 在第6节中我们证明定理3。 在7节中，我们将3节的图容器结果和4节的聚合物模型扩展到加权独立集的情况来证明定理2。

2. 热身：来自容器的算法

在本节中，我们将演示如何使用图容器的想法来设计更快的算法，以近似计算（不一定是二部）$d$-常规图中的独立集。 本节旨在作为热身，介绍容器方法和计数算法之间的相互作用，对于定理 1、2 和 3。

假设我们有一个算法 $A$，它在时间 $a(n)$ 上运行在一般（不一定是 $d$-常规）图 $G$ 上在 $n$ 顶点上，并输出 $ϵ$ 相对于 $i(G)$ 的近似值。 我们将证明，如果$G$对于$d=\omega (1)$来说是$d$-正则，则可以获得在$a(n/2)\cdot 2^{o(n)}$时间运行的算法。

让$T:=n\ln d/d$。 我们注意到，在整篇论文中，我们让 $\ln$ 表示自然对数，让 $\log$ 表示 ${\log }_2$。 然后我们可以写

其中 是大小小于 的独立集合的数量 $G$,$i_{\ge T}(G)$ 是大小小于 $T$ 的独立集合的数量大小至少为 $T$。人们可以在$\left(\genfrac{}{}{0pt}{}{n}{T}\right)\cdot \mathrm{poly}(n)$时间内通过暴力计算。 为了计算 $i_{\ge T}(G)$，我们使用 Sapozhenko [51] 的微妙想法（另请参阅 [29]、[34])进行更严格的分析。 首先，我们修复图 $G$ 顶点的排序 $\prec$。给定子集$S\subseteq V(G)$和顶点$v\in V(G)$，我们让$d_S(v)$表示$S$中$v$的邻居数量。以下算法采用大小至少为 $T$ 的独立集合 $I$ 作为输入，并返回“证书”$\xi$：

• $t,i\leftarrow 0$、$\xi \leftarrow {(0)}^n$、$V_0\leftarrow V(G)$

• 而$t\le T$做

  • $v\leftarrow {\mathrm{argmax}}_{v\in V_i}{d}_{V_i}(v)$ 使用 $\prec$ 断开关系

  • 如果$v\in I$

    • $t\leftarrow t+1$、$i\leftarrow i+1$、${\xi }_i\leftarrow 1$。

  • 如果$v\notin I$

    • $i\leftarrow i+1$。

• 返回$\xi$

值得注意的是，$\xi$不是$V(G)$的任何子集的指示向量，而是描述移除顶点$v\in I$的步骤的指示向量来自$V_i$。 假设算法运行 $k=k(\xi )$ 步（即 $k$ 是 $i$ 在算法执行过程中的最终值），此时输出为 $\xi$，并让 $V_{\xi }=V_k$. $\xi$ 的一个关键属性是它决定 $V_{\xi }$ 和 $I\cap (V(G)\setminus V_{\xi })$。 因此，我们可以根据它们的证书$\xi$对独立集进行分组并编写

(2) $$i_{\ge T}(G)=\sum _{\begin{array}{c}\xi \in {\{0,1\}}^n,\\ |\xi |=T\end{array}}i(G[V_{\xi }]).$$

此表达式的优点是，可能的证书 $\left(\genfrac{}{}{0pt}{}{n}{T}\right)$ 的数量相对较小，并且如下所示，每个 $V_{\xi }$ 的大小接近于 $n/2$ 。 因此，我们利用容器方法的独立集特征的聚类现象，有效地将我们算法的输入图的大小减半（尽管以失去图的规律性为代价）。

我们现在给出参数来限制每个 $V_{\xi }$ 的大小。 对于任何子集 $S\subseteq V(G)$，让我们将 $e_S$ 表示为导出子图 $G[S]$ 中的边数。 霍夫曼界限的直接扩展（参见例如 [10, 43, 22, 27])，并利用 $d$ 正则图的最小特征值位于至少 $-d$ 给我们

$$2e_S\ge \frac{2d}{n}{|S|}^2-d|S|.$$

所以对于$i\le k$，我们有

(3) $$\underset{v\in V_i}{\max }{d}_{V_i}(v)\ge \frac{2e_{V_i}}{|V_i|}\ge \frac{d}{n}\left(2|V_i|-n\right),$$

所以如果$v\in I$，那么$|V_{i+1}|\le |V_i|\left(1-\frac{2d}{n}\right)+d$，所以在算法结束时，我们有$|V_k|\le \frac{n}{2}+O\left(\frac{n\ln d}{d}\right)$。

因此，如果我们有一种算法 $A$ 可以在 $a(n)=a(n,ϵ)$ 的时间内运行于 $n$ 顶点上的一般图上，该算法可以在 $ϵ$ 的时间内输出 $i(G)$ 的相对近似值，用于 $G$ 顶点上的一般图 $n$ 上，那么可以在 $\left(\genfrac{}{}{0pt}{}{n}{T}\right)\cdot a\left(\frac{n}{2}+O\left(\frac{n\ln d}{d}\right)\right)$ 的时间内计算出 (2) 的 $ϵ$ 相对近似值。 将此与 的强力计算相结合，给出了及时运行的算法

$$\mathrm{poly}(n)\cdot {\left(\genfrac{}{}{0pt}{}{n}{\frac{n\ln d}{d}}\right)}^2\cdot a\left(\frac{n}{2}+O\left(\frac{n\ln d}{d}\right)\right)$$

对于 $n$ 顶点上的 $d$ 正则图 $G$ 输出 $i(G)$ 的 $ϵ$ 相对近似值。 所以特别是，如果$d=\omega (1)$，那么使用Goldberg、Lapinskas和Richerby[25]的算法作为黑盒，我们得到$2^{(0.134+o(1))n}$时间算法用于在 $n$ 顶点上的 $d$ 正则图中近似 $i(G)$。 我们将在下面的 6 节中看到，通过更复杂的想法，只要某些 $a>0$ 的错误 $ϵ=n^{-a}$ （定理 3)。

3. 图容器引理

在本节中，我们将介绍图容器理论的结果，这将是定理 1、2 和 3 算法的关键。 这里的许多想法都源于前面提到的 Sapozhenko [49] 的容器方法。

我们自始至终假设 $G$ 是一个 $d$ - 在 $2n$ 顶点上具有二分 $X,Y$ 的正则二分图，因此 $|X|=|Y|=n$。 对于子集$A\subseteq X$，我们使用$W$来表示$N(A)$。 让我们将 $[A]:=\{u\in X|N(u)\subseteq W\}$ 定义为 $A$ 的 closure。 如果由 $A$ 导出的 $G^2$ 的子图是连通的，我们就调用 $A$ $2$-linked 。 我们说$A$是扩展如果

$$|W|-|[A]|\ge (C_1/2)\frac{{\log }^{2}d}{d}|W|,$$

其中常数 $C_1>0$ 将足够大并稍后选择。 否则，我们说 $A$ 是非扩展。

令$𝒢(v,a,w)$表示$2$链接的扩展集$A$的集合，使得$A\ni v$、$|[A]|=a$和$|W|=w$。 令 ${𝒢}^{\prime }(v,a)$ 为 $2$ 链接的非扩展集 $A\ni v$ 的集合，使得 $A=[A]$ 和 $|A|=a$ 。

备注：观察到，如果$G$是二分$\alpha$-expander（如(1)处定义），则

(4) $$|N(A)|\ge (1+\alpha )|[A]|$$

对于每个$A\subseteq X$或$A\subseteq Y$，使得$|[A]|\le n/2$。 事实上，如果$|[A]|\le n/2$，则$|N(A)|=|N([A])|\ge (1+\alpha )|[A]|$。 由于 $\alpha \le 1$，不等式 (4) 意味着 $|[A]|\le |N(A)|(1-\alpha /2)$，所以

(5) $$|N(A)|-|[A]|\ge (\alpha /2)|N(A)|$$

对于每个$A$，使得$|[A]|\le n/2$。 在下文中，条件 (5) 使用起来稍微方便一些，并激发了我们对扩展集的定义。

我们现在陈述我们的主要技术引理。 第一个限制了扩展集的数量，第二个限制了非扩展集的数量（并给出了枚举它们的算法）。

Lemma 4.

有一个绝对常数 $c_1>0$，这样对于每个 $v,a,w$ 我们有

$$|𝒢(v,a,w)|\le 2^{w-c_1(w-a)}.$$

Lemma 5.

有一个绝对常数 $c_2>0$，这样对于每个 $v,a$，我们有

$$|{𝒢}^{\prime }(v,a)|\le 2^{c_2\frac{a{\log }^{2}d}{d}}.$$

此外，有一个在时间$2^{O\left(\frac{a{\log }^{2}d}{d}\right)}\cdot \mathrm{poly}(n)$运行的算法，输出集合${𝒢}^{\prime }(v,a)$。

回想一下，对于子集 $A\subseteq X$，我们使用 $W$ 来表示 $N(A)$，用 $|[A]|=a$、$|W|=w$ 表示。 设置$t=w-a$。 对于每个$s>0$，让$W_s=\{u\in W|d_{[A]}(u)\ge s\}$。 接下来，我们定义集合 $W$ 的近似概念（这又决定 $[A]$)。

Definition 6。

集合$F\subseteq W$是$A$的基本子集，如果

1. $F轴线W_{d/2}$

2. $N(F)\supseteq [A]$。

下一个引理给出了一个族 $𝒞(v,a,w)\subset 2^Y$，它包含 $𝒢(v,a,w)$ 的每个成员的基本子集。 至关重要的是，近似集 $𝒞(v,a,w)$ 的集合远小于 $𝒢(v,a,w)$。

Lemma 7。

最多有一个 $𝒞(v,a,w)\subset 2^Y$ 大小的族

$$2^{\frac{16w{\log }^{2}d}{d}}$$

这样 $𝒞(v,a,w)$ 包含每个 $2$ 链接集 $A\ni v$ 的基本子集，例如 $|[A]|=a$ 和 $|W|=w$。 此外，有一个在时间$2^{\frac{16w{\log }^{2}d}{d}}\cdot \mathrm{poly}(n)$运行的算法，输出集合$𝒞(v,a,w)$。

我们证明下面的引理7。

Park [46] 的以下引理强化了 Sapozhenko [49] 的结果（该引理也在 [34] 中隐式证明）。

Lemma 8.

存在一个绝对常数$c_3>0$，使得以下内容成立：对于每个$F\subseteq X$，令$𝒢(F,a,w)$为扩展$2$链接的集合设置 $A\subseteq X$，使得 $|[A]|=a$、$|W|=w$ 和 $F$ 是 $A$ 的基本子集。 然后

$$|𝒢(F,a,w)|\le 2^{w-c_3\left(w-a\right)}.$$

有了这些引理，我们现在证明引理4和引理5。

引理4的证明。

首先要注意的是

(6) $𝒢(v,a,w)\subseteq {\displaystyle \bigcup _{F\in 𝒞(v,a,w)}}𝒢(F,a,w)$

所以根据引理 7 和 8，我们有

$|𝒢(v,a,w)|$ $\le {\displaystyle \sum _{F\in 𝒞(v,a,w)}}|𝒢(F,a,w)|$

$\le |𝒞(v,a,w)|\cdot \underset{F\in 𝒞(v,a,w)}{\max }|𝒢(F,a,w)|$

$\le 2^{\frac{16w{\log }^{2}d}{d}}\cdot 2^{w-c_3\left(w-a\right)}$

$\le 2^{w-\left(\frac{c_3}{2}\right)\left(w-a\right)}$

对于最后一个不等式，我们通过扩展集的定义使用 $w-a\ge (C_1/2)\frac{{\log }^{2}d}{d}w$ 并假设 $C_1>64/c_3$。 ∎

引理5的证明。

令 $F$ 为 $A$ 的基本子集，其中 $A$ 是非扩展的。 请注意，$W\setminus F$ 中的每个顶点在 ${[A]}^c$ 中至少有 $d/2$ 个邻居，而 $W$ 和 ${[A]}^c$ 之间最多有 $d(w-a)$ 条边。由此可见

$$(d/2)\cdot |W\setminus F|\le d(w-a)$$

所以

$$|W\setminus F|\le 2(w-a)\le C_1\frac{{\log }^{2}d}{d}w.$$

而且，$W\setminus F\subset N^2(F)$和$N^2(F)\le w{d}^2$，所以最多有

$$\left(\genfrac{}{}{0pt}{}{w{d}^2}{\le C_{1}w({\log }^{2}d)/d}\right)\le 2^{O\left(\frac{a{\log }^{3}d}{d}\right)}$$

$W$ 的选项，每个选项决定一个$[A]$。 令 ${𝒢}^{\prime }(F,a)$ 表示 $A\subset X$ 的集合，使得 $A=[A]$、$v\in A$、$A$ 为 $2$ 链接，非扩展，$F$ 是 $A$ 的基本子集。 那么通过上面的

$$|{𝒢}^{\prime }(F,a)|=2^{O\left(\frac{a{\log }^{3}d}{d}\right)}.$$

此外，我们可以通过列出每个集合 $W$ 来在时间 $2^{O\left(\frac{a{\log }^{3}d}{d}\right)}\mathrm{poly}(n)$ 中生成集合 ${𝒢}^{\prime }(F,a)$，该集合是 $F$ 的并集，其子集为$N^2(F)$的大小至多为$C_{1}w({\log }^{2}d)/d$，生成相应的闭集$[A]$使得$N(A)=W$，并检查其是否满足所需的条件。

现在，根据引理 7，

(7) ${𝒢}^{\prime }(v,a)\subseteq {\displaystyle \bigcup _{w\in [a,a\left(1+C_1\frac{{\log }^{2}d}{d}\right)]}}{\displaystyle \bigcup _{F\in 𝒞(v,a,w)}}{𝒢}^{\prime }(F,a)$

所以

$$|{𝒢}^{\prime }(v,a)|\le \left(C_1\frac{a{\log }^{2}d}{d}\right)\cdot 2^{O\left(\frac{a{\log }^{3}d}{d}\right)}=2^{O\left(\frac{a{\log }^{3}d}{d}\right)}.$$

同样，通过(7)，引理7，以及上面生成${𝒢}^{\prime }(F,a)$的算法，我们可以及时生成${𝒢}^{\prime }(v,a)$ $2^{O\left(\frac{a{\log }^{3}d}{d}\right)}\cdot \mathrm{poly}(n)$。 ∎

我们最初需要一个由 Lovász [42] 和 Stein [54] 提供的覆盖结果。

Theorem 9。

令 $H$ 为顶点集 $P$ 和 $Q$ 上的二部图，其中 $P$ 中每个顶点的度数至少为 $a$,$Q$中每个顶点的度数最多为$b$。 然后存在大小至多为$\frac{|Q|}{a}(1+\ln b)$的子集$Q^{\prime }\subset Q$，使得$P\subseteq N(Q^{\prime })$。

我们记录定理9的以下推论，我们将在引理7的证明中使用它。

Corollary 10。

令$A\subseteq X$ 与$2$ 链接并令$A\ni v$。 然后进行以下操作：

1. 存在一个大小至多为$2\frac{a}{d}\ln d+2\frac{w}{d}$的$2$链接子集$A^{\prime }\subseteq A$，使得$A^{\prime }\ni v$和$N(A^{\prime })$是$A$的基本子集。

2. 存在一个$2$链接的子集$A^{\prime \prime }\subseteq A$，其大小最多为$2\frac{a}{d}\ln d+2\frac{w}{d}+2(w-a)$ 使得 $N(A^{\prime \prime })=W$。

证明。

我们首先证明 (1)。 令 $A_0\subset [A]$ 为包含 $v$ 且具有成对不相交邻域的顶点的最大子集。 显然$|A_0|\le \frac{w}{d}$和$N^2(A_0)\supseteq A$。 定理9保证子集$A_1\subseteq A$的大小最多为$2\frac{a}{d}\ln d$，使得$W_{d/2}\supseteq N(A_1)$。 假设$A_0\cup A_1$不是$2$链接的，那么最多有$\frac{w}{d}$$2$链接的组件。 事实上，这是正确的，因为 $N(A_0\cup A_1)\subseteq W$ 并且每两个链接组件至少覆盖 $W$ 的 $d$ 个顶点。由于 $[A]$ 是 $2$ 链接的，因此可以选择大小最多为 $\frac{w}{d}$ 的子集 $A_2\subseteq [A]$，使得 $A^{\prime }:=A_0\cup A_1\cup A_2$ 是$2$ 链接的。 我们注意到$|A^{\prime }|\le 2\frac{a}{d}\ln d+2\frac{w}{d}$。 为了证明 $N(A^{\prime })$ 是 $A$ 的基本子集，请观察

• $N^2(A^{\prime })\supseteq N^2(A_0)\supseteq [A]$，以及

• $W_{d/2}\subseteq N(A_1)\subseteq N(A^{\prime })$。

我们现在转向 (2)。 请注意，$W\setminus W_{d/2}$ 中的每个顶点在 ${[A]}^c$ 中至少有 $d/2$ 个邻居，而 $W$ 和 ${[A]}^c$ 之间最多有 $d(w-a)$ 条边。由此可见

$$(d/2)\cdot |W\setminus W_{d/2}|\le d(w-a)$$

所以

$$|W\setminus W_{d/2}|\le 2(w-a).$$

令 $A_3\subseteq A$ 为 $W\setminus W_{d/2}$ 的最小覆盖。 我们有 $|A_3|\le |W\setminus W_{d/2}|\le 2(w-a)$,$A_3$ 的每个顶点与 $A_0\subseteq A^{\prime }$ 中某个顶点的距离为 $2$，最大距离为 $A_0$。 因此，$A^{\prime \prime }=A^{\prime }\cup A_3$是$2$链接的，$|A^{\prime \prime }|\le 2(w-a)+|A^{\prime }|$和$N(A^{\prime \prime })\supseteq W$，完成了证明。 ∎

最后我们证明引理7。 我们提出的证明与[49]中的证明不同且更简单，后者的证明适用于数量上较弱的扩展概念，但反过来，要求没有两个顶点共享许多共同的邻居。

引理7的证明。

令 $A\ni v$ 为 $2$ 链接的子集，如引理的陈述中所示。 根据推论 10，存在一个 $2$ 链接的子集 $A^{\prime }\subset A$，其大小最多为 $4\frac{w}{d}\ln d$，使得 $v\ni A^{\prime }$ 和 $N(A^{\prime })$ 是 $A$ 的基本子集。 鉴于此，我们令 $ℬ(v,a,w)$ 为 $A$ 的所有 $2$ 链接子集的集合，其中包含 $v$，大小为大多数 $4\frac{w}{d}\ln d$ 并让

$$𝒞(v,a,w)=\{N(A):A\in ℬ(v,a,w)\}.$$

它仍然是 $𝒞(v,a,w)$ 大小的上限，并描述输出该集合的算法。 请注意，$|ℬ(v,a,w)|=|𝒞(v,a,w)|$和$|ℬ(v,a,w)|$最多是$G^2$中包含$v$作为根的树的数量，最多为$4\frac{w\log d}{d}$ 顶点。 请注意，$G^2$ 中的最大次数最多为$d(d-1)$。 因此可以使用以下过程枚举 $ℬ(v,a,w)$：

1. 假设图中每个顶点的邻居都有一个排序$G^2$。 让我们使用 $v_i$ 来表示顶点 $v$ 的第 $i$ 个邻居。让我们也表示$v_0=v$。

2. 生成列表$S\in {\{0,\mathrm{\dots },d(d-1)\}}^{8\frac{w\ln d}{d}}$。

3. 考虑集合 $T_S=\{v^{(0)},\mathrm{\dots },v^{(s)}\}$，其中 $v^{(0)}=v$ 和 $v^{(i)}=v_{S_i}^{(i-1)}$。

4. 如果$|T_S|\le 4\frac{w\ln d}{d}$，则输出$T_S$。

考虑 $G^2$ 中具有根 $v$ 和 $s\le 4\frac{w\ln d}{d}$ 节点的任何树。 列表$S$中至少有一个选择会导致上述过程输出该树的顶点，即，如果$(S_1,\mathrm{\dots },S_{2s})$是DFS遍历顺序并且$S_i=0$ 为 $i\ge 2s$。

对于每个列表 $S$，该过程需要 $\mathrm{poly}(n)$ 时间，可能的列表数量为 ${(d(d-1)+1)}^{8\frac{w}{d}\ln d}\le 2^{\frac{16w{\log }^{2}d}{d}}$。 因此，有一个在时间$2^{\frac{16w{\log }^{2}d}{d}}\cdot \mathrm{poly}(n)$运行的算法，输出集合$𝒞(v,a,w)$。 ∎

4. 聚合物模型

在本节中，我们将介绍 Jenssen、Keevash 和 Perkins [31] 使用的聚合物模型的变体，以获得二部展开图的近似算法。 聚合物模型起源于统计物理学（例如[26, 39])，作为研究晶格自旋模型的一种手段。 最近，它们被用来设计低温自旋模型的算法[28]。

修复一个 $d$-正则二分图 $G$，其中二分图 $(X,Y)$ 的大小分别为 $n$。 $G$的聚合物是$2$连接的、$X$的扩展子集。 回想一下，在上一节中，集合 $A\subseteq X$ 正在扩展，如果

(8) $|N(A)|-|[A]|\ge (C_1/2){\displaystyle \frac{|N(A)|{\log }^{2}d}{d}}$

其中 $C_1$ 是定理 1 中的常数。 让$𝒫(G)$表示$G$的所有聚合物的集合。聚合物$\gamma$的重量由$2^{-|N(\gamma )|}=:w_{\gamma }$给出。 如果$\gamma \cup {\gamma }^{\prime }$不是$2$连接的，我们称两种聚合物$\gamma$和${\gamma }^{\prime }$兼容，并且不兼容，否则，我们写$\gamma \nsim {\gamma }^{\prime }$。 让$\mathrm{\Omega }(G)$表示相互兼容的聚合物的所有子集的集合（包括空集）。 聚合物模型配分函数为

(9) $${\mathrm{\Xi }}_G^X:=\sum _{\mathrm{\Lambda }\in \mathrm{\Omega }(G)}\prod _{\gamma \in \mathrm{\Lambda }}{w}_{\gamma },$$

以及 $\mathrm{\Omega }(G)$ 上的相关吉布斯分布 ${\nu }_G^X$ 定义为

$${\nu }_G^X(\mathrm{\Lambda })=\frac{{\prod }_{\gamma \in \mathrm{\Lambda }}{w}_{\gamma }}{{\mathrm{\Xi }}_G^X}\text{for}\mathrm{\Lambda }\in \mathrm{\Omega }(G).$$

当聚合物模型的权重足够小时，人们可以希望通过微扰技术，特别是簇扩展来理解配分函数和吉布斯分布。

对于聚合物元组$\mathrm{\Gamma }$,不相容图、$H(\mathrm{\Gamma })$是具有顶点集$\mathrm{\Gamma }$和任意之间的边的图。两种不相容的聚合物。 簇 $\mathrm{\Gamma }$是聚合物的有序元组，因此$H(\mathrm{\Gamma })$是连接的。 让我们用$𝒞(G)$来表示$G$的所有簇的集合。 ${\mathrm{\Xi }}_G^X$的簇展开是正式的级数展开

(10) $$\ln {\mathrm{\Xi }}_G^X=\sum _{\mathrm{\Gamma }\in 𝒞(G)}\varphi (H(\mathrm{\Gamma }))\prod _{\gamma \in \mathrm{\Gamma }}{w}_{\gamma },$$

其中 $\varphi$ 是由以下定义的 Ursell 函数

$$\varphi (H)=\sum _{\begin{array}{c}{E}^{\prime }\subseteq E(H)\\ (V(H),E^{\prime })\text{connected}\end{array}}{(-1)}^{|E^{\prime }|}.$$

由于$𝒞(G)$是无限集合，因此(10)中的级数是无限和。 在我们的应用程序中，在建立足够快的收敛速度后，我们将使用截断的和。 对于这些收敛边界（如 [28, 31])，我们使用 Koteckỳ–Preiss 条件 [39] 的特殊情况。

Theorem 11 ([39]).

修复函数 $f:𝒫(G)\to [0,\mathrm{\infty })$ 和 $g:𝒫(G)\to [0,\mathrm{\infty })$。 假设对于每个 $\gamma \in 𝒫(G)$，我们有

(11) $$\sum _{{\gamma }^{\prime }\sim ̸\gamma }{w}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}\le f(\gamma ).$$

那么簇扩张绝对收敛。 此外，对于每个顶点$v$，

(12) $$\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}\left|\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{w}_{\gamma }\right|e^{g(\mathrm{\Gamma })}\le 1.$$

我们将用它来获取有关聚合物模型的一些相关结构信息。 对于聚合物 $\gamma$，定义改性聚合物重量 ${\tilde{w}}_{\gamma }=2^{-|N(\gamma )|}\cdot 2^{\frac{|\gamma |{\log }^{2}d}{d}}$ 并让

(13) ${\tilde{\mathrm{\Xi }}}_G^X={\displaystyle \sum _{\mathrm{\Lambda }\in \mathrm{\Omega }(G)}}{\displaystyle \prod _{\gamma \in \mathrm{\Lambda }}}{\tilde{w}}_{\gamma }$

是修正的聚合物模型配分函数。 我们首先证明该聚合物模型满足 Koteckỳ-Preiss 条件，可以适当选择函数 $f$ 和 $g$。

Lemma 12.

考虑修改后的聚合物模型，其中聚合物是所有正在膨胀的 $2$ 连接子集 $A\subseteq X$，并且聚合物 $\gamma$ 的重量由下式给出

$${\tilde{w}}_{\gamma }=2^{-|N(\gamma )|}\cdot 2^{\frac{|\gamma |{\log }^{2}d}{d}}.$$

让$f(\gamma )=\ln 2\cdot \frac{|\gamma |{\log }^{2}d}{d}$和$g(\gamma )=2\ln 2\cdot \frac{|N(\gamma )|{\log }^{2}d}{d}$。 那么对于足够大的$d$，每个聚合物$\gamma$都满足(11)。 该结论也适用于具有权重 $w_{\gamma }$ 和相同选择的函数 $f(\cdot ),g(\cdot )$ 的原始聚合物模型。

引理12的证明。

它足以证明自${\tilde{w}}_{\gamma }>w_{\gamma }$以来对于所有$\gamma$的修改聚合物模型的主张。

回想一下，从引理4证明$c_1\ge c_3/2\ge 64/C_1$。 我们评估

${\displaystyle \sum _{{\gamma }^{\prime }\sim ̸\gamma }}{\tilde{w}}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$ $\le {\displaystyle \sum _{v\in \gamma }}{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{\tilde{w}}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{2}^{-|N({\gamma }^{\prime })|}{e}^{2f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}\left({\displaystyle \sum _{t\ge (C_1/2)\frac{w{\log }^{2}d}{d}}}|𝒢(v,w-t,w)|2^{-w}\cdot e^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}\right)$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}{e}^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}\left({\displaystyle \sum _{t\ge (C_1/2)\frac{w{\log }^{2}d}{d}}}|𝒢(v,w-t,w)|2^{-w}\right)$

$\le |\gamma |{\displaystyle \sum _{w\ge d}}{e}^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}\left({\displaystyle \sum _{t\ge (C_1/2)\frac{w{\log }^{2}d}{d}}}{2}^{-c_1\cdot t}\right)$

$\le d|\gamma |{\displaystyle \sum _{w\ge d}}{e}^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}{2}^{-8\frac{w{\log }^{2}d}{d}}$

$\le d^2|\gamma |2^{-4{\log }^{2}d}$

$\ll \ln 2\cdot {\displaystyle \frac{|\gamma |{\log }^{2}d}{d}}=f(\gamma ).\mathit{∎}$

因此，定理 11 告诉我们

(14) ${\displaystyle \sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}}\left|\varphi (\mathrm{\Gamma }){\displaystyle \prod _{\gamma \in \mathrm{\Gamma }}}{w}_{\gamma }\right|e^{g(\gamma )}\le 1,$

与 ${\tilde{w}}_{\gamma }$ 替换 $w_{\gamma }$ 相同。

现在定义截断簇扩展的指数

(15) $${\mathrm{\Xi }}_G^X(\mathrm{\ell }):=\exp \left(\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \Vert \mathrm{\Gamma }\Vert \le \mathrm{\ell }\end{array}}\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{w}_{\gamma }\right),$$

其中$\Vert \mathrm{\Gamma }\Vert :={\sum }_{\gamma \in \mathrm{\Gamma }}|\gamma |$。 以下引理将 ${\mathrm{\Xi }}_G^X$ 近似为 ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$ 时的误差限制。

Lemma 13.

对于每个$\mathrm{\ell }\ge 1$，我们有，

(16) $$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell })\right|\le n\cdot 2^{-2\frac{\mathrm{\ell }{\log }^{2}d}{d}}.$$

特别是，如果$\mathrm{\ell }\ge \frac{d}{2{\log }^{2}d}\log (n/ϵ)$，那么

$$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell })\right|\le ϵ.$$

证明。

首先回想一下，对于集群 $\mathrm{\Gamma }$，

$$g(\mathrm{\Gamma })=\sum _{\gamma \in \mathrm{\Gamma }}g(\gamma )=2\ln 2\frac{{\log }^{2}d}{d}\sum _{\gamma \in \mathrm{\Gamma }}|N(\gamma )|\ge 2\ln 2\frac{{\log }^{2}d}{d}\Vert \mathrm{\Gamma }\Vert .$$

由(14)得出

$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell })\right|$ $=\left|{\displaystyle \sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \Vert \mathrm{\Gamma }\Vert >\mathrm{\ell }\end{array}}}\varphi (\mathrm{\Gamma }){\displaystyle \prod _{\gamma \in \mathrm{\Gamma }}}{w}_{\gamma }\right|$

$\le {\displaystyle \sum _v}{\displaystyle \sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\\ \Vert \mathrm{\Gamma }\Vert >\mathrm{\ell }\end{array}}}\left|\varphi (\mathrm{\Gamma }){\displaystyle \prod _{\gamma \in \mathrm{\Gamma }}}{w}_{\gamma }\right|$

$\le n{e}^{-2\ln 2\frac{\mathrm{\ell }{\log }^{2}d}{d}}$

$=n\cdot 2^{-2\frac{\mathrm{\ell }{\log }^{2}d}{d}}.\mathit{∎}$

让 $\Vert 𝚲\Vert ={\sum }_{\gamma \in 𝚲}|\gamma |$ 为 $𝚲\sim {\nu }_G^X$。 我们有以下 $\Vert 𝚲\Vert$ 的大偏差结果，遵循 [32，引理 16]。

Lemma 14.

对于任何$\delta \in (0,1)$，都有一个$d_0=d_0(\delta )$，例如$d\ge d_0$，我们有

$$\mathbb{P}(\Vert 𝚲\Vert \ge \delta n)\le 2^{-\left(\frac{\delta n{\log }^{2}d}{2d}\right)}.$$

证明。

通过在 (13) 处定义 ${\tilde{\mathrm{\Xi }}}_G^X$，我们可以得到 $\zeta =\frac{\ln 2{\log }^{2}d}{d}$ 的 $\ln {\tilde{\mathrm{\Xi }}}_G^X-\ln {\mathrm{\Xi }}_G^X=\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }$。 对所有 $v$ 求和 (14)，并利用 $|N(\gamma )|\ge d$ 对于每个 $\gamma$ 的事实，我们得到

(17) $$\ln {\tilde{\mathrm{\Xi }}}_G^X\le \sum _v\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}\left|\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{\tilde{w}}_{\gamma }\right|\le n\cdot 2^{-2{\log }^{2}d}.$$

因此，我们有

$\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }\le \ln {\tilde{\mathrm{\Xi }}}_G^X\le n\cdot 2^{-2{\log }^{2}d},$

因此根据马尔可夫不等式我们有

$\mathbb{P}(\Vert 𝚲\Vert \ge \delta n)$ $\le \exp \left(-\zeta \delta n+n\cdot 2^{-2{\log }^{2}d}\right)$

$\le 2^{-\frac{\delta n{\log }^{2}d}{2d}},$

其中最后一个不等式如下，因为 $(1/2)\ln 2\ge {(\delta {\log }^{2}d)}^{-1}\cdot d\cdot 2^{-2{\log }^{2}d}$ 对于足够大的 $d$。 ∎

聚合物模型的近似计数和采样

在这里，我们将使用 [31] 中的算法来近似 ${\mathrm{\Xi }}_G^X$ 并近似从 ${\nu }_G^X$ 中采样。

Lemma 15.

然后，${\mathrm{\Xi }}_G^X$ 的 FPTAS 在时间 ${(n/ϵ)}^{O(d)}$ 中运行。 此外，对于每个$ϵ>0$，都有一个在时间${(n/ϵ)}^{O(d)}$中运行的随机算法，输出具有分布${\nu }_{\text{alg}}^X$的配置$\mathrm{\Lambda }\in \mathrm{\Omega }(G)$，以便。

为了理解上述算法，我们简要描述${\mathrm{\Xi }}_G^X$的FPTAS。 使用引理 13，足以计算 ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$（如 (15) 中所定义），其中 $\mathrm{\ell }=\lceil \frac{d}{2{\log }^{2}d}\log (n/ϵ)\rceil$。

这可以通过以下方式完成

1. 列出大小最大为 $\mathrm{\ell }$ 的所有集群 $\mathrm{\Gamma }$，

2. 计算$\varphi (\mathrm{\Gamma })$，

3. 计算 ${\prod }_{\gamma \in \mathrm{\Gamma }}{w}_{\gamma }$，以及

4. 通过对截断簇扩展求幂来评估 ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$。

为了从${\nu }_G^X$中进行近似采样，我们求助于抽象聚合物模型的自还原性，请参见[28，定理10]。

Remark 1。

在第6节中定理3的证明中，我们实际上需要近似$G$各个子图的配分函数。这些子图 $H\subseteq G$ 均具有以下形式：$H$ 是在顶点集 $X^{\prime }\cup Y^{\prime }$ 上针对某些 $X^{\prime }\subseteq X$、$Y^{\prime }\subseteq Y$ 使得$N(X^{\prime })\subseteq Y^{\prime }$ 对于这样的子图，我们将 $H$ 的聚合物定义为 $X^{\prime }$ 的扩展 $2$ 链接子集，并定义配分函数 ${\mathrm{\Xi }}_H^{X^{\prime }}$ 以显而易见的方式。 我们注意到，$H$ 的聚合物是 $G$ 的聚合物的子集。特别是，由于 $G$ 上的聚合物模型满足定理 11 的假设，因此 $H$ 上的聚合物模型也满足定理 11 的假设，且函数 $f$ 和 $g$ 相同。特别是，定理 13、14 和 15 也适用于 $H$ 上的聚合物模型。

5. 扩展图的算法：定理 1 的证明

在本节中，我们证明定理1。 我们自始至终假设 $G$ 是一个 $d$ - 正则二分 $\alpha$ - 带有 $\alpha =C_1\frac{\log d}{d}$ 的扩展器。 我们让 $X,Y$ 表示 $G$ 的顶点类，并让 $n=|X|=|Y|$ 表示。 我们注意到，通过 (5)，我们对每个 $A\subset X$ 或 $A\subset Y$ 都有 $|N(A)|-|A||\ge (C_1/2)\frac{|N(A)|{\log }^{2}d}{d}$，这样 $|[A]|\le n/2$，即每个这样的集合 $A$ 正在扩展。

首先，我们证明 $i(G)$ 可以通过聚合物模型配分函数 ${\mathrm{\Xi }}_G^X$ 和 ${\mathrm{\Xi }}_G^Y$ 的线性组合来很好地近似（如 (9))。 然后我们可以使用4部分的算法来近似${\mathrm{\Xi }}_G^X$和${\mathrm{\Xi }}_G^Y$。 回顾一下，我们让 $ℐ=ℐ(G)$ 表示 $G$ 的独立集合。对于抽样算法，我们将证明 ${\mu }_G$ 可以用从聚合物度量 ${\nu }_G^X$、${\nu }_G^Y$ 派生的 $ℐ$ 上的概率分布的混合物来近似。 我们让 ${\widehat{\nu }}_G^X$ 表示 $ℐ$ 上的概率分布，定义如下：

1. 从测量 ${\nu }_G^X$ 中对一系列相容聚合物 $\mathrm{\Lambda }$ 进行采样。

2. 设置$I=J\cup {\bigcup }_{\gamma \in \mathrm{\Lambda }}\gamma$，其中$J$是$Y\backslash {\bigcup }_{\gamma \in \mathrm{\Lambda }}N(\gamma )$的均匀随机子集。

我们类似地定义 ${\widehat{\nu }}_G^Y$ 并定义混合物

$${\widehat{\mu }}_G=\frac{{\mathrm{\Xi }}_G^X}{{\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y}{\widehat{\nu }}_G^X+\frac{{\mathrm{\Xi }}_G^Y}{{\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y}{\widehat{\nu }}_G^Y.$$

Lemma 16.

对于足够大的 $n$，

$$2^n\cdot \left({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y\right)$$

是 $i(G)$ 的 $ϵ$ 相对近似值，其中 $ϵ=2^{-\frac{n{\log }^{2}d}{60d}}.$ 而且，

$${\Vert {\mu }_G-{\widehat{\mu }}_G\Vert }_{TV}\le 2ϵ.$$

证明。

让我们定义

$${ℐ}_X:=\{I\in ℐ|\text{every}2\text{-linked component of}I\cap X\text{is expanding}\}$$

即所有$I$的集合使得${\nu }_G^X(I)>0$。 我们注意到，由于 $G$ 的独立数是 $n$，因此对于每个 $I\in ℐ$，我们都有这样的独立数：

$$\min (|[I\cap X]|,|[I\cap Y]|)\le n/2.$$

特别是，$I\cap X$ 或 $I\cap Y$ 的每个组件都在扩展。 因此 $ℐ={ℐ}_X\cup {ℐ}_Y$ 等等

(18) $i(G)=|{ℐ}_X|+|{ℐ}_Y|-|{ℐ}_X\cap {ℐ}_Y|.$

注意

(19) $${ℐ}_X=2^n\cdot {\mathrm{\Xi }}_G^X$$

此外，统一选择的$I\in {ℐ}_X$的$I\cap X$的$2$链接组件的集合精确地相应于${\nu }_G^X$分布。 限制 ${ℐ}_X\cap {ℐ}_Y$ 的大小就足够了。

令${ℐ}_X^{\delta }=\{I\in {ℐ}_X:|I\cap X|\le \delta n\}$，对于$\delta \in (0,1)$，由引理14得出

(20) $$|{ℐ}_X\backslash {ℐ}_X^{\delta }|\le |{ℐ}_X|\cdot 2^{-\frac{\delta n{\log }^{2}d}{2d}}.$$

定义 ${ℐ}_Y$、${ℐ}_Y^{\delta }$，类似地并取 $\delta =1/30$ 我们有

(21) $$|{ℐ}_X^{\delta }\cap {ℐ}_Y^{\delta }|\le \left(\genfrac{}{}{0pt}{}{2n}{\le 2\delta n}\right)\le 2^n\cdot 2^{-\frac{n{\log }^{2}d}{60d}-1}\le |{ℐ}_X|\cdot 2^{-\frac{n{\log }^{2}d}{60d}-1}.$$

通过 (19)、(20) 和 (21) 我们得出结论：

(22) $|{ℐ}_X\cap {ℐ}_Y|\le |{ℐ}_X\backslash {ℐ}_X^{\delta }|+|{ℐ}_Y\backslash {ℐ}_Y^{\delta }|+|{ℐ}_Y^{\delta }\cap {ℐ}_X^{\delta }|\le 2^n({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)2^{\frac{-n{\log }^{2}d}{60d}},$

因此，通过 (18)，

(23) $2^n({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)\cdot \left(1-2^{\frac{-n{\log }^{2}d}{60d}}\right)\le i(G)\le 2^n({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y).$

这就完成了第一个主张的证明。 对于第二个主张，我们回顾一下离散概率测量之间的总变异距离的以下公式：

(24) ${\Vert {\mu }_G-{\widehat{\mu }}_G\Vert }_{TV}={\displaystyle \sum _{I:{\widehat{\mu }}_G(I)>{\mu }_G(I)}}{\widehat{\mu }}_G(I)-{\mu }_G(I).$

我们注意到，对于$I\in {ℐ}_X\mathrm{△}{ℐ}_Y$,${\widehat{\mu }}_G(I)=2^{-n}{({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)}^{-1}$，而对于$I\in {ℐ}_X\cap {ℐ}_Y$,${\widehat{\mu }}_G(I)=2^{1-n}{({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)}^{-1}$。 从 (23) 可以得出 ${\widehat{\mu }}_G(I)>{\mu }_G(I)$ 仅当 $I\in {ℐ}_X\cap {ℐ}_Y$ 时。 通过 (22) 和 (24)，我们有

$${\Vert {\mu }_G-{\widehat{\mu }}_G\Vert }_{TV}\le 2\cdot 2^{\frac{-n{\log }^{2}d}{60d}}.\mathit{∎}$$

现在我们证明定理1。

定理证明1。

设置${ϵ}_0=2^{-\frac{n{\log }^{2}d}{60d}}$。 首先假设$ϵ\le 2{ϵ}_0$，那么$i(G)$就可以准确计算出来，并且可以在$2^{n+o(n)}={(1/ϵ)}^{O(d/{\log }^{2}d)}$时间内通过暴力方式采样到均匀随机的独立集。

现在假设$ϵ>2{ϵ}_0$。 根据引理 16，计算 ${\mathrm{\Xi }}_G^X$ 和 ${\mathrm{\Xi }}_G^Y$ 的 $(ϵ/4)$ 相对近似值就足够了。 通过使用引理15给出的算法，这需要时间${(n/ϵ)}^{O(d)}$。

对于近似采样算法，我们注意到通过引理16，足以从${\widehat{\mu }}_G$获得$ϵ/2$近似样本。 具体做法如下：我们首先通过分别计算 ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$ 和 ${\mathrm{\Xi }}_G^Y(\mathrm{\ell })$ 来计算 $ϵ/8$ 与 ${\mathrm{\Xi }}_G^X$ 和 ${\mathrm{\Xi }}_G^Y$ 的相关近似值，其中 $\mathrm{\ell }$ 的选择如 Lemma 15 所示。 然后我们用各自的概率${\mathrm{\Xi }}_G^X(\mathrm{\ell })/({\mathrm{\Xi }}_G^X(\mathrm{\ell })+{\mathrm{\Xi }}_G^Y(\mathrm{\ell }))$和${\mathrm{\Xi }}_G^Y(\mathrm{\ell })/({\mathrm{\Xi }}_G^X(\mathrm{\ell })+{\mathrm{\Xi }}_G^Y(\mathrm{\ell }))$选择$X$或$Y$，然后使用引理15 从$X$（分别为）中大致采样相容聚合物$\mathrm{\Lambda }$的配置。 $Y$)，精确到总变化距离$ϵ/8$内。 给定聚合物配置 $\mathrm{\Lambda }$，我们然后独立选择 $Y\setminus N(\mathrm{\Lambda })$ 的每个顶点（分别为： $X\setminus N(\mathrm{\Lambda })$)以概率$1/2$并将它们添加到独立集中。 输出的分布则在 ${\widehat{\mu }}_G$ 的总变化距离 $ϵ/2$ 内。 有关此界限计算的详细信息，请参阅[31]的采样算法。 ∎

6. 一般正二分图的算法：定理证明3

在本节中，我们证明定理 3，给出一种算法，对于任何常数 $c>0$，返回 $n^{-c}$ 中独立集合数量的相对近似值一般的$d$-正则二分图。 与前面的部分一样，我们让 $G$ 表示 $2n$ 顶点上的 $d$ 正则图，其顶点类为 $X$ 和 $Y$. 该算法通过分离 $X$ 的扩展和非扩展 $2$ 链接集对独立集计数的贡献来进行。 为了估计非扩展组件的贡献，我们使用受容器方法启发的简单参数（参见下面的引理17)。 为了估计扩展组件的贡献，我们求助于引理15算法。

我们从以下引理开始，这将使我们能够根据非扩展组件的封闭性对其进行分组。 如果$A=[A]$，我们就说集合$A\subseteq X$是封闭的。

Lemma 17.

令 $A\subseteq X$ 为 $2$ 链接的、封闭的、非扩展的集合。 然后有一个随机 $\mathrm{poly}(n)\cdot {ϵ}^{-2}\ln (1/\delta )\cdot 2^{O\left(\frac{|A|{\log }^{2}d}{d}\right)}$ 时间算法，输出 $ϵ$ 相对于 $2$ 链接 $B\subseteq A$ 数量的近似值，使得$N(B)=N(A)$ 的概率至少为 $1-\delta$。

证明。

让 $W=N(A)$、$w=|W|$ 和 $a=|[A]|$。 让

$$𝒟:=\{B\subseteq A|N(B)=W\text{and}B\text{is}2\text{-linked}\}$$

是我们想要估计其大小的集合。 根据推论 10 最多存在一组 $A^{\prime }\in 𝒟$ 大小

$$2\frac{a}{d}\ln d+2\frac{w}{d}+2(w-a)=O\left(\frac{a{\log }^{2}d}{d}\right).$$

它遵循

$$|𝒟|\ge 2^{a-O\left(\frac{a{\log }^{2}d}{d}\right)}.$$

事实上，每个超集$B\supseteq A^{\prime }$都满足$N(B)=W$，并且$B$是$2$链接的。 第一个属性是明确的，因为$N(B)\supseteq N(A^{\prime \prime })=W$。 第二个属性成立，因为 $B$ 中的每个顶点要么在 $A^{\prime }$ 中，要么距 $A^{\prime }$ 中的某个顶点距离 $2$，即本身$2$链接。 由此可见$|𝒟|$可以通过采样估计到相对误差$ϵ$

$$\frac{1}{{ϵ}^2}\ln (1/\delta )\cdot 2^{O\left(\frac{a{\log }^{2}d}{d}\right)}$$

$A$ 的子集。 ∎

算法

对于一个封闭的、$2$链接的子集$A\subseteq X$，让我们表示

$$𝒟(A):=\mathrm{\#}\{B\subseteq A|B\text{is}2\text{-linked},N(B)=N(A)\}.$$

现在，我们定义一个算法，输入 $n$ 顶点上的图 $G$ 和精度参数 $ϵ>0$，如下所示。 让$L:=\lceil \frac{d}{2{\log }^{2}d}\log (2n/ϵ)\rceil$。 如果$d\le \sqrt{n}$，算法如下：

1. 列出所有正整数向量 $(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$，例如 $\mathrm{\ell }\le n/d$ 和 $\sum a_i\le n$。

2. 对于步骤 1 中的每个向量 $(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$，列出所有集合 $\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$，使得 $N(A_i)$ 成对不相交，并且 $A_i\in {𝒢}^{\prime }(v_i,a_i)$ 对于某些 $v_i\in X$ 对于每个 $i$。

3. 对于步骤 2 中的每个集合 $\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$，计算 $\widetilde{𝒟}(A_i)$，它是 $(ϵ/2n)$ 与 $𝒟(A_i)$ 的相对近似值，使用例证 17，为所有 $i$ 设置 $\delta =(1/3)\cdot 2^{-n^2}$。

4. 对于步骤 2 中的每个集合 $A=\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$，让 $Y_A=Y\setminus N({\cup }_{i=1}^{\mathrm{\ell }}{A}_i)$、$X_A=X\setminus N^2({\cup }_{i=1}^{\mathrm{\ell }}{A}_i)$、$G_A=G[X_A\cup Y_A]$ 并计算 ${\mathrm{\Xi }}_{G_A}^{X_A}(L)$。

5. 输出

   $$\sum _{\mathrm{\ell }=0}^{n/d}\sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}\left(\prod _{i=1}^{\mathrm{\ell }}\widetilde{𝒟}(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\mathrm{\Xi }}_{G_A}^{X_A}(L)\right).$$

如果$d>\sqrt{n}$，算法是运行上面的步骤1-3并输出

(25) ${\displaystyle \sum _{\mathrm{\ell }=0}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}\widetilde{𝒟}(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\right).$

定理证明3

我们首先证明算法的正确性：对于任何 $c>0$ 和 $ϵ=n^{-c}$，输出是 $ϵ$ 相对于 $i(G)$ 的近似值。 和之前一样，我们让 $X,Y$ 表示 $G$ 的顶点类。首先假设$d\le \sqrt{n}$。 然后我们有

$i(G)$ $=2^{|Y|}\cdot {\displaystyle \sum _{t=0}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_t\text{compatible}\\ A_{i}2\text{-linked}\forall i\end{array}}}\left({\displaystyle \prod _{i=1}^t}{2}^{-N(A_i)}\right)$

$=2^{|Y|}\cdot {\displaystyle \sum _{t=0}^{n/d}}{\displaystyle \sum _{\mathrm{\ell }=0}^t}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding},\\ 2\text{-linked}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}{2}^{-N(A_i)}\cdot {\displaystyle \sum _{\begin{array}{c}{A}_{\mathrm{\ell }+1},\mathrm{\dots },A_t\\ \subseteq X\setminus N^2({\cup }_{j=1}^{\mathrm{\ell }}{A}_j)\\ \text{compatible}\\ \forall i{A}_i\text{expanding},\\ 2\text{-linked}\end{array}}}{\displaystyle \prod _{i=\mathrm{\ell }+1}^t}{2}^{-N(A_i)}\right)$

$=2^{|Y|}\cdot {\displaystyle \sum _{t=0}^{n/d}}{\displaystyle \sum _{\mathrm{\ell }=0}^t}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}{\displaystyle \sum _{\begin{array}{c}{B}_1,\mathrm{\dots },B_{\mathrm{\ell }}\\ \forall i,B_i\subseteq A_i,\\ N(B_i)=N(A_i),\\ B_{i}2\text{-linked}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}{2}^{-N(A_i)}\cdot {\displaystyle \sum _{\begin{array}{c}{A}_{\mathrm{\ell }+1},\mathrm{\dots },A_t\\ \subseteq X\setminus N^2({\cup }_{j=1}^{\mathrm{\ell }}{A}_j)\\ \text{compatible}\\ \forall i{A}_i\text{expanding},\\ 2\text{-linked}\end{array}}}{\displaystyle \prod _{i=\mathrm{\ell }+1}^t}{2}^{-N(A_i)}\right)$

$={\displaystyle \sum _{\mathrm{\ell }=1}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}{\displaystyle \sum _{\begin{array}{c}{B}_1,\mathrm{\dots },B_{\mathrm{\ell }}\\ \forall i,B_i\subseteq A_i,\\ N(B_i)=N(A_i),\\ B_{i}2\text{-linked}\end{array}}}\left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\displaystyle \sum _{t=1}^{n/d-\mathrm{\ell }}}{\displaystyle \sum _{\begin{array}{c}{A}_1^{\prime },\mathrm{\dots },A_t^{\prime }\\ \subseteq X\setminus N^2({\cup }_{j=1}^{\mathrm{\ell }}{A}_j)\\ \text{compatible}\\ \forall i{A}_i^{\prime }\text{expanding},\\ 2\text{-linked}\end{array}}}{\displaystyle \prod _{i=1}^t}{2}^{-N(A_i^{\prime })}\right)$

$={\displaystyle \sum _{\mathrm{\ell }=1}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}𝒟(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\mathrm{\Xi }}_{G_A}^{X_A}\right)$

$=(1\pm ϵ){\displaystyle \sum _{\mathrm{\ell }=1}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}\widetilde{𝒟}(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\mathrm{\Xi }}_{G_A}^{X_A}(L)\right).$

对于我们在备注 1 中使用的最后一个等式，我们可以将引理 13 应用于 $G_A$，因此 ${\mathrm{\Xi }}_{G_A}^{X_A}(L)$ 是一个$ϵ$-相对于${\mathrm{\Xi }}_{G_A}^{X_A}$的近似值。 观察到最多有 $2^{n^2}$ 个非扩展 $A_1,\mathrm{\dots },A_{\mathrm{\ell }}$ 的选择。 因此，通过对所有这些选择进行联合边界，最后的总和正是算法以至少 $1-\delta \cdot 2^{n^2}=2/3$ 的概率输出的结果，我们拥有所需的近似保证。 如果 $d\ge \sqrt{n}$，那么我们注意到，由于 $G_A$ 的聚合物是 $G$ 聚合物的子集，我们有 (17)即$\ln {\mathrm{\Xi }}_{G_A}^{X_A}\le \ln {\mathrm{\Xi }}_G^X\le 2^{-\mathrm{\Omega }({\log }^{2}n)}$。 由此可见 $1$ 是 $ϵ$ 相对于 ${\mathrm{\Xi }}_{G_A}^{X_A}$ 的近似值（回想一下 $ϵ=n^{-c}$)，因此 (25) 是 $i(G)$ 的 $ϵ$ 相对近似值。

现在我们证明，如果 $ϵ=n^{-c}$ 且 $c>0$ 固定，则上述算法将在 $2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$ 时间内运行。 我们逐步考虑该算法。

步骤1。 对于$\mathrm{\ell }\le n/d$和$k\le n$，正整数向量$(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$的数量使得$\sum a_i=k$（即$k$ 与 $\mathrm{\ell }$ 部分）是

$$\left(\genfrac{}{}{0pt}{}{k-1}{\mathrm{\ell }-1}\right)\le \left(\genfrac{}{}{0pt}{}{n}{n/d}\right)=2^{O\left(\frac{\log d}{d}n\right)}.$$

此外，很明显，所有此类分区的集合可以在时间 $2^{O\left(\frac{\log d}{d}n\right)}$ 中列出，因此步骤 1 需要时间 $2^{O\left(\frac{\log d}{d}n\right)}$。

第2步。 令 $(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$ 为正整数向量，使得 $\mathrm{\ell }\le n/d$ 和 $\sum a_i\le n$ 成立。 我们首先列出所有元组顶点$\{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}\subset X$，这需要时间$\left(\genfrac{}{}{0pt}{}{n}{\mathrm{\ell }}\right)=2^{O\left(\frac{\log d}{d}n\right)}$。 对于每个$\{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}$，我们然后诉诸引理5在时间$2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$输出元组$({𝒢}^{\prime }(v_1,a_1),\mathrm{\dots },{𝒢}^{\prime }(v_{\mathrm{\ell }},a_{\mathrm{\ell }}))$。 我们注意到引理 5

$$|{𝒢}^{\prime }(v_1,a_1)\times \mathrm{\dots }\times {𝒢}^{\prime }(v_{\mathrm{\ell }},a_{\mathrm{\ell }})|\le \prod _{i=1}^{\mathrm{\ell }}{2}^{O\left(\frac{{\log }^{3}d}{d}{a}_i\right)}=2^{O\left(\frac{{\log }^{3}d}{d}n\right)}.$$

因此，我们可以检查${𝒢}^{\prime }(v_1,a_1)\times \mathrm{\dots }\times {𝒢}^{\prime }(v_{\mathrm{\ell }},a_{\mathrm{\ell }})$中的每个元素，看看它是否满足所需的条件，并在$2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$时间输出所需的列表。

步骤 3. 给定步骤 2 中的集合 $\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$，我们使用 Lemma 17计算所有 $i$ 的 $ϵ/n$ 相对于 $𝒟(A_i)$ 的近似 $\widetilde{𝒟}(A_i)$。 这需要时间

$${(ϵ/n)}^{-2}\ln (1/\delta )2^{O\left(\frac{{\log }^{2}d}{d}n\right)}=2^{O\left(\frac{{\log }^{2}d}{d}n\right)}$$

我们回想起 $ϵ=n^{-C}$ 和 $\delta =(1/3)\cdot 2^{-n^2}$。

步骤4。 如果 ，那么给定步骤 2 中的任意集合 $A=\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$，我们可以通过第 4 节中限制于 $G_A$ 的聚合物的算法，在 ${(n/ϵ)}^{O(d)}=2^{O\left(\frac{{\log }^{2}d}{d}n\right)}$ 的时间内计算 ${\mathrm{\Xi }}_{G_A}^{X_A}(L)$。 如果$d\ge \sqrt{n}$，我们跳过步骤4。

我们得出结论，该算法总共需要时间$2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$。

7. 加权独立集：定理 2 的证明

定理 2 的证明将遵循与定理 1 相同的思路，主要区别在于聚合物重量现在为 $w_{\gamma }=\frac{{\lambda }^{|\gamma |}}{{(1+\lambda )}^{|N(\gamma )|}}$，概括为定理 1 的 $\lambda =1$ 情况。

在本节中，我们假设 $G$ 是一个 $d$ - 常规二分 $\alpha$ - 扩展器，其二分 $X,Y$ 大小为 $n$ 每个。

定义一个聚合物模型，其中聚合物由 $2$ 连接的小 $X$ 子集组成（分别为： $Y$)，如果两个聚合物的联合不是$2$连接，则它们是兼容的（回想一下，如果$|[\gamma ]|\le n/2$,$\gamma \subset X$很小）。 聚合物$\gamma$的重量为$w_{\gamma }=\frac{{\lambda }^{|\gamma |}}{{(1+\lambda )}^{|N(\gamma )|}}$。 令 ${\mathrm{\Xi }}_G^X(\lambda )$ 为聚合物模型配分函数，${\nu }_{G,\lambda }^X$ 为相容聚合物集合的相应吉布斯测度。

定理 2 由以下两个引理得出。 下面的引理18是引理15的类似物，引理19是引理16的类似物。

Lemma 18.

对于每个$\alpha >0$，都存在$C_2>0$，因此如果$\lambda \ge \frac{C_2\log d}{d^{1/4}}$，则有一个FPTAS来计算${\mathrm{\Xi }}_G^X(\lambda )$和${\mathrm{\Xi }}_G^Y(\lambda )$ 以及${\nu }_{G,\lambda }^X$ 和${\nu }_{G,\lambda }^Y$ 的多项式时间采样方案。

如第 5 节中一样，我们将独立集上的概率度量定义为源自两个聚合物模型的度量的混合。 如下定义 $ℐ(G)$ 上的分布 ${\widehat{\nu }}_{G,\lambda }^X$。

1. 从测量 ${\nu }_{G,\lambda }^X$ 中对一系列相容聚合物 $\mathrm{\Lambda }$ 进行采样。

2. 设置$I=J\cup {\bigcup }_{\gamma \in \mathrm{\Lambda }}\gamma$，其中$J$是$Y\backslash {\bigcup }_{\gamma \in \mathrm{\Lambda }}N(\gamma )$的随机子集，通过以概率$\lambda /(1+\lambda )$独立地包含每个顶点而形成。

类似地定义 ${\widehat{\nu }}_{G,\lambda }^Y$ 并定义混合

$${\widehat{\mu }}_{G,\lambda }=\frac{{\mathrm{\Xi }}_G^X(\lambda )}{{\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda )}{\widehat{\nu }}_{G,\lambda }^X+\frac{{\mathrm{\Xi }}_G^Y(\lambda )}{{\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda )}{\widehat{\nu }}_{G,\lambda }^Y.$$

Lemma 19.

对于每个 $\alpha >0$，都存在 $C_2>0$，因此如果 $\lambda \ge \frac{C_2\log d}{d^{1/4}}$ 则对于 $n$ 足够大，

$${(1+\lambda )}^n\left({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda )\right)$$

是 $ϵ$ 相对于 $Z_G(\lambda )$ 的近似值，并且

其中$ϵ=\exp (-\mathrm{\Omega }(n))$，隐式常量是$d$的函数。

为了证明引理18和19，我们将第3和4部分的估计扩展到更一般的情况。 主要的图容器引理来自 Galvin 和 Tetali 的论文[20]。 让我们定义

$${𝒲}_{\lambda }(v,a,w):=\sum _{\begin{array}{c}A\subset X\\ |[A]|\le n/2,\\ A\text{is}2\text{-linked}\\ |N(A)|=w\end{array}}{\lambda }^{|A|}{(1+\lambda )}^{-w},$$

和

$$\beta (\lambda ):=\frac{{\log }^2(1+\lambda )}{\log (1+\lambda )+\log (2d^5/\alpha )}.$$

我们使用 [20] 中的以下引理。

Lemma 20.

存在常量 $c_4$ 和 $c_5$，使得以下成立：令 $G$ 为二部 $\alpha$-expander 并假设 $\lambda >0$. 如果$\beta (\lambda )$满足

$$\beta (\lambda )\ge c_4\max \{\frac{\log (d^5/\alpha )}{\sqrt{d}},\frac{2{\log }^{2}d}{\alpha d}\}.$$

然后

$${𝒲}_{\lambda }(v,a,w)\le 2^{-c_5(w-a)\beta (\lambda )}.$$

上述引理的假设表明$\alpha \beta (\lambda )\ge 2c_4\cdot \frac{{\log }^{2}d}{d}$。 然而，在我们的应用程序中，我们还将假设 $\beta (\lambda )$ 也足够大以确保

(26) $$\alpha \beta (\lambda )\ge \frac{4000}{c_5}\cdot \frac{{\log }^{2}d}{d}.$$

这可以通过假设$\lambda \ge \frac{C\log d}{d^{1/4}}$为足够大的常数$C_2$来完成。

我们现在证明引理18。

引理18的证明。

正如引理 15 的证明一样，FPTAS 和多项式时间采样方案将在验证聚合物模型的 Koteckỳ-Preiss 条件后得出。

聚合物模型满足(11)、$f(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|\gamma |}{8}$和$g(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|N(\gamma )|}{8}$，如以下计算所示。

${\displaystyle \sum _{{\gamma }^{\prime }\sim ̸\gamma }}{w}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$ $\le {\displaystyle \sum _{v\in \gamma }}{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{w}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{\lambda }^{|\gamma |}{(1+\lambda )}^{-|N({\gamma }^{\prime })|}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}\left({\displaystyle \sum _{t\ge (\alpha /2)w}}{𝒲}_{\lambda }(v,w-t,w)\cdot e^{c_5\alpha \ln 2\frac{\beta (\lambda )w}{4}}\right)$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}{e}^{c_5\alpha \ln 2\frac{\beta (\lambda )w}{4}}\left({\displaystyle \sum _{t\ge (\alpha /2)w}}{𝒲}_{\lambda }(v,w-t,w)\right)$

$\le |\gamma |{\displaystyle \sum _{w\ge d}}{2}^{c_5\alpha \frac{\beta (\lambda )w}{4}}\left({\displaystyle \sum _{t\ge (\alpha /2)w}}{2}^{-c_5\beta (\lambda )t}\right)$

$\le 2d|\gamma |{\displaystyle \sum _{w\ge d}}{2}^{c_5\alpha \frac{\beta (\lambda )w}{4}}{2}^{-c_5\alpha \frac{\beta (\lambda )w}{2}}$

$\le 4d^2|\gamma |2^{-c_5\alpha \frac{\beta (\lambda )d}{4}}$

$\le 4d^2|\gamma |2^{-500{\log }^{2}d}\cdot 2^{-c_5\alpha \frac{\beta (\lambda )d}{8}}$

$\le |\gamma |\cdot c_5\alpha {\displaystyle \frac{\beta (\lambda )}{16}}.$

最后一个不等式如下，因为对于$d\ge 3$，我们有，对于任何$x,y>0$，我们有$2^{-x}\le \frac{x}{2y}$，如果$x\ge 500{\log }^{2}y$。

将 ${\mathrm{\Xi }}_G^X(\mathrm{\ell },\lambda )$ 定义为截断簇扩展的指数，如 (15) 中所示。 通过引理13的计算，对于每个$\mathrm{\ell }\ge 1$，我们有，

(27) $$\left|\ln {\mathrm{\Xi }}_G^X(\lambda )-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell },\lambda )\right|\le n\cdot 2^{-500\frac{{\log }^{2}d\cdot \mathrm{\ell }}{d}}.$$

特别是，如果$\mathrm{\ell }\ge \frac{d}{1000{\log }^{2}d}\log (n/ϵ)$，那么

$$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell },\lambda )\right|\le ϵ.\mathit{∎}$$

我们现在证明引理19。

引理19的证明。

考虑一个权重为 ${\tilde{w}}_{\gamma }(\lambda )={\lambda }^{|\gamma |}{(1+\lambda )}^{-|N(\gamma )|}{2}^{c_5\alpha \frac{\beta (\lambda )}{16}}$ 的修改聚合物模型。 引理18证明中的计算表明，权重为${\tilde{w}}_{\gamma }(\lambda )$的修正聚合物模型满足(11)和$f(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|\gamma |}{16}$， $g(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|N(\gamma )|}{8}$。

让 ${\tilde{\mathrm{\Xi }}}_G^X(\lambda )$ 表示修改后的聚合物模型配分函数，如 (13) 中所示。 然后我们有

$$\ln {\tilde{\mathrm{\Xi }}}_G^X(\lambda )-\ln {\mathrm{\Xi }}_G^X(\lambda )=\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }$$

对于$\zeta =c_5\alpha \ln 2\frac{\beta (\lambda )}{16}$。 对所有 $v$ 求和 (14)，并利用 $|N(\gamma )|\ge d$ 对于每个 $\gamma$ 的事实，我们得到（如 (17))

(28) $$\ln {\tilde{\mathrm{\Xi }}}_G^X\le \sum _v\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}\left|\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{\tilde{w}}_{\gamma }\right|\le n\cdot 2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}.$$

因此，我们有

$\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }\le \ln {\tilde{\mathrm{\Xi }}}_G^X\le n\cdot 2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}.$

修复任何 $\delta \ge \frac{10}{\sqrt{d}}$。 根据马尔可夫不等式，我们有

$\mathbb{P}(\Vert 𝚲\Vert \ge \delta n)$ $\le \exp \left(-\zeta \delta n+n\cdot 2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}\right)$

$\le 2^{-c_5\alpha \frac{\beta (\lambda )}{32}\cdot \delta n}$

(29) $\le 2^{-\frac{100{\log }^{2}d}{d}\cdot \delta n},$

其中倒数第二个不等式如下，因为对于任何 $x,y>0$，如果 $x\ge 500{\log }^{2}y$，我们就有 $2^{-x\cdot y}\le \frac{x}{2\sqrt{y}}$，因此

$$2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}\le \frac{c_5\alpha \beta (\lambda )}{16\sqrt{d}}\le \frac{\zeta \delta }{2}.$$

最终的不等式 (7) 由 (26) 得出。

与定理 16 的证明一样，让 ${ℐ}_X=\{I\in ℐ:{\nu }_{G,\lambda }^X(I)>0\}$ 即所有 $I$ 的集合，使得 $I\cap X$ 的每个 $2$ 链接分量都很小。 对于$\delta >0$，设${ℐ}_X^{\delta }=\{I\in {ℐ}_X:|I\cap X|\le \delta n\}$并类似地定义${ℐ}_Y$、${ℐ}_Y^{\delta }$。 如引理 16、$ℐ={ℐ}_X\cup {ℐ}_Y$ 等

(30) $Z_G(\lambda )={\displaystyle \sum _{I\in {ℐ}_X}}{\lambda }^{|I|}+{\displaystyle \sum _{I\in {ℐ}_Y}}{\lambda }^{|I|}-{\displaystyle \sum _{I\in {ℐ}_X\cap {ℐ}_Y}}{\lambda }^{|I|}={(1+\lambda )}^n({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda ))-{\displaystyle \sum _{I\in {ℐ}_X\cap {ℐ}_Y}}{\lambda }^{|I|}.$

现在，令 $I$ 为从分布 ${\nu }_{G,\lambda }^X$ 中选择的随机独立集。 从 (7) 可以得出，对于 $\delta \ge \frac{10}{\sqrt{d}}$，

(31) $$\mathbb{P}(|I\cap X|>\delta n)=\sum _{I\in {ℐ}_X\backslash {ℐ}_X^{\delta }}\frac{{\lambda }^{|I|}}{{(1+\lambda )}^n{\mathrm{\Xi }}_G^X(\lambda )}\le 2^{-\frac{100{\log }^{2}d}{d}\cdot \delta n}.$$

此外，我们还有

${\displaystyle \sum _{I\in {ℐ}_X^{\delta }\cap {ℐ}_Y^{\delta }}}{\displaystyle \frac{{\lambda }^{|I|}}{{(1+\lambda )}^n{\mathrm{\Xi }}_G^X(\lambda )}}$ $\le {\displaystyle \frac{{\sum }_{i,j\le \delta n}\left(\genfrac{}{}{0pt}{}{n}{i}\right)\left(\genfrac{}{}{0pt}{}{n}{j}\right){\lambda }^{i+j}}{{(1+\lambda )}^n}}$

$={\displaystyle \frac{{\left({\sum }_{i\le \delta n}\left(\genfrac{}{}{0pt}{}{n}{i}\right){\lambda }^i\right)}^2}{{(1+\lambda )}^n}}$

$={(1+\lambda )}^n\mathbb{P}{\left(\mathrm{Bin}(n,{\displaystyle \frac{\lambda }{1+\lambda }})\le \delta n\right)}^2$

对于$\delta =\frac{\lambda }{100(1+\lambda )}$，该数量最多可以为$e^{-\frac{\delta n}{16}}$。 我们注意到 $\delta \ge \frac{C{\log }^{2}d}{d^{1/4}}\ge \frac{10}{\sqrt{d}}$ 对于足够大的 $C$ 来说，所以

${\displaystyle \sum _{I\in {ℐ}_X\cap {ℐ}_Y}}{\lambda }^{|I|}$ $\le {\displaystyle \sum _{I\in {ℐ}_X\backslash {ℐ}_X^{\delta }}}{\lambda }^{|I|}+{\displaystyle \sum _{I\in {ℐ}_Y\backslash {ℐ}_Y^{\delta }}}{\lambda }^{|I|}+{\displaystyle \sum _{I\in {ℐ}_X^{\delta }\cap {ℐ}_Y^{\delta }}}{\lambda }^{|I|}$

$\le {(1+\lambda )}^n({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda ))e^{-\mathrm{\Omega }(n)}.$

到 (30)，我们得出结论：

$\left|{\displaystyle \frac{Z_G(\lambda )}{{(1+\lambda )}^n({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda ))}}-1\right|=e^{-\mathrm{\Omega }(n)}.$

总变异距离的界限与引理 16 的证明相同。 ∎

致谢

WP 部分由 NSF 拨款 DMS-1847451 支持。 AP 部分由 NSF 拨款 CCF-1934915 支持。