通过收缩快速混合格劳伯动力学直至达到独特性

摘要

对于一般的反铁磁$2$自旋系统，包括加权独立集上的硬核模型和反铁磁伊辛模型，当无限正则树位于李等人（2013）的唯一性区域时，最大阶数$\mathrm{\Delta }$图上的分割函数有一个$\mathrm{𝖥𝖯𝖳𝖠𝖲}$。 此外，在树非唯一性区域中，Sly（2010）表明，除非$\mathrm{𝖭𝖯}=\mathrm{𝖱𝖯}$，否则不存在$\mathrm{𝖥𝖯𝖱𝖠𝖲}$来估计配分函数。 算法结果遵循 Weitz (2006) 提出的相关衰减方法或 Barvinok (2016) 开发的多项式插值方法。 然而，运行时间只是常数$\mathrm{\Delta }$的多项式。 对于硬核模型，Anari 等人（2020）最近的工作在树唯一性区域建立了简单单点马尔可夫链的快速混合，称为格劳伯动力学。 我们的工作通过考虑固定顶点 $v$ 对其他顶点的总成对影响（而不是其他顶点对 $v$ 的总影响）来简化他们对格劳伯动力学的分析，从而扩展他们对所有 2 旋转模型的工作并改进了混合时间。

更重要的是，我们的证明将三种不同的算法方法联系在一起：我们证明了所谓的树递归与合适的势函数的收缩，这是建立 Weitz 相关衰减方法和 Barvinok 多项式插值方法效率的主要技术，也建立了格劳伯动力学的快速混合。 我们强调，这种联系适用于所有 2 自旋模型（反铁磁和铁磁），并且相关衰减或多项式插值方法的现有证明立即意味着格劳伯动力学的快速混合。 我们的证明利用图配分函数是韦茨自回避游走树配分函数的除数。 这一事实催生了用于分析顶点影响的新工具，并且可能对复零的研究具有独立意义。

1简介

在最大度数 $\mathrm{\Delta }$ 的一般图中的近似计数问题的计算复杂性与度数 $\mathrm{\Delta }$ 的无限规则树（或向上）上的统计物理相变之间建立了显着的联系。在更一般的情况下为 $\mathrm{\Delta }$)。 这种联系适用于二态反铁磁自旋系统——独立集上的硬核模型和伊辛模型是此类系统最有趣的例子。

给定一个 $n$ 顶点图 $G=(V,E)$，2 个自旋模型的配置是对顶点的自旋 $0,1$ 的 $2^n$ 分配。 2-自旋系统由三个参数定义：边权重$\beta ,\gamma >0$和顶点权重$\lambda >0$。 边缘参数$\beta$控制相邻$1$-自旋之间相互作用的（相对）强度，$\gamma$对应于相邻$0$-自旋，并且$\lambda$ 是应用于具有 $1$-自旋的顶点的外部场。

每个自旋配置 $\sigma \in {\{0,1\}}^V$ 都分配有一个权重

$$w_G(\sigma )={\beta }^{m_1(\sigma )}{\gamma }^{m_0(\sigma )}{\lambda }^{n_1(\sigma )},$$

其中，对于自旋$s\in \{0,1\}$,$m_s(\sigma )=\mathrm{\#}\{uv\in E:{\sigma }_u={\sigma }_v=s\}$是具有自旋$s$的单色边的数量，$n_1(\sigma )=\mathrm{\#}\{v\in V:{\sigma }_v=1\}$是具有自旋的顶点的数量$1$（按照标准，参数已标准化，因此我们可以避免两个额外的参数）。 自旋构型的吉布斯分布由 ${\mu }_G(\sigma )=\frac{w_G(\sigma )}{Z_G(\beta ,\gamma ,\lambda )},$ 给出，其中 $Z_G(\beta ,\gamma ,\lambda )={\sum }_{\sigma \in {\{0,1\}}^V}{\beta }^{m_1(\sigma )}{\gamma }^{m_0(\sigma )}{\lambda }^{n_1(\sigma )}$ 是配分函数。

有两个特别有趣的例子：硬核模型和伊辛模型。 当$\beta =0$和$\gamma =1$时，唯一具有非零权重的配置是$G$的独立集和独立集$\sigma$的权重是$w(\sigma )={\lambda }^{|\sigma |}$；这个例子被称为硬核模型，其中参数$\lambda$对应于逸度。

在$\beta =\gamma$的情况下，重要的量是单色边的总数$m(\sigma )=m_0(\sigma )+m_1(\sigma )$，配置的权重$\sigma$是$w(\sigma )={\beta }^{m(\sigma )}{\lambda }^{n_1(\sigma )}$；这是经典的伊辛模型，其中参数$\beta$对应于逆温度，$\lambda$是外部场($\lambda =1$表示没有外场）。 请注意，当$\beta >1$时，模型是铁磁，因为相邻顶点更喜欢具有相同的自旋，而是反铁磁伊辛模型。 在一般的$2$自旋系统中，当$\beta \gamma >1$时模型是铁磁的，当时模型是反铁磁的。 （当 $\beta \gamma =1$ 时，我们得到一个简单的产品分布。）

基本算法任务是从吉布斯分布中采样并估计配分函数。 对于近似采样问题，我们给出一个图 $G$ 和一个 $ϵ>0$，我们的目标是从总变异距离内的分布 $\pi$ 生成样本$\le ϵ$ 的吉布斯分布 ${\mu }_G$ 在时间 $\mathrm{poly}(n,\log (1/ϵ))$ 上的分布。 高效的近似采样算法意味着近似计数问题[JVV86，ŠVV09]的$\mathrm{𝖥𝖯𝖱𝖠𝖲}$（完全多项式随机近似方案）。 回想一下，给定一个 $n$ 顶点图 $G$ 和 $ϵ,\delta >0$,$\mathrm{𝖥𝖯𝖱𝖠𝖲}$ 输出一个 $(1\pm ϵ)$ 近似值$Z_G$ 的概率 $\ge 1-\delta$ 在时间 $\mathrm{poly}(n,1/ϵ,\log (1/\delta ))$ 中，而 $\mathrm{𝖥𝖯𝖳𝖠𝖲}$ 是确定性模拟（即 $\delta =0$ ）。

近似采样问题的标准方法是马尔可夫链蒙特卡罗 (MCMC) 方法；事实上，有一个简单的马尔可夫链，称为格劳伯动力学。 格劳伯动力学的工作原理如下：从时间 $t$ 的配置 $X_t$ 中，选择一个随机顶点 $v$，然后设置 $X_{t+1}(w)=X_t(w)$ 为所有$w\ne v$，最后我们从$\mu ({\sigma }_v|{\sigma }_w=X_{t+1}(w)\text{for all}w\ne v)$的条件分布中选择$X_{t+1}(v)$。 对于硬核模型的情况，如果当前没有邻居被占用，则$X_{t+1}(v)$被设置为被占用（即自旋$1$)，概率为$\lambda /(1+\lambda )$，否则它被设置为空闲。

很容易验证格劳伯动力学是遍历的，吉布斯分布是唯一的平稳分布。 混合时间是保证从最差初始状态$X_0$开始，$X_t$的分布在总变化距离$\le 1/4$ 的吉布斯分布。 目标是证明混合时间是$n$中的多项式，在这种情况下，链被称为快速混合。

对于铁磁 Ising 模型（有或没有外场）的情况，Jerrum 和 Sinclair [JS93] 的经典结果通过 MCMC 方法为所有图给出了 $\mathrm{𝖥𝖯𝖱𝖠𝖲}$ 。 这是通用图的有效算法的唯一情况。 对于反铁磁二自旋模型，该图与常规树上的统计物理相变密切相关。

硬核模型的情况很好地说明了唯一性/非唯一性相变。 考虑以 $r$ 为根的无限 $\mathrm{\Delta }$-正则树 $T$，并让 $T_h$ 表示在第一个 $h$ 此相变捕获 $T_h$ 叶子处的配置是否在限制 $h\to \mathrm{\infty }$ 内“影响”根。 对于硬核模型，我们可以考虑偶数高度树（对应于全偶数边界条件）与奇数高度树。 令$p_h$表示吉布斯分布${\mu }_{T_h}$中根被占据的边际概率。 让 $p_{\mathrm{𝖾𝗏𝖾𝗇}}={lim}_{h\to \mathrm{\infty }}{p}_{2h}$ 和 $p_{\mathrm{𝗈𝖽𝖽}}={lim}_{h\to \mathrm{\infty }}{p}_{2h+1}$。 如果成立，我们就说树唯一性成立；如果$p_{\mathrm{𝖾𝗏𝖾𝗇}}=p_{\mathrm{𝗈𝖽𝖽}}$不相等，我们就说树非唯一性成立。 对于所有$\mathrm{\Delta }\ge 3$，都存在临界逸度${\lambda }_c(\mathrm{\Delta })={(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}/{(\mathrm{\Delta }-2)}^{\mathrm{\Delta }})$[Kel85]，其中树唯一性保持当且仅当$\lambda \le {\lambda }_c(\mathrm{\Delta })$。

显着的联系是最大度 $\mathrm{\Delta }$ 的一般图的算法相变发生在同一树临界点。 对于所有常量$\mathrm{\Delta }$、所有$\delta >0$、所有、所有最大度图$\mathrm{\Delta }$、[Wei06] 提出了一个用于近似配分函数的$\mathrm{𝖥𝖯𝖳𝖠𝖲}$。 另一方面，对于所有$\delta >0$，所有$\lambda >(1+\delta ){\lambda }_c(\mathrm{\Delta })$,[Sly10，SS14，GŠV16]证明，除非$\mathrm{𝖭𝖯}=\mathrm{𝖱𝖯}$，没有用于估计配分函数的$\mathrm{𝖥𝖯𝖱𝖠𝖲}$。

一个重要的警告是，Weitz 算法的运行时间为 ${(n/ϵ)}^{C\log \mathrm{\Delta }}$，其中近似因子为 $(1\pm ϵ)$，常数 $C$ 多项式取决于间隙 $\delta$（回想一下，)。 Sinclair 等人[SST14]将Weitz的相关衰减算法扩展到树唯一性区域中的反铁磁Ising模型，以及相应树唯一性区域中的所有反铁磁2-自旋系统（如下详述） ) 作者：Li、Lu 和 Yin [LLY13]。

Barvinok [Bar16] 提出了一种有趣的新算法方法，并由 Patel 和 Regts [PR17] 改进，利用复平面中配分函数零点的缺失来使用泰勒近似有效地近似配分函数对数的合适变换。 这种多项式插值方法被证明在与 Peters 和 Regts [PR19] 的 Weitz 结果相同的树唯一性区域中是有效的，尽管运行时间的指数取决于 $\mathrm{\Delta }$。

长期以来，人们推测简单的格劳伯动力学正在树的独特性区域中迅速混合。 Anari、Liu 和 Oveis Gharan 最近证明了这一点[ALO20]；他们证明，对于所有$\delta >0$，只要，混合时间就是$n^{O(\exp (1/\delta ))}$。 我们改进了这个结果。 首先，我们将混合时间从 $n^{O(\exp (1/\delta ))}$ 改进到 $n^{O(1/\delta )}$，如以下定理所述。

Theorem 1 （硬核模型）。

令 $\mathrm{\Delta }\ge 3$ 为整数，$\delta \in (0,1)$。 对于最大度$\mathrm{\Delta }$的每个$n$-顶点图$G$和每个，硬核模型的格劳伯动力学的混合时间在 $G$ 上，逸度 $\lambda$ 为 $O(n^{2+32/\delta })$。

除非进一步改进 [AL20] 中的局部到全局参数，此界限是最佳的。 我们改进的结果源于更简单、更清晰的证明方法，该方法使我们能够将结果扩展到各种 2-spin 模型，与相关衰减算法的关键结果相匹配，并大大缩短运行时间。

我们的证明方法统一了近似计数的三种主要算法工具：相关衰减、多项式插值和 MCMC。 相关衰减和多项式插值方法的大多数已知结果都是通过在所谓的树递归上显示适当定义的势函数的收缩来证明的；树递归是韦茨的自回避游走树的结果，我们将在本文后面更详细地描述。 Shao 和 Sun 最近的一项工作[SS20] 统一了这两种方法，表明通常用于证明相关衰减算法效率的收缩也意味着（在一些额外的分析条件下）多项式插值方法是有效的。

在这里，我们证明了势函数的相同收缩也意味着格劳伯动力学的快速混合，以及我们改进的独立于 $\mathrm{\Delta }$ 的运行时间；详细说明请参见4和5。 我们的证明利用了有关韦茨自回避游走树的几个新工具，这些工具在部分 3中有详细介绍。 特别地，我们证明了图$G$的配分函数除以Weitz自回避游走树的配分函数；请参阅8。 这一结果对于确定具有复杂参数的配分函数不存在零点具有潜在的独立意义，因为它使人们能够考虑自回避游走树。 这一结果还产生了一个新的、有用的等价物，用于根据自回避树来限制图中的影响，这加强了 Weitz [Wei06] 先前已知的联系；详情请参见8。

作为一个简单的结果，我们在树唯一性区域中获得了反铁磁 Ising 模型的 Glauber 动力学的快速混合。 就边活动而言，$\mathrm{\Delta }$-正则树上 Ising 模型的两个临界点位于 ${\beta }_c(\mathrm{\Delta })=\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 ${\overline{\beta }}_c(\mathrm{\Delta })=\frac{1}{{\beta }_c(\mathrm{\Delta })}=\frac{\mathrm{\Delta }}{\mathrm{\Delta }-2}$；第一个位于反铁磁区域，而第二个位于铁磁区域。 如果，则唯一性适用于$\mathrm{\Delta }$-常规树上的所有外部字段$\lambda$。

如前所述，对于铁磁 Ising 模型，$\mathrm{𝖥𝖯𝖱𝖠𝖲}$ 被称为通用图 [JS93]。 此外，Mossel和Sly[MS13]证明了铁磁Ising模型的Glauber动力学在时的$O(n\log n)$混合时间。 然而，反铁磁伊辛模型在树独特性区域的快速混合尚不清楚。

我们为情况 $\beta >{\beta }_c(\mathrm{\Delta })$ 提供以下混合结果。 请注意，当 $\beta \le {\beta }_c$ 时，外部字段 $\lambda$ 的某些值有一个额外的唯一性区域；该区域由 3 覆盖。

Theorem 2 （反铁磁伊辛模型）。

令 $\mathrm{\Delta }\ge 3$ 为整数，$\delta \in (0,1)$。 假设$1>\beta \ge {\beta }_c(\mathrm{\Delta })+\delta (1-{\beta }_c(\mathrm{\Delta }))$和$\lambda >0$。 然后对于最大度$\mathrm{\Delta }$的每个$n$-顶点图$G$，伊辛模型的格劳伯动力学在$G$上的混合时间边权重为$\beta$，外场$\lambda$为$O(n^{2+1.5/\delta })$。

我们的硬核模型和伊辛模型的结果适合一般反铁磁二自旋系统的更大框架。 回想一下，反铁磁情况是在 时。

对于一般的 2-自旋系统，适当的树相变更加复杂，因为存在树唯一性阈值在 $\mathrm{\Delta }$ 中不是单调的模型。 因此，正如 [LLY13] 所考虑的那样，适当的概念是“最高$\mathrm{\Delta }$唯一性”。 粗略地说，如果对于每个整数 $\mathrm{\ell }\ge 1$，距离 $\mathrm{\ell }$ 处的所有顶点，我们说间隙 $\delta \in (0,1)$ 的唯一性在 $d$ 正则树上成立> 从根开始对根的边缘有总的“影响”$\lesssim {(1-\delta )}^{\mathrm{\ell }}$。 如果带有间隙 $\delta$ 的唯一性在所有 $d$ 常规树上成立，则我们说最多 $\mathrm{\Delta }$ 带有间隙 $\delta$ 的唯一性成立$1\le d\le \mathrm{\Delta }$;准确定义请参见部分 2。

1和2都是以下一般快速混合结果的推论，该结果适用于整个树独特性区域中的一般反铁磁$2$自旋系统。

Theorem 3 （一般反铁磁$2$-自旋系统）。

令 $\mathrm{\Delta }\ge 3$ 为整数，$\delta \in (0,1)$。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$。 假设参数 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，间隙为 $\delta$。 然后对于最大度$\mathrm{\Delta }$的每个$n$-顶点图$G$，反铁磁$2$-自旋的格劳伯动力学的混合时间$G$ 上带有参数 $(\beta ,\gamma ,\lambda )$ 的系统是 $O(n^{2+72/\delta })$。

我们还匹配了铁磁 2-自旋模型的现有相关衰减结果[GL18, SS20]；结果请参见部分8，以及附录F 为证明。

1.1电位法混合

树递归在近似计数的研究中非常有用。 考虑一棵以 $r$ 为根的树。假设 $r$ 有 $d$ 子级，用 $v_1,\mathrm{\dots },v_d$ 表示。 对于 $1\le i\le {\mathrm{\Delta }}_i$，我们将 $T_{v_i}$ 定义为以 $v_i$ 为根的 $T$ 的子树，其中包含 $v_i$ 的所有后代。 让 $$Rr=μT​(σr​ = ​1)/μT​(σr​ = ​0) 表示根的边际比率，并且 $$Rvi=μTvi​(σvi​ = ​1)/μTvi​(σvi​ = ​0) 对于每个子树。 由于$T_{v_i}$的独立性，树递归是一个在给定$R_{v_1},\mathrm{\dots },R_{v_d}$的情况下计算$R_r$的公式。 更具体地说，我们可以编写 $R_r=F_d(R_{v_1},\mathrm{\dots },R_{v_d})$，其中 $F_d:{[0,+\mathrm{\infty }]}^d\to [0,+\mathrm{\infty }]$ 是一个多元函数，对于 $(x_1,\mathrm{\dots },x_d)\in {[0,+\mathrm{\infty }]}^d$，

$$F_d(x_1,\mathrm{\dots },x_d)=\lambda \prod _{i=1}^d\frac{\beta x_i+1}{x_i+\gamma }.$$

然而，在本文中，我们特别关注边际比率的对数。 原因是我们要仔细研究[ALO20]中介绍的吉布斯分布${\mu }_G$的成对影响矩阵 ${ℐ}_G$并定义为每个 $r,v\in V$

$${ℐ}_G(r\to v)={\mu }_G({\sigma }_v=1\mid {\sigma }_r=1)-{\mu }_G({\sigma }_v=1\mid {\sigma }_r=0).$$

在[ALO20]中，作者表明，如果${ℐ}_G$的最大特征值有适当的界限，那么格劳伯动力学就是快速混合。 我们在本文中做出的一个重要观察是，影响 $$ℐG​(r​ → ​v) $v$ 上的 $r$ 可以被视为 $\log R_r$ 相对于 $v$ 处的日志外部字段的导数（参见 12 因此，我们使用对数比率更方便。 为此，我们将树递归重写为 $\log R_v=H_d(\log R_{v_1},\mathrm{\dots },\log R_{v_d})$，其中 $H_d:{[-\mathrm{\infty },+\mathrm{\infty }]}^d\to [-\mathrm{\infty },+\mathrm{\infty }]$ 是一个函数，对于 $(y_1,\mathrm{\dots },y_d)\in {[-\mathrm{\infty },+\mathrm{\infty }]}^d$，

$$H_d(y_1,\mathrm{\dots },y_d)=\log \lambda +\sum _{i=1}^d\log \left(\frac{\beta e^{y_i}+1}{e^{y_i}+\gamma }\right).$$

观察$H=\log \circ F\circ \exp$。 此外，我们定义

$$h(y)=-\frac{(1-\beta \gamma )e^y}{(\beta e^y+1)(e^y+\gamma )}$$

对于 $y\in [-\mathrm{\infty },+\mathrm{\infty }]$，以便 $\frac{\partial }{\partial y_i}{H}_d(y_1,\mathrm{\dots },y_d)=h(y_i)$ 对于每个 $i$。

为了证明我们的主要结果，我们使用了已广泛用于建立相关性衰减的势方法。 通过为对数比率选择合适的势函数，我们表明给定顶点的总影响随着距离呈指数衰减，从而建立了格劳伯动力学的快速混合。 让我们首先明确我们对潜力的要求。 对于每个整数 $d\ge 0$，我们定义一个有界区间 $J_d$，其中包含 $d$ 度顶点处的所有对数比率。更具体地说，当 时，我们让 $J_d=[\log (\lambda {\beta }^d),\log (\lambda /{\gamma }^d)]$ ；当 $\beta \gamma >1$ 时，我们让 $J_d=[\log (\lambda /{\gamma }^d),\log (\lambda {\beta }^d)]$ 。 此外，将$J={\bigcup }_{d=0}^{\mathrm{\Delta }-1}{J}_d$定义为包含次数小于$\mathrm{\Delta }$的所有对数比率的区间。

Definition 4 ($(\alpha ,c)$-势函数).

令 $\mathrm{\Delta }\ge 3$ 为整数。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$和$\lambda >0$。 令 $\mathrm{\Psi }:[-\mathrm{\infty },+\mathrm{\infty }]\to (-\mathrm{\infty },+\mathrm{\infty })$ 为具有图像 $S=\mathrm{\Psi }[-\mathrm{\infty },+\mathrm{\infty }]$ 和导数 $\psi ={\mathrm{\Psi }}^{\prime }$ 的可微且递增函数。 对于任意 $\alpha \in (0,1)$ 和 $c>0$，如果 $\mathrm{\Psi }$ 满足以下条件，我们就说它是关于 $\mathrm{\Delta }$ 和 $(\beta ,\gamma ,\lambda )$ 的 $(\alpha ,c)$ 势函数：

1. （收缩）对于每个整数 $d$ 使得 和每个 $({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\in S^d$，我​​们有

   $${\Vert \nabla H_d^{\mathrm{\Psi }}({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\Vert }_1=\sum _{i=1}^d\frac{\psi (y)}{\psi (y_i)}\cdot |h(y_i)|\le 1-\alpha$$

   其中 $H_d^{\mathrm{\Psi }}=\mathrm{\Psi }\circ H_d\circ {\mathrm{\Psi }}^{-1}$、$y_i={\mathrm{\Psi }}^{-1}({\tilde{y}}_i)$ 为 $1\le i\le d$，以及$y=H_d(y_1,\mathrm{\dots },y_d)$。

2. （有界）对于每个$y_1,y_2\in J$，我们有

   $$\frac{\psi (y_2)}{\psi (y_1)}\cdot \left|h(y_1)\right|\le \frac{c}{\mathrm{\Delta }}.$$

在$(\alpha ,c)$-势的定义中，应该将$y$视为顶点处的对数边际比，势函数为$\log R$。 以下定理在给定 $(\alpha ,c)$-势函数的情况下建立了格劳伯动力学的快速混合。

Theorem 5。

令 $\mathrm{\Delta }\ge 3$ 为整数。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$和$\lambda >0$。 假设对于某些 $\alpha \in (0,1)$ 和 $c>0$，存在相对于 $\mathrm{\Delta }$ 和 $(\beta ,\gamma ,\lambda )$ 的 $(\alpha ,c)$ 势。 然后对于最大度$\mathrm{\Delta }$的每个$n$-顶点图$G$,$2$-自旋系统的格劳伯动力学的混合时间带有参数 $(\beta ,\gamma ,\lambda )$ 的 $G$ 是 $O(n^{2+c/\alpha })$。

我们在部分3中概述了我们的证明。 请注意，在 4 和 5 中，常数 $c$ 允许依赖于最大度数 $\mathrm{\Delta }$ 和参数 $(\beta ,\gamma ,\lambda )$ 总的来说。 例如，对 [LLY13] 中的势进行简单的黑盒应用将为 有界性 条件提供 $c=\mathrm{\Theta }(\mathrm{\Delta })$，从而产生 $n^{\mathrm{\Theta }(\mathrm{\Delta })}$ 混合。 然而，这对于具有潜在无限度数的图来说是不可取的。 我们的贡献之一在于，我们证明了 Boundedness 条件在一个通用常数 $c$ 与 $\mathrm{\Delta }$ 和 $(\beta ,\gamma ,\lambda )$ 无关的情况下成立。 因此，我们的混合时间是 $O(n^{2+c/\delta })$，除了 $1/\delta$ 之外，指数中没有任何参数。

在部分7中，我们给出了$(\alpha ,c)$-势的稍微更一般的定义，它放宽了有界性 条件，并且对于我们分析具有 的反铁磁 $2$ 自旋系统是必要的。 5 对于这一更大类的势仍然成立。

我们注意到，在潜在方法的所有先前工作中，结果和证明总是以 $F_d$、$R$ 的树递归和 $\mathrm{\Phi }$ 的形式呈现， $R$ 的潜在函数。事实上，我们的结果也可以翻译成$(F_d,\mathrm{\Phi })$的语言。 要看到这一点，从$H_d=\log \circ F_d\circ \exp$开始，如果我们选择$\mathrm{\Phi }=\mathrm{\Psi }\circ \log$，则可以直接检查$H_d^{\mathrm{\Psi }}=\mathrm{\Psi }\circ H_d\circ {\mathrm{\Psi }}^{-1}=\mathrm{\Phi }\circ F_d\circ {\mathrm{\Phi }}^{-1}=F_d^{\mathrm{\Phi }}$，从而检查$\nabla H_d^{\mathrm{\Psi }}=\nabla F_d^{\mathrm{\Phi }}$。 这意味着当且仅当相应的收缩条件对于$(F_d,\mathrm{\Phi })$成立时，4中的收缩条件对于$(H_d,\mathrm{\Psi })$成立。 有界性条件也可以等效地表述为$(F_d,\mathrm{\Phi })$。 尽管如此，在本文中我们选择使用 $(H_d,\mathrm{\Psi })$ 出于以下两个原因。 首先，正如前面提到的，事实是 $$ℐG​(r​ → ​v) 是 $\log R_r$ 的导数，因此可以很自然地考虑对数比率的树递归。 事实上，直接使用 $(H_d,\mathrm{\Psi })$ 呈现我们的结果和证明比切换到 $(F_d,\mathrm{\Phi })$ 更容易、更清晰。 其次，我们将使用的势函数 $\mathrm{\Psi }$ 是通过转换 $\mathrm{\Psi }=\mathrm{\Phi }\circ \exp$ 从 [LLY13] 中的精确势 $\mathrm{\Phi }$ 获得的。 有趣的是，这个势能的导数就是$\psi =\sqrt{|h|}$。 那么收缩条件有一个很好的形式：${\sum }_{i=1}^d\sqrt{h(y)h(y_i)}\le 1-\alpha$； Boundedness 条件仅涉及 $h(y)$ 的上限。 这似乎揭示了 [LLY13] 中神秘的势函数 $\mathrm{\Phi }$，并且还表明 $H_d$ 是树递归的一个有意义的变体考虑。 再添加一个证据，对于很多情况（例如，)，选择了潜在的$\mathrm{\Phi }=\log$，这仅仅意味着我们可以选择$\mathrm{\Psi }$恒等函数和 $H_d$ 本身正在收缩，没有任何不平凡的潜力。

2021 年 7 月修订。

这篇论文在 FOCS 2020 上发表后，在[LLY13]中发现了关于反铁磁二自旋系统唯一性区域描述的一个小错误。 该错误已在最新版本的[LLY13]中修复。 在本次修订中，我们更新了部分7和附录E中相应的结果和证明 依赖于 [LLY13] 中的更改；特别地，36根据当前唯一性区域的描述进行调整。 我们指出，这些变化纯粹是技术性的，不会影响我们主要结果（例如5)的有效性。

致谢。

我们要感谢 Shayan Oveis Gharan 和 Nima Anari 激发了讨论。 我们也感谢匿名审稿人提出的有益的意见和建议。 我们感谢 Yitong Yin 与我们沟通[LLY13]的最新更新，并提供有关修改附录中的陈述和结果证明的有用说明E，特别是36。

2 预赛

混合时间和光谱间隙

令 $P$ 为具有平稳分布 $\mu$ 的有限状态空间 $\mathrm{\Omega }$ 上遍历（即不可约且非周期）马尔可夫链的转移矩阵。 让$P^t(x_0,\cdot )$表示从$x_0\in \mathrm{\Omega }$开始的$t$步之后链的分布。 $P$的混合时间定义为

$$T_{\mathrm{mix}}(P)=\underset{x_0\in \mathrm{\Omega }}{\max }\min \left\{t\ge 0:{\Vert P^t(x_0,\cdot )-\mu (\cdot )\Vert }_{\mathrm{TV}}\le \frac{1}{4}\right\}.$$

如果$\mu (x)P(x,y)=\mu (y)P(y,x)$对于所有$x,y\in \mathrm{\Omega }$，我们说$P$是可逆的。 如果$P$是可逆的，则$P$只有实特征值，可用$1={\lambda }_1\ge \mathrm{\cdots }\ge {\lambda }_{|\mathrm{\Omega }|}\ge -1$表示。 $P$的光谱间隙定义为$1-{\lambda }_2$,$P$的绝对光谱间隙为定义为${\lambda }^{\ast }(P)=1-\max \{|{\lambda }_2|,|{\lambda }_{|\mathrm{\Omega }|}|\}$。 如果 $P$ 相对于内积 ${⟨\cdot ,\cdot ⟩}_{\mu }$ 也是半正定的，则​​ $P$ 的所有特征值都是非负的，因此 ${\lambda }^{\ast }(P)=1-{\lambda }_2$ 也是非负的。 最后，混合时间和绝对光谱间隙的关系为

$$T_{\mathrm{mix}}(P)\le \frac{1}{{\lambda }^{\ast }(P)}\log \left(\frac{4}{{\min }_{x\in \mathrm{\Omega }}\mu (x)}\right).$$ (1)

独特性

令 $\mathrm{\Delta }\ge 3$ 为整数或 $\mathrm{\Delta }=\mathrm{\infty }$。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$。 对于 ，定义

$$f_d(R)=\lambda {\left(\frac{\beta R+1}{R+\gamma }\right)}^d$$

并用$R_d^{\ast }$表示$f_d$的唯一不动点。 对于$\delta \in (0,1)$，我们说参数$(\beta ,\gamma ,\lambda )$是up-to-$\mathrm{\Delta }$唯一的，间隙$\delta$如果 对于所有 。

比例及影响力

考虑图 $G=(V,E)$ 上的 $2$-自旋系统。 让 $\mathrm{\Lambda }\subseteq V$ 和 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$。 对于所有$v\in V\backslash \mathrm{\Lambda }$，我们将$v$处的边际比率定义为

$$R_G^{{\sigma }_{\mathrm{\Lambda }}}(v)=\frac{{\mu }_G({\sigma }_v=1\mid {\sigma }_{\mathrm{\Lambda }})}{{\mu }_G({\sigma }_v=0\mid {\sigma }_{\mathrm{\Lambda }})}.$$

对于所有$u,v\in V\backslash \mathrm{\Lambda }$，我们定义$u$对$v$的（成对）影响：

$${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(u\to v)={\mu }_G({\sigma }_v=1\mid {\sigma }_u=1,{\sigma }_{\mathrm{\Lambda }})-{\mu }_G({\sigma }_v=1\mid {\sigma }_u=0,{\sigma }_{\mathrm{\Lambda }}).$$

为（成对）影响矩阵编写${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}$，其条目由下式给出 $$ℐGσΛ​ (u​ → ​v).

韦茨的自回避行走树

令 $G=(V,E)$ 为连通图，$r\in V$ 为 $G$ 的顶点。 自回避行走（SAW）树定义如下。 假设顶点集$V$存在全序。从 $r$ 出发的自回避步行是一条路径 $r=v_0-v_1-\mathrm{\cdots }-v_{\mathrm{\ell }}$，使得所有 都具有 $v_i\ne v_j$。 SAW树$T_{\text{saw}}(G,r)$是一棵以$r$为根的树，由所有带有$\mathrm{deg}(v_{\mathrm{\ell }})=1$的自回避行走$r=v_0-v_1-\mathrm{\cdots }-v_{\mathrm{\ell }}$以及附加的关闭循环的又一个顶点（即 $r=v_0-v_1-\mathrm{\cdots }-v_{\mathrm{\ell }}-v_i$ 对于某些 $0\le i\le \mathrm{\ell }-2$ ，例如 $\{v_{\mathrm{\ell }},v_i\}\in E$)。 请注意，$G$ 的顶点可能在 SAW 树中具有多个副本，并且除了叶子之外，顶点的度数将被保留。 请参阅图1了解示例。

我们可以使用相同的参数$(\beta ,\gamma ,\lambda )$在$T_{\text{saw}}(G,r)$上定义一个$2$-自旋系统，其中一些叶子被固定到特定的自旋。 更具体地说，对于附加了 $v_i$ 的自回避行走 $r=v_0-v_1-\mathrm{\cdots }-v_{\mathrm{\ell }}$，我们将 $v_i$ 修复为旋转 $1$ 如果 相对于 $V$ 上的总排序，如果 $v_{i+1}>v_{\mathrm{\ell }}$ 则旋转 $0$。 对于每个 $v\in V$，我们用 ${𝒞}_v$ 表示 $T_{\text{saw}}(G,r)$ 中 $v$ 的所有自由（未固定）副本的集合。 对于 $\mathrm{\Lambda }\subseteq V$ 和部分配置 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$，我们通过将自旋 ${\sigma }_v$ 分配给 $v$ 的每个副本 $\widehat{v}$ 从 ${𝒞}_v$ 开始，并删除 $\widehat{v}$ 的所有后代，为每个 $v\in \mathrm{\Lambda }$ 定义具有条件 ${\sigma }_{\mathrm{\Lambda }}$ 的 SAW 树。 请注意，一般来说，来自 ${𝒞}_v$ 的 $v$ 的不同副本可以接收不同的自旋分配。 最后，如果每个顶点 $v$ 都有不同的字段 ${\lambda }_v$，则来自 ${𝒞}_v$ 的 $v$ 的所有副本都将具有相同的字段SAW 树中的 ${\lambda }_v$。

图1： 图 $G$ 和以 $r$ 为根的自回避游走树 $T_{\text{saw}}(G,r)$。 $T_{\text{saw}}(G,r)$ 中具有相同标签的顶点是 $G$ 中相同顶点的副本。 ($\mathrm{●}$/$\mathrm{○}$：固定为旋转$1$/$0$。）

3 主要结果的证明大纲

步骤 1 ([ALO20])：光谱独立意味着快速混合。

我们的证明建立在[ALO20]的基础上，他证明了从最大程度图上的硬核分布中采样的格劳伯动力学最多$\mathrm{\Delta }$混合在$O(n^{\exp (O(1/\delta ))})$步中每当 $\lambda \le (1-\delta ){\lambda }_c(\mathrm{\Delta })$ 时。 他们证明的关键要素之一是他们称之为谱独立性的概念。 [ALO20]表明光谱独立性意味着快速混合。 请注意，${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}$ 的对角线条目是 $1$，而不是 [ALO20] 中原始定义中的 $0$。

Definition 6 （谱独立性[ALO20])。

我们说 $n$ 顶点图 $G$ 上的吉布斯分布 ${\mu }_G$ 与 $({\eta }_0,\mathrm{\dots },{\eta }_{n-2})$ 谱无关，如果对于大小为 $k$ 和 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 的每个 $0\le k\le n-2$、$\mathrm{\Lambda }\subseteq V$，都有 ${\lambda }_{\max }({ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}})-1\le {\eta }_k$。

Theorem 7 ([ALO20]).

如果 $\mu$ 是一个 $({\eta }_0,\mathrm{\dots },{\eta }_{n-2})$ 谱独立分布，则从 $\mu$ 采样的格劳伯动力学至少具有谱间隙

$$\frac{1}{n}\prod _{i=0}^{n-2}\left(1-\frac{{\eta }_i}{n-i-1}\right).$$

我们现在的主要目标是限制 ${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}$ 的最大特征值。

步骤 2：自我回避行走树保留影响。

从标准线性代数，我们知道 ${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}$ 的最大特征值的上限是 $1$-范数 $$‖ℐGσΛ‖10>=1>maxrεV​ ΣvεV|ℐGσΛ​ (v​ → ​r)|，对应于顶点 $r$ 的总影响，以及无穷范数 $$‖ℐGσΛ‖∞0>=1>maxrεV​ ΣvεV|ℐGσΛ​ (r​ → ​v)|，对应于$r$的总影响。在[ALO20]中，作者使用${\Vert {ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}\Vert }_1$作为${\lambda }_{\max }({ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}})$的上限。 粗略地说，他们证明了在所有边界条件下，固定顶点 $r$ 上的绝对影响总和的上限是以 $r$ 为根的自避让行走树中 $r$ 上的最大绝对影响。 在本文中，我们将使用 ${\Vert {ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}\Vert }_{\mathrm{\infty }}$ 来代替上限 ${\lambda }_{\max }({ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}})$。 事实上，如果我们看看自回避树中 $r$ 的影响，则事实更多。 我们证明对于每个顶点$v\in V$，影响 $$ℐGσΛ​ (r​ → ​v) $G$中的内容以影响力总和的形式保存在以$r$为根的自回避游走树$T=T_{\text{saw}}(G,r)$中 $$ℐTσΛ​ (r​ → ​v^) $v$ 的所有副本 $\widehat{v}$。

我们建立这一事实的方法是将配分函数视为 $\lambda$ 中的多项式。 事实上，考虑每个 $v\in V$ 具有任意外部字段 ${\lambda }_v$ 的更一般情况将很有用。 让 $𝝀=\{{\lambda }_v:v\in V\}$ 表示字段。 对于$\mathrm{\Lambda }\subseteq V$和${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$，以${\sigma }_{\mathrm{\Lambda }}$为条件的$\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}$的权重定义为$w_G(\sigma \mid {\sigma }_{\mathrm{\Lambda }})={\beta }^{m_1(\sigma \mid {\sigma }_{\mathrm{\Lambda }})}{\gamma }^{m_0(\sigma \mid {\sigma }_{\mathrm{\Lambda }})}{\prod }_{v\in V\backslash \mathrm{\Lambda }}{\lambda }_v^{{\sigma }_v}$，其中$m_i(\cdot \mid {\sigma }_{\mathrm{\Lambda }})$ 是 $i=0,1$ 的 $V\backslash \mathrm{\Lambda }$ 中至少有一个端点的 $i$-$i$ 边的数量。 此外，$Z_G^{{\sigma }_{\mathrm{\Lambda }}}={\sum }_{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}{w}_G(\sigma \mid {\sigma }_{\mathrm{\Lambda }})$是以${\sigma }_{\mathrm{\Lambda }}$为条件的配分函数。 我们将$\beta$和$\gamma$视为一些固定常量，并将$𝝀$视为$n=|V|$变量。 从这个意义上说，我们将权重$w_G(\sigma \mid {\sigma }_{\mathrm{\Lambda }})$视为$𝝀$中的单项式，将配分函数$Z_G^{{\sigma }_{\mathrm{\Lambda }}}$视为$𝝀$中的多项式。 此外，边际比率$R_G^{{\sigma }_{\mathrm{\Lambda }}}(v)$及其影响 $$ℐGσΛ​ (r​ → ​v) for $r,v\in V$ 都是 $𝝀$ 中的函数。 我们的主要结果是 $G$ 的配分函数除以每个 $r\in V$ 的 $T_{\text{saw}}(G,r)$ 的配分函数。 由此，我们表明 SAW 树保留了根的影响，并重新建立了 Weitz 的著名结果[Wei06]，请参阅13。

Lemma 8.

令 $G=(V,E)$ 为连通图，$r\in V$ 为顶点，$\mathrm{\Lambda }\subseteq V\backslash \{r\}$ 使得 $G\backslash \mathrm{\Lambda }$ 连通。 令$T=T_{\text{saw}}(G,r)$为以$r$为根的$G$的自回避游走树。然后对于每个${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$,$Z_G^{{\sigma }_{\mathrm{\Lambda }}}$除以$Z_T^{{\sigma }_{\mathrm{\Lambda }}}$。 更准确地说，存在一个独立于 ${\lambda }_r$ 的多项式 $P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}(𝛌)$，使得

$Z_T^{{\sigma }_{\mathrm{\Lambda }}}=Z_G^{{\sigma }_{\mathrm{\Lambda }}}\cdot P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}.$ (2)

作为推论，对于每个顶点 $v\in V$，

${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)={\displaystyle \sum _{\widehat{v}\in {𝒞}_v}}{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to \widehat{v}),$ (3)

其中 ${𝒞}_v$ 是 $T$ 中 $v$ 的所有自由（未固定）副本的集合。

Remark 1。

我们强调，为了限定 $G$ 中顶点的总影响，只需要 Eq. 3 的 8，这可以用纯粹的组合方式证明。 然而，我们相信$G$的多元配分函数的整除性Eq. 2及其自回避游走树可能具有独立的兴趣。

我们注意到，整除性语句 Eq. 2 的单变量版本已经出现在 [Ben18] 中配分函数复数根研究中的硬核模型和零场伊辛模型的[LSS19]。 从8，我们可以得到 ${\Sigma }_{v\epsilon V}|$ℐGσΛ​ (r​ → ​v)|≤ΣvεVT |ℐTσΛ​ (r​ → ​v)| 对于任何固定的$r$。这意味着，我们只需要对树的所有影响力之和设置上限，即可获得 ${\lambda }_{\max }({ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}})$ 的上限。

第三步：给予良好潜力的影响力的衰减。

树递归为我们提供了一个很好的工具来递归计算树的顶点（对数）比率。 正如我们在 12 中所示，影响 $$ℐGσΛ​ (r​ → ​v) 实际上是 $r$ 处对数边际比的导数版本。因此，可以自然地使用树递归来关联这些影响。 然后，我们应用势方法（该方法已在文献中广泛使用）来建立相关性的衰减（强空间混合）。 下面的引理表明，对距离 $k$ 的绝对影响之和随 $k$ 呈指数衰减，可以将其视为成对影响的衰减。

Lemma 9.

如果存在关于$\mathrm{\Delta }$和$(\beta ,\gamma ,\lambda )$的$(\alpha ,c)$-潜在函数$\mathrm{\Psi }$，其中$\alpha \in (0,1)$和$c>0$，然后对于每个 $\mathrm{\Lambda }\subseteq V_T\backslash \{r\}$、${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 和所有整数 $k\ge 1$，

$$\sum _{v\in L_r(k)}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|\le c\cdot {(1-\alpha )}^{k-1}$$

其中$L_r(k)$表示距$r$距离为$k$的所有自由顶点的集合。

然后通过组合7、8和9来证明5。 我们将其证明留给附录A。

第四步：找到好的潜力。

作为最后一步，我们需要找到 4 中定义的 $(\alpha ,c)$ 势函数。 我们选择的潜在$\mathrm{\Psi }$正是来自[LLY13]的那个，适应对数边际比率和树递归$H$（参见部分6了解更多详情）。 我们证明，如果参数 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，且有间隙 $\delta \in (0,1)$ 以及 $\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 或 $\gamma \le 1$，则 $\mathrm{\Psi }$ 是 $(\alpha ,c)$ 势。

Lemma 10.

令 $\mathrm{\Delta }\ge 3$ 为整数。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$。 假设 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，间隙为 $\delta \in (0,1)$。 隐式定义函数 $\mathrm{\Psi }$

$${\mathrm{\Psi }}^{\prime }(y)=\psi (y)=\sqrt{\frac{(1-\beta \gamma )e^y}{(\beta e^y+1)(e^y+\gamma )}}=\sqrt{\left|h(y)\right|},\mathrm{\Psi }(0)=0.$$ (4)

如果$\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$，则$\mathrm{\Psi }$是具有$\alpha \ge \delta /2$和$c\le 1.5$的$(\alpha ,c)$势函数。 如果 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma \le 1$，那么 $\mathrm{\Psi }$ 与 $\alpha \ge \delta /2$ 和 $c\le 18$ 是一个 $(\alpha ,c)$ 电位；如果 $\beta =0$，我们可以进一步取 $c\le 4$。

我们从 5 和 10 推断出 $\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 或 $\gamma \le 1$ 情况的 3。 其证明可参见附录A。 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma >1$ 的情况比较棘手。 正如[LLY13]第5节所讨论的，当$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$和$\gamma >1$时，对于某些$\lambda >0$，自旋系统在于唯一性任意图的区域，即使具有无界度（即，最多 $\mathrm{\infty }$ 唯一）。 因此，在这种情况下，顶点的总影响可能与 $\mathrm{\Theta }(\mathrm{\Delta }/\delta )$ 一样大，从而导致 $n^{\mathrm{\Theta }(\mathrm{\Delta }/\delta )}$ 混合时间。 为了解决这个问题，我们考虑固定顶点的绝对影响的适当加权总和，这也是影响矩阵的最大特征值的上限。 然后将 4 和 5 修改为稍强的版本。 本案的陈述及证据载于部分7及附录D。

本文的其余部分安排如下。 在部分4中，我们证明了8关于SAW树的属性。 在部分 5中，我们建立了关于势法影响衰减的9。 我们验证部分6中的收缩条件以选择势能。 部分 7专门讨论$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$和$\gamma >1$的情况，其中更通用的版本需要 4 和 5；缺失的证明可以在附录0>D1>中找到。在附录3>E4>2>中，我们验证了有界性5>条件及其在所有情况下对我们潜力的概括。 我们在部分 8中考虑铁磁自旋系统，证明留给附录 F 。我们在附录A中证明了我们的所有主要结果。

4 保留自回避行走树的影响

在本节中，我们将展示[Wei06]中介绍的自回避行走（SAW）树（另见[SS05])，保留了根的所有影响，从而建立8。 为此，我们将 $G$ 的配分函数（视为外部字段 $𝝀$ 的多项式）除以 SAW 树的配分函数。 由此我们证明根顶点 $r$ 对 $G$ 中另一个顶点 $v$ 的影响与对 $v$ 使用我们的证明方法，我们表明根的边缘保留在 SAW 树中，重新建立了 Weitz 著名的结果 [Wei06]，以及与 $v$ 相关的所有成对协方差> 被保留。

Theorem 11.

令 $G=(V,E)$ 为连通图，$r\in V$ 为顶点，$\mathrm{\Lambda }\subseteq V\backslash \{r\}$ 使得 $G\backslash \mathrm{\Lambda }$ 连通。 令$T=T_{\text{saw}}(G,r)$为以$r$为根的$G$的自回避游走树。然后对于每个${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$,$Z_G^{{\sigma }_{\mathrm{\Lambda }}}$除以$Z_T^{{\sigma }_{\mathrm{\Lambda }}}$。 更准确地说，存在一个多项式 $P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}(𝛌)$ 使得

$$Z_T^{{\sigma }_{\mathrm{\Lambda }}}=Z_G^{{\sigma }_{\mathrm{\Lambda }}}\cdot P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}.$$

此外，多项式$P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}$独立于${\lambda }_r$。

Remark 2。

对 11 的证明可以进行调整，以给出 Eq. 3 中 8 的纯组合证明。 就像在[Wei06，定理3.1]的证明中一样，我们可以通过顶点分裂和伸缩来进行，其中不是伸缩边际比率的乘积，而是伸缩单顶点影响的总和。

我们注意到，[Ben18] 证明了硬核模型的 11 的单变量版本，而 [LSS19] 对于零模型显示了类似的结果。具有均匀边缘权重的伊辛场模型。 我们的结果适用于所有 $2$ 自旋系统和每个顶点的任意字段。 我们还可以以简单的方式将其推广到每条边的任意边权重。 至关重要的是，商多项式$P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}$与根处的场${\lambda }_r$无关，由此我们可以立即推导出根的边际保留和影响。

在证明11之前，我们首先给出它的一些结果。 对于所有 $u,v\in V\backslash \mathrm{\Lambda }$，我们将 $v$ 处的 marginal 定义为 $$MGσΛ​(v0>)1>=2>μG​(v​ = ​1∣σΛ) （为了方便起见，我们将事件 ${\sigma }_v=i$ 写为 $v=i$)，以及 $u$ 和 $v$ 的 协方差 > 作为

$$K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,v)={\mu }_G(u=v=1\mid {\sigma }_{\mathrm{\Lambda }})-{\mu }_G(u=1\mid {\sigma }_{\mathrm{\Lambda }}){\mu }_G(v=1\mid {\sigma }_{\mathrm{\Lambda }}).$$

以下引理将我们感兴趣的量与（对数）配分函数的适当导数联系起来。 引理的第一部分和第二部分是民间传说。

Lemma 12.

对于每个图 $G=(V,E)$、$\mathrm{\Lambda }\subseteq V$ 和 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$，以下内容成立：

1. 对于所有$v\in V$,

   $$\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)\log Z_G^{{\sigma }_{\mathrm{\Lambda }}}=M_G^{{\sigma }_{\mathrm{\Lambda }}}(v);$$

2. 对于所有$u,v\in V$,

   $$\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)\left({\lambda }_u\frac{\partial }{\partial {\lambda }_u}\right)\log Z_G^{{\sigma }_{\mathrm{\Lambda }}}=\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)=K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,v);$$

3. 对于所有$u,v\in V$,

   $$\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)\log R_G^{{\sigma }_{\mathrm{\Lambda }}}(u)={ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(u\to v).$$

证明。

前两部分是标准的。 为了完整性，我们将这两个事实的证明包含在附录B中。 对于第 3 部分，我们从第 2 部分推断出

$\left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\log R_G^{{\sigma }_{\mathrm{\Lambda }}}(u)=\left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\log \left({\displaystyle \frac{M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)}{1-M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)}}\right)={\displaystyle \frac{\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)}{M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)\left(1-M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)\right)}}={\displaystyle \frac{K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,v)}{K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,u)}}.$

仍有待证明的是

$${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(u\to v)=\frac{K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,v)}{K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,u)},$$

这实际上适用于任何两个二元随机变量。 为了看到这一点，我们首先计算 $$KGσΛ​(0>u1>,2>u3>)4>⋅5>ℐ7>G8>σ0>Λ1>9>6>​2>(u​ → ​v) 根据定义：

$K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,u)\cdot {ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(u\to v)$

$=$ ${\mu }_G(u=1\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(u=0\mid {\sigma }_{\mathrm{\Lambda }})\cdot \left[{\mu }_G(v=1\mid u=1,{\sigma }_{\mathrm{\Lambda }})-{\mu }_G(v=1\mid u=0,{\sigma }_{\mathrm{\Lambda }})\right]$

$=$ ${\mu }_G(u=1,v=1\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(u=0\mid {\sigma }_{\mathrm{\Lambda }})-{\mu }_G(u=1\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(u=0,v=1\mid {\sigma }_{\mathrm{\Lambda }})$

$=$ ${\mu }_G(u=1,v=1\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(u=0,v=0\mid {\sigma }_{\mathrm{\Lambda }})-{\mu }_G(u=1,v=0\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(u=0,v=1\mid {\sigma }_{\mathrm{\Lambda }}).$

同时，协方差可以写为

$K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,v)$ $={\mu }_G(u=1,v=1\mid {\sigma }_{\mathrm{\Lambda }})-{\mu }_G(u=1\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(v=1\mid {\sigma }_{\mathrm{\Lambda }})$

$={\mu }_G(u=1,v=1\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(u=0,v=0\mid {\sigma }_{\mathrm{\Lambda }})-{\mu }_G(u=1,v=0\mid {\sigma }_{\mathrm{\Lambda }})\cdot {\mu }_G(u=0,v=1\mid {\sigma }_{\mathrm{\Lambda }}).$

这表明 $$ℐGσΛ​ (u​ → ​v)=KGσ Λ​0>(2>u3>,4>v5>)6>1>/7>K9>G0>σ2>Λ3>1>8>​4>(6>u7>,8>u9>)0>5> 从而确立了第 3 部分。 ∎

我们从 11 和以下引理的第二项推导出 8。 11的证明在节4.1中给出。

Lemma 13.

令 $G=(V,E)$ 为连通图，$r\in V$ 为顶点，$\mathrm{\Lambda }\subseteq V\backslash \{r\}$ 使得 $G\backslash \mathrm{\Lambda }$ 连通。 令$T=T_{\text{saw}}(G,r)$为以$r$为根的$G$的自回避游走树。那么对于每个 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 我们有：

1. ([Wei06，定理3.1])根边缘的保留 $r$:

   $$M_G^{{\sigma }_{\mathrm{\Lambda }}}(r)=M_T^{{\sigma }_{\mathrm{\Lambda }}}(r)\text{and}{R}_G^{{\sigma }_{\mathrm{\Lambda }}}(r)=R_T^{{\sigma }_{\mathrm{\Lambda }}}(r);$$

2. 保留协方差和影响$r$：对于每个$v\in V$,

   $$K_G^{{\sigma }_{\mathrm{\Lambda }}}(r,v)=\sum _{\widehat{v}\in {𝒞}_v}{K}_T^{{\sigma }_{\mathrm{\Lambda }}}(r,\widehat{v})\text{and}{ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)=\sum _{\widehat{v}\in {𝒞}_v}{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to \widehat{v}).$$

   其中，${𝒞}_v$是$v$在$T$.中的所有自由（非固定）副本的集合。

证明。

到11，存在多项式$P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}(𝝀)$，使得$Z_T^{{\sigma }_{\mathrm{\Lambda }}}=Z_G^{{\sigma }_{\mathrm{\Lambda }}}\cdot P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}$和$P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}$独立于${\lambda }_r$。 那么从 12 可以得出

$$M_T^{{\sigma }_{\mathrm{\Lambda }}}(r)=\left({\lambda }_r\frac{\partial }{\partial {\lambda }_r}\right)\log Z_T^{{\sigma }_{\mathrm{\Lambda }}}=\left({\lambda }_r\frac{\partial }{\partial {\lambda }_r}\right)\left(\log Z_G^{{\sigma }_{\mathrm{\Lambda }}}+\log P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}\right)=\left({\lambda }_r\frac{\partial }{\partial {\lambda }_r}\right)\log Z_G^{{\sigma }_{\mathrm{\Lambda }}}=M_G^{{\sigma }_{\mathrm{\Lambda }}}(r),$$

因此$R_T^{{\sigma }_{\mathrm{\Lambda }}}(r)=R_G^{{\sigma }_{\mathrm{\Lambda }}}(r)$。 对于第二项，再次从 12 我们得到

$$K_G^{{\sigma }_{\mathrm{\Lambda }}}(r,v)=\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)M_G^{{\sigma }_{\mathrm{\Lambda }}}(r)=\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)M_T^{{\sigma }_{\mathrm{\Lambda }}}(r).$$

回想一下，对于 SAW 树 $T$ 上的自旋系统，来自 ${𝒞}_v$ 的 $v$ 的每个自由副本 $\widehat{v}$ 都具有相同的外部字段 ${\lambda }_{\widehat{v}}={\lambda }_v$。 然后，根据导数的链式法则和12，我们推导出

$$K_G^{{\sigma }_{\mathrm{\Lambda }}}(r,v)=\sum _{\widehat{v}\in {𝒞}_v}\left({\lambda }_{\widehat{v}}\frac{\partial }{\partial {\lambda }_{\widehat{v}}}\right)M_T^{{\sigma }_{\mathrm{\Lambda }}}(r)\cdot \frac{\partial {\lambda }_{\widehat{v}}}{\partial {\lambda }_v}\cdot \frac{{\lambda }_v}{{\lambda }_{\widehat{v}}}=\sum _{\widehat{v}\in {𝒞}_v}{K}_T^{{\sigma }_{\mathrm{\Lambda }}}(r,\widehat{v}).$$

最后，我们有

$${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)=\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)\log R_G^{{\sigma }_{\mathrm{\Lambda }}}(r)=\left({\lambda }_v\frac{\partial }{\partial {\lambda }_v}\right)\log R_T^{{\sigma }_{\mathrm{\Lambda }}}(r)=\sum _{\widehat{v}\in {𝒞}_v}{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to \widehat{v}),$$

其中最后一个等式如下。 ∎

4.1 11的证明

在提出证明之前，让我们首先回顾一下之前介绍的符号和定义。 用 $𝝀=\{{\lambda }_v:v\in V\}$ 表示所有顶点处的字段集。 对于$\mathrm{\Lambda }\subseteq V$和${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$，以${\sigma }_{\mathrm{\Lambda }}$为条件的$\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}$的权重由下式给出

$$w_G(\sigma \mid {\sigma }_{\mathrm{\Lambda }})={\beta }^{m_1(\sigma \mid {\sigma }_{\mathrm{\Lambda }})}{\gamma }^{m_0(\sigma \mid {\sigma }_{\mathrm{\Lambda }})}\prod _{v\in V\backslash \mathrm{\Lambda }}{\lambda }_v^{{\sigma }_v},$$

其中对于 $i=0,1$,$m_i(\cdot \mid {\sigma }_{\mathrm{\Lambda }})$ 表示两个端点都接收自旋 $i$ 且至少其中一个位于 $V\backslash \mathrm{\Lambda }$ 中的边数>。 以${\sigma }_{\mathrm{\Lambda }}$为条件的配分函数定义为$Z_G^{{\sigma }_{\mathrm{\Lambda }}}={\sum }_{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}{w}_G(\sigma \mid {\sigma }_{\mathrm{\Lambda }})$。 对于 SAW 树，我们以相同的方式定义条件权重和配分函数。 特别是，回想一下，当我们在 SAW 树上修复条件 ${\sigma }_{\mathrm{\Lambda }}$ 时，我们还会删除每个 $v\in \mathrm{\Lambda }$ 的 $\widehat{v}\in {𝒞}_v$ 的所有后代。

对于每个 $v\in V\backslash \mathrm{\Lambda }$ 和 $i\in \{0,1\}$，我们应编写 $v=i$ 来表示配置集，使得 ${\sigma }_v=i$ （即 $\{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}:{\sigma }_v=i\}$) 并让 $$ZGσΛ​ (v​ = ​我) 是所有配置的权重之和 $$v​ = ​我. 我们进一步扩展这个符号并写成 $$ZGσΛ​ (U​ = ​σU) 对于每个 $U\subseteq V\backslash \mathrm{\Lambda }$ 和 ${\sigma }_U\in {\{0,1\}}^U$。 对于 SAW 树，我们也采用相同的符号。

11 的证明。

我们将证明存在一个独立于 ${\lambda }_r$ 的多项式 $P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}(𝝀)$，使得

$$Z_T^{{\sigma }_{\mathrm{\Lambda }}}(r=1)=Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=1)\cdot P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}\text{and}{Z}_T^{{\sigma }_{\mathrm{\Lambda }}}(r=0)=Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=0)\cdot P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}.$$ (5)

方程 5的高级证明思路与[Wei06，定理3.1]中的相应结果类似>。 令 $m$ 为 $V\backslash \mathrm{\Lambda }$ 中至少有一个端点的边数。 我们对 $m$ 使用归纳法。当 $m=0$ 时，该语句自 $T=G$ 起就很简单。 假设 Eq. 5 对于所有图形和所有小于 $m$ 边的条件成立。 假设根 $r$ 有 $d$ 个邻居 $v_1,\mathrm{\dots },v_d$。 定义$G^{\prime }$为将顶点$r$替换为$d$顶点$r_1,\mathrm{\dots },r_d$，然后连接$\{r_i,d_i\}$得到的图对于$1\le i\le d$。

首先考虑$(G\backslash \{r\})\backslash \mathrm{\Lambda }$仍然连接的情况。 对于每个$i$，让$G_i=G^{\prime }-r_i$。 使用相同的参数 $(\beta ,\gamma ,𝝀)$ 在 $G_i$ 上定义 $2$-自旋系统，加上顶点 $r_1,\mathrm{\dots },r_{i-1}$ 固定为自旋的附加条件$0$而$r_{i+1},\mathrm{\dots },r_d$固定为自旋$1$；我们用 ${\sigma }_{U_i}$ 和 $U_i=\{v_1,\mathrm{\dots },v_d\}\backslash \{v_i\}$ 来表示这种条件。 然后，可以通过以下递归过程生成$T=T_{\text{saw}}(G,r)$。 另请参阅图2了解说明。

图2： 自回避行走（SAW）树的递归构造。 这里$T_i$是$G_i$的SAW树，其根为$i=1,2,3$的$v_i$。 ($\mathrm{●}$/$\mathrm{○}$：固定为旋转$1$/$0$。）

算法：$T_{\text{saw}}(G,r)$

1. 对于每个$i$，让$T_i=T_{\text{saw}}(G_i,v_i)$加上条件${\sigma }_{U_i}$；

2. 通过将 $\{r,v_i\}$ 连接为 $1\le i\le d$，使 $T=T_{\text{saw}}(G,r)$ 成为 $r$ 和 $T_1,\mathrm{\dots },T_d$ 的并集；输出$T$。

为了证明的目的，我们还考虑 $G^{\prime }$ 上具有相同参数 $(\beta ,\gamma ,𝝀)$ 的 $2$-自旋系统，但我们让顶点 $r_1,\mathrm{\dots },r_d$ 没有字段（即为 $1\le i\le d$ 设置 ${\lambda }_{r_i}=1$ 而不是 ${\lambda }_r$)。 然后我们观察到

$$Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=1)={\lambda }_r\cdot Z_{G^{\prime }}^{{\sigma }_{\mathrm{\Lambda }}}(r_1=1,\mathrm{\dots },r_d=1),$$

将自旋 $1$ 替换为 $0$ 也是如此。 对于$1\le i\le d$，让${\sigma }_{{\mathrm{\Lambda }}_i}$表示条件${\sigma }_{\mathrm{\Lambda }}$和${\sigma }_{U_i}$的并集，其中${\mathrm{\Lambda }}_i=\mathrm{\Lambda }\cup U_i$。 然后对于每个 $1\le i\le d$ 我们有

$$Z_{G^{\prime }}^{{\sigma }_{\mathrm{\Lambda }}}(r_1=0,\mathrm{\dots },r_{i-1}=0,r_i=1,\mathrm{\dots },r_d=1)=\beta \cdot Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=1)+Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=0).$$

请注意，两侧都独立于字段${\lambda }_r$：对于左侧，所有$r_i$在$G^{\prime }$上都没有用于旋转系统的字段；对于右侧，请记住，我们不计算每个 $G_i$ 的条件分区函数的固定顶点的权重。 现在定义 $Q_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=Q_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}(𝝀)$ 通过

$$Q_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=\prod _{i=2}^d{Z}_{G^{\prime }}^{{\sigma }_{\mathrm{\Lambda }}}(r_1=0,\mathrm{\dots },r_{i-1}=0,r_i=1,\mathrm{\dots },r_d=1),$$

它独立于 ${\lambda }_r$。 然后我们得到

$Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=1)\cdot Q_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}$ $={\lambda }_r\cdot {\displaystyle \prod _{i=1}^d}{Z}_{G^{\prime }}^{{\sigma }_{\mathrm{\Lambda }}}(r_1=0,\mathrm{\dots },r_{i-1}=0,r_i=1,\mathrm{\dots },r_d=1)$

$={\lambda }_r\cdot {\displaystyle \prod _{i=1}^d}\left(\beta \cdot Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=1)+Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=0)\right).$

使用类似的论证，我们也有

$Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=0)\cdot Q_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}$ $={\displaystyle \prod _{i=1}^d}{Z}_{G^{\prime }}^{{\sigma }_{\mathrm{\Lambda }}}(r_1=0,\mathrm{\dots },r_i=0,r_{i+1}=1,\mathrm{\dots },r_d=1)$

$={\displaystyle \prod _{i=1}^d}\left(Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=1)+\gamma \cdot Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=0)\right).$

由于我们假设 $(G\backslash \{r\})\backslash \mathrm{\Lambda }$ 是连通的，因此对于每个 $i$ 来说，图 $G_i\backslash \mathrm{\Lambda }$ 也是连通的。 然后，根据归纳假设，对于每个 $i$ 都存在一个多项式 $P_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}=P_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(𝝀)$ 使得

$$Z_{T_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(r=1)=Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(r=1)\cdot P_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}\text{and}{Z}_{T_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(r=0)=Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(r=0)\cdot P_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}};$$

这些多项式独立于 ${\lambda }_r$，因为 $G_i$ 的条件分配函数不涉及 ${\lambda }_r$。 现在如果我们让

$$P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=Q_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}\cdot \prod _{i=1}^d{P}_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}},$$

那么从树递归可以得出

$Z_T^{{\sigma }_{\mathrm{\Lambda }}}(r=1)$ $={\lambda }_r\cdot {\displaystyle \prod _{i=1}^d}\left(\beta \cdot Z_{T_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=1)+Z_{T_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=0)\right)$

$={\lambda }_r\cdot {\displaystyle \prod _{i=1}^d}\left(\beta \cdot Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=1)\cdot P_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}+Z_{G_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}(v_i=0)\cdot P_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}\right)$

$=Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=1)\cdot Q_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}\cdot {\displaystyle \prod _{i=1}^d}{P}_{G_i,v_i}^{{\sigma }_{{\mathrm{\Lambda }}_i}}$

$=Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=1)\cdot P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}.$

另一个平等 $$ZTσΛ​ (r​ = ​0)=ZGσΛ​ (r​ = ​0)·PG,r σΛ 以同样的方式建立。 这样就完成了$(G\backslash \{r\})\backslash \mathrm{\Lambda }$已连接的情况的证明。

如果$(G\backslash \{r\})\backslash \mathrm{\Lambda }$有两个或多个连通分量，那么我们可以通过每个分量的SAW树构造$T_{\text{saw}}(G,r)$。 回想一下，$G^{\prime }$ 是通过将顶点 $r$ 拆分为图中 $G$ 中的 $d$ 个副本来定义的。假设 $G^{\prime }\backslash \mathrm{\Lambda }$ 具有整数 $k\ge 2$ 的 $k$ 连接分量。 令 $G_{(1)}^{\prime },\mathrm{\dots },G_{(k)}^{\prime }$ 为每个组件导出的子图，以及来自与其相邻的 $\mathrm{\Lambda }$ 的顶点。 对于每个 $j$，让 $G_{(j)}$ 是通过将 $r$ 的所有副本收缩为一个顶点 $r_{(j)}$ 从 $G_{(j)}^{\prime }$ 得到的图形，并让 $T_{(j)}=T_{\text{saw}}(G_{(j)}^{\prime },r_{(j)})$. 观察一下，一旦我们收缩 $T_{(1)},\mathrm{\dots },T_{(k)}$ 的根 $r_{(1)},\mathrm{\dots },r_{(k)}$，生成的树就是 $T_{\text{saw}}(G,r)$。

我们在每个 $G_{(j)}$ 上使用相同的参数 $(\beta ,\gamma ,𝝀)$ 定义 $2$-spin 系统，只是顶点 $r_{(j)}$ 没有字段（即 ${\lambda }_{r_{(j)}}=1$ 而不是 ${\lambda }_r$)。 对于$1\le j\le k$，令${\mathrm{\Lambda }}_{(j)}=\mathrm{\Lambda }\cap V(G_{(j)})$和${\sigma }_{{\mathrm{\Lambda }}_{(j)}}$为限制在${\mathrm{\Lambda }}_{(j)}$上的配置${\sigma }_{\mathrm{\Lambda }}$。 然后 $G_{(j)}\backslash {\mathrm{\Lambda }}_{(j)}$ 与每个 $j$ 连接，并且由于 $k\ge 2$，每个具有条件 ${\sigma }_{{\mathrm{\Lambda }}_{(j)}}$ 的 $G_{(j)}$ 的数量少于$m$ 边缘。 因此，我们可以应用归纳假设；即，对于$1\le j\le k$，存在一个独立于${\lambda }_r$的多项式$P_{G_{(i)},r_{(i)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}=P_{G_{(i)},r_{(i)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}(𝝀)$，使得

$$Z_{T_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}(r_{(j)}=1)=Z_{G_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}(r_{(j)}=1)\cdot P_{G_{(j)},r_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}\text{and}{Z}_{T_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}(r_{(j)}=0)=Z_{G_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}(r_{(j)}=0)\cdot P_{G_{(j)},r_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}.$$

我们将多项式 $P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}(𝝀)$ 定义为

$$P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}}=\prod _{j=1}^k{P}_{G_{(j)},r_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}.$$

然后很容易检查

$Z_T^{{\sigma }_{\mathrm{\Lambda }}}(r=1)$ $={\lambda }_r\cdot {\displaystyle \prod _{j=1}^k}{Z}_{T_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}(r_{(j)}=1)={\lambda }_r\cdot {\displaystyle \prod _{j=1}^k}\left(Z_{G_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}(r_{(j)}=1)\cdot P_{G_{(j)},r_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}\right)$

$=Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=1)\cdot {\displaystyle \prod _{j=1}^k}{P}_{G_{(j)},r_{(j)}}^{{\sigma }_{{\mathrm{\Lambda }}_{(j)}}}=Z_G^{{\sigma }_{\mathrm{\Lambda }}}(r=1)\cdot P_{G,r}^{{\sigma }_{\mathrm{\Lambda }}},$

和类似地 $$ZTσΛ​ (r​ = ​0)=ZGσΛ​ (r​ = ​0)·PG,r σΛ. 定理如下。 ∎

5 对树木的影响范围

在本节中，我们研究根对树中其他顶点的影响。 我们给出根对固定距离处所有顶点的总影响的上限。 为此，我们应用了势方法，该方法已用于建立相关衰减属性（例如，参见[LLY12，LLY13，GL18])。 给定任意势函数 $\mathrm{\Psi }$，我们的上限是根据 $\mathrm{\Psi }$ 的属性，涉及 ${\Vert \nabla H_d^{\mathrm{\Psi }}\Vert }_1$ 和 $|\psi |$ 上的界限，其中 $\psi ={\mathrm{\Psi }}^{\prime }$。 然后，在 $\mathrm{\Psi }$ 为 $(\alpha ,c)$ 势的情况下，我们推导出 9。

假设$T=(V_T,E_T)$是一棵以$r$为根、最大度数至多$\mathrm{\Delta }$的树。 令 $\mathrm{\Lambda }\subseteq V_T\backslash \{r\}$ 和 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 是任意且固定的。 考虑 $T$ 上的 $2$-自旋系统，参数为 $(\beta ,\gamma ,\lambda )$，以 ${\sigma }_{\mathrm{\Lambda }}$ 为条件。 我们需要限制影响力 $$ℐTσΛ​ (r​ → ​v) 从根$r$到另一个顶点$v\in V_T$。 请注意，如果在删除 $\mathrm{\Lambda }$ 时 $v$ 与 $r$ 断开连接，则 $$ℐTσΛ​ (r​ → ​v)=0 由自旋系统的马尔可夫性质。 因此，我们可以假设，通过删除所有此类顶点，$\mathrm{\Lambda }$ 只包含 $T$ 的叶子。

对于顶点 $v\in V_T$，令 $T_v=(V_{T_v},E_{T_v})$ 为以 $v$ 为根的 $T$ 的子树，其中包含 $v$ 的所有后代>;请注意$T_r=T$。 我们将 $L_v(k)\subseteq V_T\backslash \mathrm{\Lambda }$ 写为 $T_v$ 中距 $v$ 距离为 $k$ 的所有自由顶点的集合。 我们特别关注子树$T_v$中$v$处的边际比率，为了简单起见，写成$R_v=R_{T_v}^{{\sigma }_{\mathrm{\Lambda }}}(v)$。 $\log R_v$ 通过树递归 $H$ 关联。如果顶点 $v$ 有 $d$ 子节点，用 $u_1,\mathrm{\dots },u_d$ 表示，则树递归由下式给出

$$\log R_v=H_d(\log R_{u_1},\mathrm{\dots },\log R_{u_d}),$$

其中对于 $1\le d\le \mathrm{\Delta }$ 和 $(y_1,\mathrm{\dots },y_d)\in {[-\mathrm{\infty },+\mathrm{\infty }]}^d$，

$$H_d(y_1,\mathrm{\dots },y_d)=\log \lambda +\sum _{i=1}^d\log \left(\frac{\beta e^{y_i}+1}{e^{y_i}+\gamma }\right).$$

另请记住，对于 $y\in [-\mathrm{\infty },+\mathrm{\infty }]$，我们定义

$$h(y)=-\frac{(1-\beta \gamma )e^y}{(\beta e^y+1)(e^y+\gamma )}$$

和所有 $1\le i\le d\le \mathrm{\Delta }$ 的 $\frac{\partial }{\partial y_i}{H}_d(y_1,\mathrm{\dots },y_d)=h(y_i)$。

下面的引理允许我们使用任意势函数将所有影响的总和从根限制到距离 $k$。

Lemma 14.

令 $\mathrm{\Psi }:[-\mathrm{\infty },+\mathrm{\infty }]\to (-\mathrm{\infty },+\mathrm{\infty })$ 为具有图像 $S=\mathrm{\Psi }[-\mathrm{\infty },+\mathrm{\infty }]$ 和导数 $\psi ={\mathrm{\Psi }}^{\prime }$ 的可微且递增（势）函数。 用${\mathrm{\Delta }}_r$表示根$r$的次数。 然后对于每个整数 $k\ge 1$，

在哪里

$$A_{\mathrm{\Psi }}=\underset{u\in L_r(1)}{\max }\left\{\frac{|h(\log R_u)|}{\psi (\log R_u)}\right\}\text{and}{B}_{\mathrm{\Psi }}=\underset{v\in L_r(k)}{\max }\left\{\psi (\log R_v)\right\}.$$

在证明14之前，我们首先提出对树的影响的两个有用的属性。 首先，在[ALO20]中表明，影响满足以下形式的树链式法则。

Lemma 15 ([ALO20，引理B.2])。

假设 $u,v,w\in V_T$ 是三个不同的顶点，使得 $u$ 位于从 $v$ 到 $w$ 的唯一路径上。然后

$${ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(v\to w)={ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(v\to u)\cdot {ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u\to w).$$

其次，对于树上的两个相邻顶点，一个对另一个的影响由函数$h$给出。

Lemma 16.

令 $v\in V_T$ 和 $u$ 为子树 $T_v$ 中 $v$ 的子级。 然后

$${ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(v\to u)=h(\log R_u).$$

证明。

引理可以通过影响力的显式计算来证明。 在这里，我们利用 12 提出了一个更微妙的证明，它给出了影响力与函数 $h$ 之间关系的一些见解。我们假设$v$在子树$T_v$中有$d$个子节点，分别用$u_1=u$和$u_2,\mathrm{\dots },u_d$表示。 我们还假设，作为比统一字段更通用的设置，每个顶点 $w$ 都附加到其自己的字段 ${\lambda }_w$ 上。 那么 12 和树递归意味着

${ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(v\to u)$ $={ℐ}_{T_v}^{{\sigma }_{\mathrm{\Lambda }}}(v\to u)=\left({\lambda }_u{\displaystyle \frac{\partial }{\partial {\lambda }_u}}\right)\log R_v$

$=\left({\lambda }_u{\displaystyle \frac{\partial }{\partial {\lambda }_u}}\right)H_d(\log R_{u_1},\mathrm{\dots },\log R_{u_d})$

$={\displaystyle \sum _{i=1}^d}{\displaystyle \frac{\partial }{\partial \log R_{u_i}}}{H}_d(\log R_{u_1},\mathrm{\dots },\log R_{u_d})\cdot \left({\lambda }_u{\displaystyle \frac{\partial }{\partial {\lambda }_u}}\right)\log R_{u_i}$

$={\displaystyle \sum _{i=1}^d}h(\log R_{u_i})\cdot {ℐ}_{T_{u_i}}^{{\sigma }_{\mathrm{\Lambda }}}(u_i\to u)=h(\log R_u),$

最后一个相等是因为 $$ℐTuiσΛ​0>(ui​ → ​u)=0 对于 $u_i\ne u$ 和 $$ℐTuσΛ​(u​ → ​u)=1. ∎

我们现在准备证明14。

14 的证明。

对于顶点$v\in V_T$，用$d_v$表示其子节点的数量；请注意$d_r={\mathrm{\Delta }}_r$。 令 $u_1,\mathrm{\dots },u_{{\mathrm{\Delta }}_r}$ 为根 $r$ 的子级。我们可以假设 $r$ 的所有这些子元素都是自由的，因为如果 $u_i$ 是固定的，那么 $$ℐTσΛ​ (r​ → ​ui)=0 根据定义。 然后通过15和16，我们得到

${\displaystyle \sum _{v\in L_r(k)}}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|$ $={\displaystyle \sum _{i=1}^{{\mathrm{\Delta }}_r}}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to u_i)\right|{\displaystyle \sum _{v\in L_{u_i}(k-1)}}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u_i\to v)\right|$

$={\displaystyle \sum _{i=1}^{{\mathrm{\Delta }}_r}}\left|h(\log R_{u_i})\right|{\displaystyle \sum _{v\in L_{u_i}(k-1)}}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u_i\to v)\right|$

$={\displaystyle \sum _{i=1}^{{\mathrm{\Delta }}_r}}{\displaystyle \frac{\left|h(\log R_{u_i})\right|}{\psi (\log R_{u_i})}}{\displaystyle \sum _{v\in L_{u_i}(k-1)}}\psi (\log R_{u_i})\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u_i\to v)\right|.$

因此，我们得到

$$\sum _{v\in L_r(k)}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|\le {\mathrm{\Delta }}_r\cdot \underset{1\le i\le {\mathrm{\Delta }}_r}{\max }\left\{\frac{|h(\log R_{u_i})|}{\psi (\log R_{u_i})}\right\}\cdot \underset{1\le i\le {\mathrm{\Delta }}_r}{\max }\left\{\sum _{v\in L_{u_i}(k-1)}\psi (\log R_{u_i})\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u_i\to v)\right|\right\}.$$ (6)

接下来，我们通过归纳法证明，对于每个顶点 $u\in V_T\backslash \{r\}$ 和每个整数 $k\ge 0$ 我们有

$$\sum _{v\in L_u(k)}\psi (\log R_u)\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u\to v)\right|\le \underset{v\in L_u(k)}{\max }\left\{\psi (\log R_v)\right\}\cdot {\left(\underset{w\in V_{T_u}}{\max }\underset{\widetilde{𝒚}\in S^{d_w}}{sup}{\Vert \nabla H_{d_w}^{\mathrm{\Psi }}(\widetilde{𝒚})\Vert }_1\right)}^k.$$ (7)

观察一下，一旦我们建立 Eq. 7，引理就会立即通过插入 Eq. 7 代入方程 6。 我们将使用$k$上的归纳法来证明方程7。 当$k=0$时，如果$u\in \mathrm{\Lambda }$固定，则$L_u(0)=\mathrm{\varnothing }$没有任何内容可显示；否则，Eq. 7 变为

$$\psi (\log R_u)\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u\to u)\right|\le \psi (\log R_u),$$

自从 $$ℐTσΛ​ (u​ → ​u)=1. 现在假设 Eq. 7 对于某个整数 $k-1\ge 0$ 成立（对于每个顶点 $u\in V_T\backslash \{r\}$ ）。 令 $u\in V_T\backslash \{r\}$ 为任意值，并用 $w_1,\mathrm{\dots },w_d$ 表示 $u$ 的子级，其中 （如果 $d=0$ 则 $L_u(k)=\mathrm{\varnothing }$ 和 Eq. 7 基本成立）。 再次到 15 和 16 我们有

${\displaystyle \sum _{v\in L_u(k)}}\psi (\log R_u)\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u\to v)\right|$ $={\displaystyle \sum _{i=1}^d}\psi (\log R_u)\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u\to w_i)\right|{\displaystyle \sum _{v\in L_{w_i}(k-1)}}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(w_i\to v)\right|$

$={\displaystyle \sum _{i=1}^d}{\displaystyle \frac{\psi (\log R_u)}{\psi (\log R_{w_i})}}\left|h(\log R_{w_i})\right|{\displaystyle \sum _{v\in L_{w_i}(k-1)}}\psi (\log R_{w_i})\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(w_i\to v)\right|.$

使用归纳假设，我们得到

${\displaystyle \sum _{v\in L_u(k)}}\psi (\log R_u)\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(u\to v)\right|$

$\le$ ${\displaystyle \sum _{i=1}^d}{\displaystyle \frac{\psi (\log R_u)}{\psi (\log R_{w_i})}}\left|h(\log R_{w_i})\right|\cdot \underset{v\in L_{w_i}(k-1)}{\max }\left\{\psi (\log R_v)\right\}\cdot {\left(\underset{w\in V_{T_{w_i}}}{\max }\underset{\widetilde{𝒚}\in S^{d_w}}{sup}{\Vert \nabla H_{d_w}^{\mathrm{\Psi }}(\widetilde{𝒚})\Vert }_1\right)}^{k-1}$

$\le$ $\underset{v\in L_u(k)}{\max }\left\{\psi (\log R_v)\right\}\cdot {\left(\underset{w\in V_{T_u}\backslash \{u\}}{\max }\underset{\widetilde{𝒚}\in S^{d_w}}{sup}{\Vert \nabla H_{d_w}^{\mathrm{\Psi }}(\widetilde{𝒚})\Vert }_1\right)}^{k-1}\cdot {\displaystyle \sum _{i=1}^d}{\displaystyle \frac{\psi (\log R_u)}{\psi (\log R_{w_i})}}\left|h(\log R_{w_i})\right|$

$\le$ $\underset{v\in L_u(k)}{\max }\left\{\psi (\log R_v)\right\}\cdot {\left(\underset{w\in V_{T_u}}{\max }\underset{\widetilde{𝒚}\in S^{d_w}}{sup}{\Vert \nabla H_{d_w}^{\mathrm{\Psi }}(\widetilde{𝒚})\Vert }_1\right)}^k,$

最后的不等式由此得出

${\displaystyle \sum _{i=1}^d}{\displaystyle \frac{\psi (\log R_u)}{\psi (\log R_{w_i})}}\left|h(\log R_{w_i})\right|$ $={\displaystyle \sum _{i=1}^d}\left|{\displaystyle \frac{\partial }{\partial \mathrm{\Psi }(\log R_{w_i})}}{H}_d^{\mathrm{\Psi }}(\mathrm{\Psi }(\log R_{w_1}),\mathrm{\dots },\mathrm{\Psi }(\log R_{w_d}))\right|$

$={\Vert \nabla H_d^{\mathrm{\Psi }}(\mathrm{\Psi }(\log R_{w_1}),\mathrm{\dots },\mathrm{\Psi }(\log R_{w_d}))\Vert }_1.$

至此方程 7成立，从而完成了引理的证明。 ∎

然后我们推导出 9 作为推论。

9 的证明。

由于 $\mathrm{\Psi }$ 是一个 $(\alpha ,c)$ 势，因此 Contraction 条件意味着

同时，由于子树$T_v$中的顶点$v\in V_T\backslash \{r\}$的度小于$\mathrm{\Delta }$，所以我们有$\log R_v\in J$。 那么 Boundedness 条件意味着对于所有 $u\in L_r(1)$ 和 $v\in L_r(k)$，

$$\frac{\psi (\log R_v)}{\psi (\log R_u)}\cdot |h(\log R_u)|\le \frac{c}{\mathrm{\Delta }}.$$

因此，我们得到

$${\mathrm{\Delta }}_r{A}_{\mathrm{\Psi }}{B}_{\mathrm{\Psi }}={\mathrm{\Delta }}_r\cdot \underset{u\in L_r(1)}{\max }\left\{\frac{|h(\log R_u)|}{\psi (\log R_u)}\right\}\cdot \underset{v\in L_r(k)}{\max }\left\{\psi (\log R_v)\right\}\le c.$$

引理紧随 14 而来。 ∎

6 验证良好的潜力：收缩

在本节中，我们第一步来证明10。 令 $\mathrm{\Delta }\ge 3$ 为整数。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$。 回想一下，我们通过导数定义了我们的势函数 $\mathrm{\Psi }:[-\mathrm{\infty },+\mathrm{\infty }]\to (-\mathrm{\infty },+\mathrm{\infty })$

$${\mathrm{\Psi }}^{\prime }(y)=\psi (y)=\sqrt{\frac{(1-\beta \gamma )e^y}{(\beta e^y+1)(e^y+\gamma )}},\mathrm{\Psi }(0)=0.$$ (1)

我们在附录C中包含一个简短的证明，以表明$\mathrm{\Psi }$是明确定义的。 If $(\beta ,\gamma ,\lambda )$ is up-to-$\mathrm{\Delta }$ unique with gap $\delta \in (0,1)$, then we show that $\mathrm{\Psi }$ satisfies the Contraction condition for $\alpha =\delta /2$. 这适用于唯一性区域中的所有参数$(\beta ,\gamma ,\lambda )$,无需要求$\gamma \le 1$。 在后面的 附录 E中，我们建立了 $\mathrm{\Psi }$ 当 $\gamma \le 1$ 时的 有界性 条件，完成了 10 的证明。 $\gamma >1$的情况比较复杂，留给Section7。

在给出证明之前，我们首先指出势函数 $\mathrm{\Psi }$ 本质上与 [LLY13] 中使用的势函数 $\mathrm{\Phi }$ 相同（请注意，[LLY13] 使用 $\phi$ 作为势函数的符号，使用 $\mathrm{\Phi }={\phi }^{\prime }$ 作为其导数）。 回想一下，边际比率的树递归由函数 $F_d:{[0,+\mathrm{\infty }]}^d\to [0,+\mathrm{\infty }]$ 给出，其中 $1\le d\le \mathrm{\Delta }$ 使得对于所有 $(x_1,\mathrm{\dots },x_d)\in {[0,+\mathrm{\infty }]}^d$，

$$F_d(x_1,\mathrm{\dots },x_d)=\lambda \prod _{i=1}^d\frac{\beta x_i+1}{x_i+\gamma }.$$

来自 [LLY13] 的势函数 $\mathrm{\Phi }:[0,+\mathrm{\infty }]\to (-\mathrm{\infty },+\mathrm{\infty })$ 通过其导数隐式定义为

$${\mathrm{\Phi }}^{\prime }(x)=\phi (x)=\frac{1}{\sqrt{x(\beta x+1)(x+\gamma )}},\mathrm{\Phi }(1)=0.$$

以下引理解释了我们如何从 $\mathrm{\Phi }$ 获得潜在的 $\mathrm{\Psi }$。

Lemma 17.

我们有$\mathrm{\Psi }=\sqrt{1-\beta \gamma }\cdot (\mathrm{\Phi }\circ \exp )$；即，$\mathrm{\Psi }(y)=\sqrt{1-\beta \gamma }\cdot \mathrm{\Phi }(e^y)$ 代表所有 $y\in [-\mathrm{\infty },+\mathrm{\infty }]$。

证明。

检查起来很简单

$$\psi (y)=\sqrt{\frac{(1-\beta \gamma )e^y}{(\beta e^y+1)(e^y+\gamma )}}=\sqrt{1-\beta \gamma }\cdot e^y\cdot \sqrt{\frac{1}{e^y(\beta e^y+1)(e^y+\gamma )}}=\sqrt{1-\beta \gamma }\cdot e^y\phi (e^y).$$

所以，

$$\mathrm{\Psi }(y)={\int }_0^y\psi (t)dt=\sqrt{1-\beta \gamma }\cdot {\int }_0^y{e}^t\phi (e^t)dt=\sqrt{1-\beta \gamma }\cdot {\int }_1^{e^y}\phi (s)ds=\sqrt{1-\beta \gamma }\cdot \mathrm{\Phi }(e^y).\mathit{∎}$$

结合[LLY13]引理12、13和14的结果，我们得到当$(\beta ,\gamma ,\lambda )$在时，势函数$\mathrm{\Phi }$满足以下梯度界限独特性区域。 请注意，这可以被视为收缩条件，但对于$\mathrm{\Phi }$和$F_d$而言。

Theorem 18 ([LLY13]).

令 $S_{\mathrm{\Phi }}=\mathrm{\Phi }[0,+\mathrm{\infty }]$ 为 $\mathrm{\Phi }$ 的图像。 如果参数 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一，且间隔 $\delta \in (0,1)$，则对于每个整数 $d$ 使得 和每个 $({\tilde{x}}_1,\mathrm{\dots },{\tilde{x}}_d)\in S_{\mathrm{\Phi }}^d$，

$${\Vert \nabla F_d^{\mathrm{\Phi }}({\tilde{x}}_1,\mathrm{\dots },{\tilde{x}}_d)\Vert }_1\le \sqrt{1-\delta }$$

其中$F_d^{\mathrm{\Phi }}=\mathrm{\Phi }\circ F_d\circ {\mathrm{\Phi }}^{-1}$。

回想一下我们在部分1.1中的定义。 就对数边际比而言，树递归由函数 $H_d:{[-\mathrm{\infty },+\mathrm{\infty }]}^d\to [-\mathrm{\infty },+\mathrm{\infty }]$ 描述，其中 $1\le d\le \mathrm{\Delta }$ 使得对于每个 $(y_1,\mathrm{\dots },y_d)\in {[-\mathrm{\infty },+\mathrm{\infty }]}^d$，

$$H_d(y_1,\mathrm{\dots },y_d)=\log \lambda +\sum _{i=1}^d\log \left(\frac{\beta e^{y_i}+1}{e^{y_i}+\gamma }\right).$$

观察 $H_d=\log \circ F_d\circ \exp$，因为我们从比率转向对数比率。 我们现在准备好为 $\mathrm{\Psi }$ 建立收缩条件。

Lemma 19.

令 $S_{\mathrm{\Psi }}=\mathrm{\Psi }[-\mathrm{\infty },+\mathrm{\infty }]$ 为 $\mathrm{\Psi }$ 的图像。 如果参数 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一，且间隔 $\delta \in (0,1)$，则对于每个整数 $d$ 使得 和每个 $({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\in S_{\mathrm{\Psi }}^d$，

$${\Vert \nabla H_d^{\mathrm{\Psi }}({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\Vert }_1\le \sqrt{1-\delta }$$

其中$H_d^{\mathrm{\Psi }}=\mathrm{\Psi }\circ H_d\circ {\mathrm{\Psi }}^{-1}$。

证明。

将 $x\in ℝ$ 的线性函数 $a:ℝ\to ℝ$ 定义为 $a(x)=\sqrt{1-\beta \gamma }\cdot x$。 然后17给出$\mathrm{\Psi }=a\circ \mathrm{\Phi }\circ \exp$，从而给出$\mathrm{\Psi }\circ \log =a\circ \mathrm{\Phi }$。 由此可见，对于每个 ，

$$H_d^{\mathrm{\Psi }}=\mathrm{\Psi }\circ H_d\circ {\mathrm{\Psi }}^{-1}=\mathrm{\Psi }\circ \log \circ F_d\circ \exp \circ {\mathrm{\Psi }}^{-1}=a\circ \mathrm{\Phi }\circ F_d\circ {\mathrm{\Phi }}^{-1}\circ a^{-1}=a\circ F_d^{\mathrm{\Phi }}\circ a^{-1}.$$

这意味着，对于每个 $({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\in S_{\mathrm{\Psi }}^d$ 我们有

$$H_d^{\mathrm{\Psi }}({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)=\sqrt{1-\beta \gamma }\cdot F_d^{\mathrm{\Phi }}({\tilde{x}}_1,\mathrm{\dots },{\tilde{x}}_d)$$

其中 ${\tilde{x}}_i={\tilde{y}}_i/\sqrt{1-\beta \gamma }$ 代表 $1\le i\le d$。 然后，对于每个$i$，

$$\frac{\partial }{\partial {\tilde{y}}_i}{H}_d^{\mathrm{\Psi }}({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)=\sqrt{1-\beta \gamma }\cdot \frac{\partial }{\partial {\tilde{x}}_i}{F}_d^{\mathrm{\Phi }}({\tilde{x}}_1,\mathrm{\dots },{\tilde{x}}_d)\cdot \frac{\mathrm{d}{\tilde{x}}_i}{\mathrm{d}{\tilde{y}}_i}=\frac{\partial }{\partial {\tilde{x}}_i}{F}_d^{\mathrm{\Phi }}({\tilde{x}}_1,\mathrm{\dots },{\tilde{x}}_d).$$

这意味着 $\nabla H_d^{\mathrm{\Psi }}({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)=\nabla F_d^{\mathrm{\Phi }}({\tilde{x}}_1,\mathrm{\dots },{\tilde{x}}_d)$ 对于所有 $({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\in S_{\mathrm{\Psi }}^d$ 而言，引理则来自 18。 ∎

7 剩余的反铁磁情况：$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$和$\gamma >1$

在本节中，我们讨论 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma >1$ 的情况。 正如[LLY13]中所研究的，在这种情况下，唯一性区域更加复杂。 例如，存在一个临界${\lambda }_c^{\ast }>0$，使得具有的$2$自旋系统处于任意图的唯一性区域中；也就是说，$(\beta ,\gamma ,\lambda )$ 最多是$\mathrm{\infty }$ 是唯一的。 为了处理大度数，我们需要放宽4中的有界性条件，并定义更通用版本的$(\alpha ,c)$势。 我们将看到 5 对于这个一般的 $(\alpha ,c)$ 潜力仍然成立。 其背后的原因是，为了限制影响力矩阵的最大特征值，只需考虑具有大度数的顶点的绝对影响力的顶点加权和。

Remark 20。

我们在部分E.1中提供了有关唯一性区域的更多背景信息。 请注意，在最近的 [LLY13] 修订版中，作者更新了案例 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma >1$ 的唯一性区域的描述，修复了一个小错误在以前的版本中。 本文本节及附录E中的陈述和证明也根据新版本[LLY13]<进行了相应调整/t3>.

回想一下，我们的目标是限制矩阵 ${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}$ 的最大特征值。 我们可以通过限制绝对行总和的上限来做到这一点 ${\Sigma }_{v\epsilon V\backslash \mathrm{\Lambda }}|$ℐGσΛ​ (r​ → ​v)| 固定的 $r$，从而为我们提供了 ${\lambda }_{\max }({ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}})$ 的有效上限。 然而，当$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$和$\gamma >1$时，这种方法不起作用。 在这种情况下，势 $\mathrm{\Psi }$ 无法成为独立于 $\mathrm{\Delta }$ 的通用常数 $c$ 的 $(\alpha ,c)$ 势。 事实上，不存在这样的 $(\alpha ,c)$ 势作为绝对行和 ${\Sigma }_{v\epsilon V\backslash \mathrm{\Lambda }}|$ℐGσΛ​ (r​ → ​v)| 可以与$\mathrm{\Theta }(\mathrm{\Delta })$一样大。 特别是，如果参数 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\infty }$ 唯一，这意味着自旋系统对于任意图都具有唯一性，则绝对行和 ${\Sigma }_{v\epsilon V\backslash \mathrm{\Lambda }}|$ℐGσΛ​ (r​ → ​v)| 可以是 $\mathrm{\Theta }(n)$，其中 $n=|V|$。 我们举一个具体的例子来说明这种情况。

Example 21.

考虑由参数 $\beta =0$、$\gamma >1$ 和 $\lambda >0$ 在以 $r$ 为中心、有 $\mathrm{\Delta }$ 叶的星形图上指定的反铁磁性 2 自旋系统。 一个简单的计算表明 $|$ℐG​(r​ → ​v)|=λλ+γ 对于任何叶顶点$v\ne r$。 因此， ${\Sigma }_{v\ne r}|$ℐG​(r​ → ​v)|=Δ⋅λλ+γ. 现在，从 $\gamma >1$ 开始，我们有

强迫 ${\Sigma }_{v\ne r}|$ℐG​(r​ → ​v)|=θγ​(Δ) 即使 位于唯一性区域。 然而，我们仍然有 ${\lambda }_{\max }({ℐ}_G)=O(1)$ 因为 ${\Sigma }_{v\ne r}|$ℐG​(v​ → ​r)|=O​(1) .

为了解决这个问题，人们可能需要考虑绝对列总和，涉及对固定顶点的绝对影响的总和。 然而，这不允许我们使用图和 SAW 树之间的美丽连接，如 8 所示。 相反，我们在这里考虑 ${ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}$ 绝对行和的顶点加权版本，它也是最大特征值的上限。

Lemma 22.

令 $\rho :V\to {ℝ}^{+}$ 为顶点的正权重函数。 如果存在一个常量 $\xi >0$，对于每个 $r\in V$ 我们有

$$\sum _{v\in V\backslash \mathrm{\Lambda }}{\rho }_v\cdot \left|{ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|\le \xi \cdot {\rho }_r,$$ (8)

然后${\lambda }_{\max }({ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}})\le \xi$。

证明。

让$𝒫=\mathrm{diag}\{{\rho }_v:v\in V\backslash \mathrm{\Lambda }\}$。 那么假设就等价于${\Vert {𝒫}^{-1}{ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}𝒫\Vert }_{\mathrm{\infty }}\le \xi$。 由此可见${\lambda }_{\max }({ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}})={\lambda }_{\max }({𝒫}^{-1}{ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}𝒫)\le \xi$。 ∎

然后，我们修改 4 中 $(\alpha ,c)$-势的定义，以允许较弱的 有界性 条件。 我们注意到 23 和 4 之间唯一的两个区别是：我们允许 $\mathrm{\Delta }=\mathrm{\infty }$；并且有界性条件被放宽到我们所说的一般有界性。 回想一下，对于每个 ，我们在 时设置 $J_d=[\log (\lambda {\beta }^d),\log (\lambda /{\gamma }^d)]$，在 $\beta \gamma >1$ 时设置 $J_d=[\log (\lambda /{\gamma }^d),\log (\lambda {\beta }^d)]$。

Definition 23 （一般$(\alpha ,c)$-势函数）。

令 $\mathrm{\Delta }\ge 3$ 为整数或 $\mathrm{\Delta }=\mathrm{\infty }$。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$和$\lambda >0$。 令 $\mathrm{\Psi }:[-\mathrm{\infty },+\mathrm{\infty }]\to (-\mathrm{\infty },+\mathrm{\infty })$ 为具有图像 $S=\mathrm{\Psi }[-\mathrm{\infty },+\mathrm{\infty }]$ 和导数 $\psi ={\mathrm{\Psi }}^{\prime }$ 的可微且递增函数。 对于任何$\alpha \in (0,1)$和$c>0$，我们说$\mathrm{\Psi }$是一个一般$(\alpha ,c)$势函数 $\mathrm{\Delta }$和$(\beta ,\gamma ,\lambda )$如果满足以下条件：

1. （收缩）对于每个整数 $d$ 使得 和每个 $({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\in S^d$，我​​们有

   $${\Vert \nabla H_d^{\mathrm{\Psi }}({\tilde{y}}_1,\mathrm{\dots },{\tilde{y}}_d)\Vert }_1=\sum _{i=1}^d\frac{\psi (y)}{\psi (y_i)}\cdot |h(y_i)|\le 1-\alpha$$

   其中 $H_d^{\mathrm{\Psi }}=\mathrm{\Psi }\circ H_d\circ {\mathrm{\Psi }}^{-1}$、$y_i={\mathrm{\Psi }}^{-1}({\tilde{y}}_i)$ 为 $1\le i\le d$，以及$y=H_d(y_1,\mathrm{\dots },y_d)$。

2. （一般有界性）对于所有整数 $d_1,d_2$ 使得 和所有实数 $y_1\in J_{d_1},y_2\in J_{d_2}$，我​​们有

   $$\frac{\psi (y_2)}{\psi (y_1)}\cdot |h(y_1)|\le \frac{2c}{d_1+d_2+2}.$$

请注意，一般有界性 是比有界性 更弱的条件。 要看到这一点，如果潜在函数 $\mathrm{\Psi }$ 满足带有参数 $c$ 的 有界性，则对于每个 和每个 $y_i\in J_{d_i}$ 其中 $i=1,2$ 我们有

$$\frac{\psi (y_2)}{\psi (y_1)}\cdot |h(y_1)|\le \frac{c}{\mathrm{\Delta }}\le \frac{2c}{d_1+d_2+2}.$$

以下定理概括了 5 并表明一般的 $(\alpha ,c)$ 势函数足以建立格劳伯动力学的快速混合。

Theorem 24.

令 $\mathrm{\Delta }\ge 3$ 为整数或 $\mathrm{\Delta }=+\mathrm{\infty }$。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$和$\lambda >0$。 假设对于某些 $\alpha \in (0,1)$ 和 $c>0$ 存在相对于 $\mathrm{\Delta }$ 和 $(\beta ,\gamma ,\lambda )$ 的一般 $(\alpha ,c)$ 势。 然后对于最大度$\mathrm{\Delta }$的每个$n$-顶点图$G$,$2$-自旋系统的格劳伯动力学的混合时间带有参数 $(\beta ,\gamma ,\lambda )$ 的 $G$ 是 $O(n^{2+2c/\alpha })$。

然后，我们给出了 10 的对应关系，表明当 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma >1$ 时，$\mathrm{\Psi }$ 是一个一般的 $(\alpha ,c)$ 电位。 然后从24和25获得本例的3。

Lemma 25.

令 $\mathrm{\Delta }\ge 3$ 为整数。 令$\beta ,\gamma ,\lambda$为实数，使得和$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$。 假设 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，间隙为 $\delta \in (0,1)$。 那么由Eq.4隐式定义的函数$\mathrm{\Psi }$就是一个通用的$(\alpha ,c)$-势函数与$\alpha \ge \delta /2$和$c\le 18$；如果$\beta =0$，我们可以进一步取$c\le 4$。

24的证明可以在附录D中找到。对于25,$\mathrm{\Psi }$的收缩条件来自19，并且一般有界性1>是与所有其他案例一起在附录3>E4>2>中得到证明。

8 铁磁案例

在铁磁情况下，[GL18, SS20] 中给出了最著名的相关衰减结果。 使用[GL18]和[SS20]中的势函数，我们显示以下两个结果，与已知的相关衰减结果相匹配。 事实上，[SS20] 的势函数是常量 $\alpha =\mathrm{\Theta }(\delta )$ 和 $c\le O(1)$ 的 $(\alpha ,c)$ 势函数。

Theorem 26.

固定一个整数$\mathrm{\Delta }\ge 3$、正实数$\beta ,\gamma ,\lambda$和，并假设$(\beta ,\gamma ,\lambda )$满足以下三个条件之一：

1. $\frac{\mathrm{\Delta }-2+\delta }{\mathrm{\Delta }-\delta }\le \sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-\delta }{\mathrm{\Delta }-2+\delta }$,$\lambda$是任意的；

2. $\sqrt{\beta \gamma }\ge \frac{\mathrm{\Delta }}{\mathrm{\Delta }-2}$和$\lambda \le (1-\delta )\frac{\gamma }{\max \{1,{\beta }^{\mathrm{\Delta }-1}\}\cdot ((\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta })}$;

3. $\sqrt{\beta \gamma }\ge \frac{\mathrm{\Delta }}{\mathrm{\Delta }-2}$和$\lambda \ge \frac{1}{1-\delta }\cdot \frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{\beta \cdot \min \{1,1/{\gamma }^{\mathrm{\Delta }-1}\}}$。

那么恒等函数$\mathrm{\Psi }(y)=y$（基于[SS20]中给出的势）是$(\alpha ,c)$-$\alpha =\mathrm{\Theta }(\delta )$的势函数，并且$c\le O(1)$。 此外，对于每个最大度数至多$\mathrm{\Delta }$的$n$-顶点图$G$,$G$ 与参数 $(\beta ,\gamma ,\lambda )$ 是 $O(n^{2+c/\delta })$，对于通用常量 $c>0$。

Remark 3。

条件1包括铁磁情况和反铁磁情况。 请注意，在这两种情况下，$(\beta ,\gamma ,\lambda )$ 最多是 $\mathrm{\Delta }$ 唯一，且有间隙 $\delta$。 对于反铁磁性情况，与 公式 4 中 10 给出的电势 $\mathrm{\Psi }$ 的约束 $\alpha \ge \delta /2$ 相比，同一函数 $\mathrm{\Psi }$ 是一个 $(\alpha ,c)$ 电位，具有 $c\le 1.5$ 和更好的收缩率 $\alpha \ge \delta$。 对于具有$\beta =\gamma >1$（伊辛模型）的铁磁情况，已知[MS13]的更强结果，这给出了$O(n\log n)$混合。

[GL18] 的势函数确实是一个 $(\alpha ,c)$ 势函数，但不幸的是，$c$ 必须依赖于 $\mathrm{\Delta }$。 我们得到以下结果，该结果弱于无界度图[GL18]中的相关衰减算法。

Theorem 27.

固定一个整数$\mathrm{\Delta }\ge 3$和满足$\beta \le 1\le \gamma$、$\sqrt{\beta \gamma }\ge \frac{\mathrm{\Delta }}{\mathrm{\Delta }-2}$和的非负实数$\beta ,\gamma ,\lambda$。 然后对于每个$n$-顶点图$G$，其最大度数至多为$\mathrm{\Delta }$，铁磁2-自旋系统的格劳伯动力学在$G$ 与参数 $(\beta ,\gamma ,\lambda )$ 是 $O(n^C)$，对于常量 $C$ 仅取决于 $\beta ,\gamma ,\lambda ,\mathrm{\Delta }$，但不取决于 $n$.

这些定理的证明在附录F中提供。

附录A主要结果证明

本节我们给出1、2、3和5的证明。

5 的证明。

请注意，由于格劳伯动力学的转移矩阵 $P$ 具有所有非负特征值，因此我们有 ${\lambda }^{\ast }(P)=1-{\lambda }_2(P)$ ，因此为了推导出混合，它足以满足下界 $1-{\lambda }_2(P)$。 我们通过使用7来做到这一点。 对于足够小的${\eta }_i$，足以显示$({\eta }_0,\mathrm{\dots },{\eta }_{n-2})$的光谱独立性。

要绑定${\eta }_i$，只需绑定 ${\Sigma }_{v\epsilon V\backslash \{r\}}|$ℐGσΛ​ (r​ → ​v)| 对于具有 $n=|V|$ 顶点的所有图 $G=(V,E)$ 以及 $i$ 顶点的子集 $\mathrm{\Lambda }$ 上的所有边界条件 ${\sigma }_{\mathrm{\Lambda }}$。 我们声明如下：

$$\sum _{v\in V\backslash \{r\}}\left|{ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|\le \min \{\frac{c}{\alpha },C(n-i-1)\}$$ (9)

其中 $C\in (0,1)$ 是仅取决于 $\beta ,\gamma ,\lambda ,\mathrm{\Delta }$ 的常数。 第一个上限 $\frac{c}{\delta }$ 推导如下

${\displaystyle \sum _{v\in V\backslash \{r\}}}\left|{ℐ}_G^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|$ $\le {\displaystyle \sum _{v\in V_T\backslash \{r\}}}\left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|$ (8; $T=T_{\text{saw}}(G,r)$)

$={\displaystyle \sum _{k=1}^{\mathrm{\infty }}}{\displaystyle \sum _{v\in L_r(k)}}\left|{ℐ}_T^{{\sigma }_{{\mathrm{\Lambda }}_{\mathrm{\Lambda }}}}(r\to v)\right|$ (split the sum by levels)

$\le c{\displaystyle \sum _{k=1}^{\mathrm{\infty }}}{(1-\alpha )}^{k-1}$ (9)

$={\displaystyle \frac{c}{\alpha }}.$

第二个上限 $C(n-i-1)$ 更简单。 直观上，这意味着每个绝对成对影响 $|$ℐGσΛ​ (r​ → ​v)| 至多是某个常数$C$，因此绝对影响力的总和上限为$C(n-i-1)$。 下面的两个主张给出了更精确的陈述，其证明在部分A.2中提供。

Claim 28 （反铁磁案例）。

固定整数$\mathrm{\Delta }\ge 3$和实数$\beta ,\gamma ,\lambda$，并假设$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$。 那么，对于每个最大阶数至多为 $\mathrm{\Delta }$ 的 $n$ 顶点图 $G$，参数为 $(\beta ,\gamma ,\lambda )$ 的 $G$ 上的反铁磁 $2$ 自旋系统是 $Cn$ 光谱独立的，其常数 仅取决于 $\beta ,\gamma ,\lambda ,\mathrm{\Delta }$ 。 此外，如果 $(\beta ,\gamma ,\mathrm{\Delta })$ 最多是 $\mathrm{\Delta }$ 唯一，那么我们可以放弃对 $\mathrm{\Delta }$ 的依赖。

Claim 29 （铁磁外壳）。

固定一个整数$\mathrm{\Delta }\ge 3$和正实数$\beta ,\gamma ,\lambda$，并假设$\beta \le \gamma$和$\beta \gamma >1$。 那么，对于每个最大阶数至多为 $\mathrm{\Delta }$ 的 $n$ 顶点图 $G$，参数为 $(\beta ,\gamma ,\lambda )$ 的 $G$ 上的铁磁 $2$ 自旋系统是 $Cn$ 光谱独立的，常数 仅取决于 $\beta ,\gamma ,\lambda ,\mathrm{\Delta }$ 。

有了Eq.9，我们立即看到到7，

$$1-{\lambda }_2(P)\ge \frac{1}{n}\prod _{i=0}^{n-2}\left(1-\frac{{\eta }_i}{n-i-1}\right)\ge \frac{1}{n}\cdot {(1-C)}^{2\lceil c/\alpha \rceil -1}\cdot \prod _{i=0}^{n-2\lceil c/\alpha \rceil -1}\left(1-\frac{c}{\alpha }\cdot \frac{1}{n-i-1}\right).$$

利用 $1-x\ge \exp (-x-x^2)$ 对于所有 $0\le x\le \frac{1}{2}$ 的事实（可以通过微积分直接证明），我们得到

${\displaystyle \prod _{i=0}^{n-2\lceil c/\alpha \rceil -1}}\left(1-{\displaystyle \frac{c}{\alpha }}\cdot {\displaystyle \frac{1}{n-i-1}}\right)={\displaystyle \prod _{j=2\lceil c/\alpha \rceil }^{n-1}}\left(1-{\displaystyle \frac{c}{\alpha }}\cdot {\displaystyle \frac{1}{j}}\right)\ge \exp \left(-{\displaystyle \frac{c}{\alpha }}{\displaystyle \sum _{j=2\lceil c/\alpha \rceil }^{n-1}}{\displaystyle \frac{1}{j}}-{\displaystyle \frac{c^2}{{\alpha }^2}}{\displaystyle \sum _{j=2\lceil c/\alpha \rceil }^{n-1}}{\displaystyle \frac{1}{j^2}}\right).$

现在自从

$$\sum _{j=2\lceil c/\alpha \rceil }^{n-1}\frac{1}{j}\le \sum _{j=2}^n\frac{1}{j}\le {\int }_1^n\frac{dx}{x}=\log n$$

和

$$\sum _{j=2\lceil c/\alpha \rceil }^{n-1}\frac{1}{j^2}\le \sum _{j=2}^{\mathrm{\infty }}\frac{1}{j(j-1)}=1,$$

我们推断

$$1-{\lambda }_2(P)\ge {(1-C)}^{2\lceil c/\alpha \rceil -1}\cdot e^{-{(c/\alpha )}^2}\cdot n^{-(1+c/\alpha )}.$$

然后从 Eq. 1 得出定理。 ∎

3 的证明。

我们利用 5 和 24，只要存在 $(\alpha ,c)$ 电位，就会出现 $O(n^{2+\frac{c}{\alpha }})$ 混合；如果存在一般的 $(\alpha ,c)$ 电位，就会出现 $O(n^{2+\frac{2c}{\alpha }})$ 混合。 我们使用 Eq. 4 给出的势，它是 [LLY13] 中势函数的改编到对数边际比率。 当 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一且间隙 $\delta \in (0,1)$ 时，它是一个 $(\alpha ,c)$ 势或一般 $(\alpha ,c)$-由10和25计算的势，其中$\alpha \ge \delta /2$和$c$ 定理如下。 ∎

1 的证明。

在30之后的部分A.1中，$\lambda \le (1-\delta ){\lambda }_c(\mathrm{\Delta })$意味着最多$\mathrm{\Delta }$ 具有间隙$\ge \delta /4$ 的唯一性。 从$\gamma \le 1$开始，我们可以再次诉诸10来获得$(\alpha ,c)$与$\alpha \ge \delta /8$和$c\le 4$的势。 1 然后是 5 和 $O(n^{2+32/\delta })$ 混合。 ∎

2 的证明。

在31之后的部分A.1中，$\beta \ge {\beta }_c(\mathrm{\Delta })+\delta (1-{\beta }_c(\mathrm{\Delta }))$意味着最多$\mathrm{\Delta }$ 具有间隙$\delta$ 的唯一性。 再次呼吁 10，我们获得 $(\alpha ,c)$ 与 $\alpha \ge \delta /2$ 和 $c\le 1.5$ 的势。 2 然后是 5 和 $O(n^{2+3/\delta })$ 混合。

虽然我们在技术上通过使用 [LLY13] 势能得到 $O(n^{2+3/\delta })$，但我们可以通过使用平凡的恒等函数作为势能将其改进为 $O(n^{2+1.5/\delta })$ 混合。 参见26的第一种情况（在节 F.1中证明）和备注 3。 ∎

A.1 参数 paps 方面的唯一性差距

在本节中，我们陈述并证明30和31，它们将参数差距与唯一性差距联系起来。

Claim 30 （硬核模型；来自 [ALO20] 的引理 C.1）。

固定整数 $\mathrm{\Delta }\ge 3$、 和 $\beta =0,\gamma >0$。 如果$\lambda \le (1-\delta ){\lambda }_c(\gamma ,\mathrm{\Delta })$，则$(\beta ,\gamma ,\lambda )$最多$\mathrm{\Delta }$是唯一的，间隔$\delta /4$。

Claim 31 （大$\sqrt{\beta \gamma }$)。

固定整数$\mathrm{\Delta }\ge 3$和。 如果 $\sqrt{\beta \gamma }\ge \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}+\delta \left(1-\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}\right)=\frac{\mathrm{\Delta }-2(1-\delta )}{\mathrm{\Delta }}$，则 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，对于所有 $\lambda$ 来说，间隔为 。 注意如果$\beta =\gamma$，这正是条件$\beta \ge {\beta }_c(\mathrm{\Delta })+\delta (1-{\beta }_c(\mathrm{\Delta }))$。

证明。

考虑 子 $f_d(R)=\lambda {\left(\frac{\beta R+1}{R+\gamma }\right)}^d$ 边际比率的单变量递归。求微分，我们有

$f_d^{\prime }(R)$ $=d\lambda {\left({\displaystyle \frac{\beta R+1}{R+\gamma }}\right)}^{d-1}\cdot \left({\displaystyle \frac{\beta }{R+\gamma }}-{\displaystyle \frac{\beta R+1}{{(R+\gamma )}^2}}\right)=-d(1-\beta \gamma )\lambda {\left({\displaystyle \frac{\beta R+1}{R+\gamma }}\right)}^d\cdot {\displaystyle \frac{1}{(\beta R+1)(R+\gamma )}}$

$=-d(1-\beta \gamma )\cdot {\displaystyle \frac{f_d(R)}{(\beta R+1)(R+\gamma )}}.$

在唯一的固定点$R_d^{\ast }$，我们有$f_d(R_d^{\ast })=R_d^{\ast }$，所以

$\left|f_d^{\prime }(R_d^{\ast })\right|=d(1-\beta \gamma ){\displaystyle \frac{R_d^{\ast }}{(\beta R_d^{\ast }+1)(R_d^{\ast }+\gamma )}}.$

到 37 时，我们得到了上限

$\left|f_d^{\prime }(R_d^{\ast })\right|\le d\cdot {\displaystyle \frac{1-\beta \gamma }{{(1+\sqrt{\beta \gamma })}^2}}=d\cdot {\displaystyle \frac{1-\sqrt{\beta \gamma }}{1+\sqrt{\beta \gamma }}}.$

由于我们假设 $\sqrt{\beta \gamma }\ge \frac{\mathrm{\Delta }-2(1-\delta )}{\mathrm{\Delta }}$，我们得到

$d\cdot {\displaystyle \frac{1-\sqrt{\beta \gamma }}{1+\sqrt{\beta \gamma }}}\le d\cdot {\displaystyle \frac{\mathrm{\Delta }-(\mathrm{\Delta }-2(1-\delta ))}{\mathrm{\Delta }+(\mathrm{\Delta }-2(1-\delta ))}}=d\cdot {\displaystyle \frac{1-\delta }{\mathrm{\Delta }-1+\delta }}\le (1-\delta ){\displaystyle \frac{d}{\mathrm{\Delta }-1}}.$

由于所有 最多为 $1-\delta$，因此我们最多有 $\mathrm{\Delta }$ 个唯一性，间隙为 $\delta$。 ∎

A.2 恒定大小图的谱独立界限

在本节中，我们证明具有少于 $O(c/\alpha )$ 多个顶点的图的谱独立边界，因为对于具有如此少顶点的图，基于树递归收缩的边界变得微不足道。

28 的证明。

如果$R_v$表示顶点$v\in G$的边际比率，则$R_v\ge \lambda {\beta }^{\mathrm{\Delta }}$。 在$\gamma \le 1$的情况下，我们也有$R_v\le \lambda /{\gamma }^{\mathrm{\Delta }}$；如果$\gamma >1$，我们就有$R_v\le \lambda$。 由此可见，我们立即就有了界限

对于所有$u,v\in G$。 请注意，这些常量小于 $1$，并且仅取决于 $\beta ,\gamma ,\lambda ,\mathrm{\Delta }$，从而产生第一个声明。

现在，当最多 $\mathrm{\Delta }$ 唯一性成立时，我们继续消除对 $\mathrm{\Delta }$ 的依赖。 我们有以下案例：

1. 如果$\gamma >1$，我们立即获得$\frac{\lambda }{1+\lambda }$的边界，它独立于$\mathrm{\Delta }$。

2. 如果$\beta =0$和$\gamma \le 1$，则$\frac{\lambda (1-{\beta }^{\mathrm{\Delta }}{\gamma }^{\mathrm{\Delta }})}{(\lambda +{\gamma }^{\mathrm{\Delta }})(1+\lambda {\beta }^{\mathrm{\Delta }})}=\frac{\lambda }{\lambda +{\gamma }^{\mathrm{\Delta }}}\le \frac{\lambda }{{\gamma }^{\mathrm{\Delta }}}$。 由于 $(\beta ,\gamma ,\lambda )$ 的唯一性最多为 $\mathrm{\Delta }$，因此我们必须有 。 由此可见$\frac{\lambda }{{\gamma }^{\mathrm{\Delta }}}\le O(1/\mathrm{\Delta })$。

3. 如果$\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$和$\gamma \le 1$，那么

   ${\displaystyle \frac{\lambda (1-{\beta }^{\mathrm{\Delta }}{\gamma }^{\mathrm{\Delta }})}{(\lambda +{\gamma }^{\mathrm{\Delta }})(1+\lambda {\beta }^{\mathrm{\Delta }})}}\le 1-{\beta }^{\mathrm{\Delta }}{\gamma }^{\mathrm{\Delta }}\approx 1-e^{-2}.$

4. 如果 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$，那么让 ${\mathrm{\Delta }}_0$ 成为 中的最大值，使得 $\sqrt{\beta \gamma }>\frac{d-2}{d}$. 如果$\lambda \le {\lambda }_c(\beta ,\gamma ,\mathrm{\Delta })$，那么到35，我们有

   ${\displaystyle \frac{\lambda (1-{\beta }^{\mathrm{\Delta }}{\gamma }^{\mathrm{\Delta }})}{(\lambda +{\gamma }^{\mathrm{\Delta }})(1+\lambda {\beta }^{\mathrm{\Delta }})}}\le {\displaystyle \frac{\lambda }{{\gamma }^{\mathrm{\Delta }}}}\le O({\mathrm{\Delta }}_0/\mathrm{\Delta }).$

   如果$\lambda \ge {\overline{\lambda }}_c(\beta ,\gamma ,\mathrm{\Delta })$，那么再次到35，我们有

   $$\frac{\lambda (1-{\beta }^{\mathrm{\Delta }}{\gamma }^{\mathrm{\Delta }})}{(\lambda +{\gamma }^{\mathrm{\Delta }})(1+\lambda {\beta }^{\mathrm{\Delta }})}\le \frac{1}{\lambda {\beta }^{\mathrm{\Delta }}}\le O({\mathrm{\Delta }}_0/\mathrm{\Delta }).\mathit{∎}$$

29 的证明。

证明与反铁磁情况相同，我们在此省略。 ∎

附录 B 12 的证明（第 1 部分和第 2 部分）

12 的证明（第 1 部分和第 2 部分）。

为了看到第一个等式，我们直接计算并得到

$\left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\log Z_G^{{\sigma }_{\mathrm{\Lambda }}}$ $={\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}\cdot \left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)Z_G^{{\sigma }_{\mathrm{\Lambda }}}$

$={\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}{\displaystyle \sum _{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}}\left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\left({\beta }^{m_1(\sigma )}{\gamma }^{m_0(\sigma )}{\displaystyle \prod _{w\in V}}{\lambda }_w^{{\sigma }_w}\right)$

$={\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}{\displaystyle \sum _{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}}{\sigma }_v\left({\beta }^{m_1(\sigma )}{\gamma }^{m_0(\sigma )}{\displaystyle \prod _{w\in V}}{\lambda }_w^{{\sigma }_w}\right)$

$={\displaystyle \sum _{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}}{\sigma }_v\cdot {\mu }_G(\sigma \mid {\sigma }_{\mathrm{\Lambda }})=M_G^{{\sigma }_{\mathrm{\Lambda }}}(v).$

对于第 2 部分，使用上面的结果，我们还可以得到

$\left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\left({\lambda }_u{\displaystyle \frac{\partial }{\partial {\lambda }_u}}\right)\log Z_G^{{\sigma }_{\mathrm{\Lambda }}}$

$=$ $\left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\left({\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}\cdot \left({\lambda }_u{\displaystyle \frac{\partial }{\partial {\lambda }_u}}\right)Z_G^{{\sigma }_{\mathrm{\Lambda }}}\right)$

$=$ ${\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}\cdot \left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\left({\lambda }_u{\displaystyle \frac{\partial }{\partial {\lambda }_u}}\right)Z_G^{{\sigma }_{\mathrm{\Lambda }}}-{\displaystyle \frac{1}{{(Z_G^{{\sigma }_{\mathrm{\Lambda }}})}^2}}\cdot \left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)Z_G^{{\sigma }_{\mathrm{\Lambda }}}\cdot \left({\lambda }_u{\displaystyle \frac{\partial }{\partial {\lambda }_u}}\right)Z_G^{{\sigma }_{\mathrm{\Lambda }}}$

$=$ ${\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}\cdot \left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\left({\displaystyle \sum _{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}}{\sigma }_u\left({\beta }^{m_1(\sigma )}{\gamma }^{m_0(\sigma )}{\displaystyle \prod _{w\in V}}{\lambda }_w^{{\sigma }_w}\right)\right)-M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)\cdot M_G^{{\sigma }_{\mathrm{\Lambda }}}(v)$

$=$ ${\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}{\displaystyle \sum _{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}}{\sigma }_u\cdot \left({\lambda }_v{\displaystyle \frac{\partial }{\partial {\lambda }_v}}\right)\left({\beta }^{m_1(\sigma )}{\gamma }^{m_0(\sigma )}{\displaystyle \prod _{w\in V}}{\lambda }_w^{{\sigma }_w}\right)-M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)\cdot M_G^{{\sigma }_{\mathrm{\Lambda }}}(v)$

$=$ ${\displaystyle \frac{1}{Z_G^{{\sigma }_{\mathrm{\Lambda }}}}}{\displaystyle \sum _{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}}{\sigma }_u\cdot {\sigma }_v\left({\beta }^{m_1(\sigma )}{\gamma }^{m_0(\sigma )}{\displaystyle \prod _{w\in V}}{\lambda }_w^{{\sigma }_w}\right)-M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)\cdot M_G^{{\sigma }_{\mathrm{\Lambda }}}(v)$

$=$ ${\displaystyle \sum _{\sigma \in {\{0,1\}}^{V\backslash \mathrm{\Lambda }}}}{\sigma }_u\cdot {\sigma }_v\cdot {\mu }_G(\sigma \mid {\sigma }_{\mathrm{\Lambda }})-M_G^{{\sigma }_{\mathrm{\Lambda }}}(u)\cdot M_G^{{\sigma }_{\mathrm{\Lambda }}}(v)$

$=$ $K_G^{{\sigma }_{\mathrm{\Lambda }}}(u,v).\mathit{∎}$

附录 C $\mathrm{\Psi }$ 的技术引理

以下引理意味着由 Eq. 4 给出的势 $\mathrm{\Psi }$ 是明确定义的。

Lemma 32.

对于所有 $\beta ,\gamma >0$ 这样的 ，我们有

证明。

对于 $+\mathrm{\infty }$ 一侧，我们有

类似地，对于 $-\mathrm{\infty }$ 一侧，我们有

附录D势法混合：24的证明

在本节中，我们以与 5 相同的方式证明 24，如 Section 3 中所述。 这里的主要区别是我们考虑绝对影响的加权和 ${\Sigma }_{v\epsilon V\backslash \mathrm{\Lambda }}$ρv⋅|ℐGσΛ​ (r​ → ​v)| 其中 $\rho :V\to {ℝ}^{+}$ 是权重函数。 这足以让我们限制影响矩阵的特征值，如 22 所示。 我们将选择顶点$v$的权重为${\rho }_v={\mathrm{\Delta }}_v$，度为$v$。给定一般的$(\alpha ,c)$势，以下引理为我们提供了对距离$k$的绝对影响的加权和的上限。 特别是，它概括了9。

Lemma 33.

如果存在关于$\mathrm{\Delta }$和$(\beta ,\gamma ,\lambda )$的一般$(\alpha ,c)$-潜在函数$\mathrm{\Psi }$，其中$\alpha \in (0,1)$和$c>0$，然后对于每个 $\mathrm{\Lambda }\subseteq V_T\backslash \{r\}$、${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 和所有整数 $k\ge 1$，

$$\sum _{v\in L_r(k)}{\mathrm{\Delta }}_v\cdot \left|{ℐ}_T^{{\sigma }_{\mathrm{\Lambda }}}(r\to v)\right|\le 2c\cdot {(1-\alpha )}^{k-1}\cdot {\mathrm{\Delta }}_r$$

其中$L_r(k)$表示距$r$距离为$k$的所有自由顶点的集合。

为了证明33，我们首先声明对于任何权重函数$\rho$的14的以下推广。 34 的证明与 14 相同，此处省略。

Lemma 34.

令 $\mathrm{\Psi }:[-\mathrm{\infty },+\mathrm{\infty }]\to (-\mathrm{\infty },+\mathrm{\infty })$ 为具有图像 $S=\mathrm{\Psi }[-\mathrm{\infty },+\mathrm{\infty }]$ 和导数 $\psi ={\mathrm{\Psi }}^{\prime }$ 的可微且递增（势）函数。 用${\mathrm{\Delta }}_r$表示根$r$的次数。 然后对于每个整数 $k\ge 1$，

在哪里

$$A_{\mathrm{\Psi }}=\underset{u\in L_r(1)}{\max }\left\{\frac{|h(\log R_u)|}{\psi (\log R_u)}\right\}\text{and}{B}_{\mathrm{\Psi }}^{\rho }=\underset{v\in L_r(k)}{\max }\left\{{\rho }_v\cdot \psi (\log R_v)\right\}.$$

然后我们证明33和24。

33 的证明。

用${\mathrm{\Delta }}_v$表示顶点$v\in V_T\backslash \{r\}$的度数，用$d_v={\mathrm{\Delta }}_v-1$表示子树$T_v$中$v$的度数>。 为所有 $v\in V_T$ 选择顶点权重为 ${\rho }_v={\mathrm{\Delta }}_v$。 由于 $\mathrm{\Psi }$ 是一般的 $(\alpha ,c)$ 势，因此 收缩 条件意味着

由于 $\log R_v\in J_{d_v}$ 根据 $J_d$ 的定义，一般有界性条件意味着对于所有 $u\in L_r(1)$ 和 $v\in L_r(k)$ ,

$$\frac{\psi (\log R_v)}{\psi (\log R_u)}\cdot |h(\log R_u)|\le \frac{2c}{{\mathrm{\Delta }}_u+{\mathrm{\Delta }}_v}.$$

因此，我们得到

$${\mathrm{\Delta }}_r{A}_{\mathrm{\Psi }}{B}_{\mathrm{\Psi }}^{\rho }={\mathrm{\Delta }}_r\cdot \underset{u\in L_r(1)}{\max }\left\{\frac{|h(\log R_u)|}{\psi (\log R_u)}\right\}\cdot \underset{v\in L_r(k)}{\max }\left\{{\mathrm{\Delta }}_v\cdot \psi (\log R_v)\right\}\le 2c\cdot {\mathrm{\Delta }}_r.$$

引理紧随 34 而来。 ∎

24 的证明。

24 的证明几乎与 5 相同。 我们指出，这里唯一的区别是我们考虑给定顶点的绝对影响的加权和。 由于 SAW 树保留了顶点度数，因此我们仍然可以应用 8。 然后，结合7、22、8和33，我​​们完成了定理的证明。 ∎

附录E验证良好的潜力：有界性

在本小节中，我们将展示由 Eq. 定义的势函数 $\mathrm{\Psi }$ 的有界性 或一般有界性 条件。 > 4 在不同的参数范围内。 结合19，我们完成了10和25的证明。

在节 E.1中，我们以[LLY13]的工作为基础，介绍了参数$(\beta ,\gamma ,\lambda )$唯一性区域的背景。 然后，我们在部分E.2中显示有界性和一般有界性。 技术引理的证明留给部分E.3。

E.1 唯一性区域的预备知识

在本节中，我们简要描述参数$(\beta ,\gamma ,\lambda )$的唯一性区域。 这里的所有结果及其证明可以在最新版本的[LLY13]的引理21中找到。

令 $\mathrm{\Delta }\ge 3$ 为整数，$\beta ,\gamma ,\lambda$ 为实数。 我们假设 $0\le \beta \le \gamma$、$\gamma >0$、 和 $\lambda >0$。 对于 $1\le d\le \mathrm{\Delta }$ 定义

$$f_d(R)=\lambda {\left(\frac{\beta R+1}{R+\gamma }\right)}^d$$

并用$R_d^{\ast }$表示$f_d$的唯一不动点。 回想一下，如果 对于所有 都是唯一的，那么参数 $(\beta ,\gamma ,\lambda )$ 直至 $\mathrm{\Delta }$ 都是唯一的，间隙为 $\delta \in (0,1)$ 。

当$\beta =0$时，自旋系统称为硬约束模型。 在这种情况下，存在一个外部场的临界阈值，定义为

当且仅当 时，参数 $(0,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一。 特别是，当 $\gamma \le 1$ 临界字段由下式给出时

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

当$\beta >0$时，自旋系统称为软约束模型。 如果 $\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$，则 $(\beta ,\gamma ,\lambda )$ 对于所有 $\lambda >0$ 来说最多是唯一的 $\mathrm{\Delta }$。 如果$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$唯一性区域更加复杂，我们现在描述。 让

$$\overline{\mathrm{\Delta }}=\frac{1+\sqrt{\beta \gamma }}{1-\sqrt{\beta \gamma }},$$

这样对于每个 我们有 ，对于每个 $d\ge \overline{\mathrm{\Delta }}$ 我们有 $d\cdot \frac{1-\sqrt{\beta \gamma }}{1+\sqrt{\beta \gamma }}\ge 1$。 对于每个 ，我们将 $x_1(d)\le x_2(d)$ 定义为二次方程的两个正根

$$\frac{d(1-\beta \gamma )x}{(\beta x+1)(x+\gamma )}=1.$$

更具体地说，$x_1(d)$ 和 $x_2(d)$ 由下式给出

$$x_1(d)=\frac{\theta (d)-\sqrt{\theta {(d)}^2-4\beta \gamma }}{2\beta }\text{and}{x}_2(d)=\frac{\theta (d)+\sqrt{\theta {(d)}^2-4\beta \gamma }}{2\beta }$$

在哪里

$$\theta (d)=d(1-\beta \gamma )-(1+\beta \gamma ).$$

请注意，$\theta (d)\ge 2\sqrt{\beta \gamma }$ 适用于所有 $d\ge \overline{\mathrm{\Delta }}$。 对于 $i=1,2$ 我们让

$${\lambda }_i(d)=x_i(d){\left(\frac{x_i(d)+\gamma }{\beta x_i(d)+1}\right)}^d.$$

然后，当且仅当 $\lambda$ 属于以下状态时，参数 $(\beta ,\gamma ,\lambda )$ 最多是唯一的$\mathrm{\Delta }$

(10)

特别是，当 $\gamma \le 1$ 存在两个关键阈值 时，参数 $(\beta ,\gamma ,\lambda )$ 最多可达 $\mathrm{\Delta }$ 唯一，当且仅当如果 或 $\lambda >{\overline{\lambda }}_c$（即 $𝒜=(0,{\lambda }_c)\cup ({\overline{\lambda }}_c,\mathrm{\infty })$)，其中

以下关键字段的界限对我们稍后的证明很有帮助。

Lemma 35.

1. 如果 $\beta =0$，则对于每个整数 $d$ 使得 我们有

   $${\lambda }_c\le \frac{4{\gamma }^{d+1}}{d-1}.$$

2. 如果 $\beta >0$ 和 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$，则对于每个整数 $d$这样我们有

   $${\lambda }_1(d)\le \frac{18{\gamma }^{d+1}}{\theta (d)}\text{and}{\lambda }_2(d)\ge \frac{\theta (d)}{18{\beta }^{d+1}}$$

   其中$\theta (d)=d(1-\beta \gamma )-(1+\beta \gamma )$。

35的证明被推迟到SectionE.3。

E.2 有界性证明

本节我们通过在相应范围内建立有界性和一般有界性来完成10和25的证明参数。

令 $\mathrm{\Delta }\ge 3$ 为整数。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$。 回想一下，势函数 $\mathrm{\Psi }$ 定义为

$${\mathrm{\Psi }}^{\prime }(y)=\psi (y)=\sqrt{\frac{(1-\beta \gamma )e^y}{(\beta e^y+1)(e^y+\gamma )}}=\sqrt{\left|h(y)\right|},\mathrm{\Psi }(0)=0.$$ (1)

令人惊讶的是发现$\psi =\sqrt{|h|}$，因为潜在的$\mathrm{\Psi }$正是[LLY13]中的那个，如17所示>。 这似乎不是巧合，它提供了一些直觉，说明为什么 [LLY13] 的潜力有效。 更重要的是，$\psi =\sqrt{|h|}$这一事实有助于我们证明有界性和一般有界性。 回想一下，对于 和 ，我们让 $J_d=[\log (\lambda {\beta }^d),\log (\lambda /{\gamma }^d)]$ 为具有 $d$ 子节点的顶点的对数边际比范围。 然后对于每个 和 $y_i\in J_{d_i}$ 其中 $i=1,2$，我们有

$$\frac{\psi (y_2)}{\psi (y_1)}\cdot |h(y_1)|=\sqrt{|h(y_1)|\cdot |h(y_2)|}.$$ (11)

下面的引理给出了 $\sqrt{|h(y_1)|\cdot |h(y_2)|}$ 的上限，从中和 Eq. 11 我们推导出 有界性 和一般有界性 立即。 引理中的括号指示边界应用于哪个引理。

Lemma 36.

令 $\mathrm{\Delta }\ge 3$ 为整数。 令$\beta ,\gamma ,\lambda$为实数，使得$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$。 假设参数 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，间隙为 $\delta \in (0,1)$。 那么对于所有整数 $d_1,d_2$ 使得 以及所有实数 $y_i\in J_{d_i}$ 其中 $i=1,2$，以下成立：

1. 硬约束模型： $\beta =0$和。

   1. (10) 如果 $\gamma \le 1$，则

      $$|h(y_1)|\le \frac{4}{\mathrm{\Delta }}.$$

   2. (25) 如果 $\gamma >1$，则

      $$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{8}{d_1+d_2+2}.$$

2. 软约束模型： $\beta >0$和$\lambda \in 𝒜$。

   1. (10) 如果 $\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$，则

      $$|h(y_1)|\le \frac{1.5}{\mathrm{\Delta }}.$$

   2. (10) 如果 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma \le 1$ ，那么

      $$|h(y_1)|\le \frac{18}{\mathrm{\Delta }}.$$

   3. (25) 如果 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma >1$ ，那么

      $$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{36}{d_1+d_2+2}.$$

下面的引理很有帮助，其证明可以在 Section E.3 中找到。

Lemma 37.

对于每个 $y\in [-\mathrm{\infty },+\mathrm{\infty }]$ 我们有

$$|h(y)|=\frac{|1-\beta \gamma |e^y}{(\beta e^y+1)(e^y+\gamma )}\le \frac{|1-\sqrt{\beta \gamma }|}{1+\sqrt{\beta \gamma }}.$$

我们在这里给出36的证明。

36 的证明。

我们使用部分E.1中的符号和结果。

H. 硬约束模型：$\beta =0$ 和 。

H.1。 $\gamma \le 1$。

对于每个 $y_1\in J_{d_1}$，我们从 35 推断出

$$e^{y_1}\le \frac{\lambda }{{\gamma }^{d_1}}\le \frac{{\lambda }_c}{{\gamma }^{\mathrm{\Delta }-1}}\le \frac{4\gamma }{\mathrm{\Delta }-2}.$$

因此，

$$|h(y_1)|=\frac{e^{y_1}}{e^{y_1}+\gamma }\le \frac{\frac{4\gamma }{\mathrm{\Delta }-2}}{\frac{4\gamma }{\mathrm{\Delta }-2}+\gamma }=\frac{4}{\mathrm{\Delta }+2}\le \frac{4}{\mathrm{\Delta }}.$$

H.2。 $\gamma >1$。

让 $\overline{y}=\frac{y_1+y_2}{2}$ 和 $\overline{d}=\frac{d_1+d_2}{2}$。 然后我们得到

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}=\sqrt{\frac{e^{y_1}}{e^{y_1}+\gamma }}\cdot \sqrt{\frac{e^{y_2}}{e^{y_2}+\gamma }}=\frac{1}{\sqrt{(1+\gamma e^{-y_1})(1+\gamma e^{-y_2})}}\le \frac{1}{1+\gamma e^{-\overline{y}}},$$

其中最后一个不等式由 AM-GM 不等式得出

$$(1+\gamma e^{-y_1})(1+\gamma e^{-y_2})=1+\gamma (e^{-y_1}+e^{-y_2})+{\gamma }^2{e}^{-2\overline{y}}\ge 1+2\gamma e^{-\overline{y}}+{\gamma }^2{e}^{-2\overline{y}}={(1+\gamma e^{-\overline{y}})}^2.$$

由于 $y_i\in J_{d_i}$ 对于 $i=1,2$，我们有

$$e^{\overline{y}}=\sqrt{e^{y_1}\cdot e^{y_2}}\le \sqrt{\frac{\lambda }{{\gamma }^{d_1}}\cdot \frac{\lambda }{{\gamma }^{d_2}}}=\frac{\lambda }{{\gamma }^{\overline{d}}}.$$

如果$\overline{d}\ge 2$，那么我们从35和$\gamma >1$推断出

$$e^{\overline{y}}\le \frac{{\lambda }_c}{{\gamma }^{\lfloor \overline{d}\rfloor }}\le \frac{4\gamma }{\lfloor \overline{d}\rfloor -1}.$$

它遵循

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1}{1+\gamma e^{-\overline{y}}}\le \frac{1}{1+\frac{\lfloor \overline{d}\rfloor -1}{4}}=\frac{4}{\lfloor \overline{d}\rfloor +3}\le \frac{8}{d_1+d_2+2}.$$

如果，那么很容易看出

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le 1\le \frac{8}{d_1+d_2+2}.$$

S. 软约束模型：$\beta >0$ 和 $\lambda \in 𝒜$。

S.1。 $\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$。

对于每个 $y_1\in J$，我们从 37 推断出

$$|h(y_1)|\le \frac{1-\sqrt{\beta \gamma }}{1+\sqrt{\beta \gamma }}\le \frac{1}{\mathrm{\Delta }-1}\le \frac{1.5}{\mathrm{\Delta }}.$$

S.2。 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma \le 1$。

在本例中，我们有 或 $\lambda >{\overline{\lambda }}_c$，其中 ${\lambda }_c,{\overline{\lambda }}_c$ 是两个关键字段。 首先考虑$\lambda >{\overline{\lambda }}_c$。 对于每个 $y_1\in J_{d_1}$，我们从 35 和 推断出

$$e^{y_1}\ge \lambda {\beta }^{d_1}\ge {\overline{\lambda }}_c{\beta }^{\mathrm{\Delta }-1}\ge \frac{\theta (\mathrm{\Delta }-1)}{18\beta }$$

其中$\theta (d)=d(1-\beta \gamma )-(1+\beta \gamma )$。 因此，

$|h(y_1)|={\displaystyle \frac{(1-\beta \gamma )e^{y_1}}{(\beta e^{y_1}+1)(e^{y_1}+\gamma )}}$ $={\displaystyle \frac{1-\beta \gamma }{\beta e^{y_1}+\gamma e^{-y_1}+(1+\beta \gamma )}}$

$\le {\displaystyle \frac{1-\beta \gamma }{\frac{\theta (\mathrm{\Delta }-1)}{18}+(1+\beta \gamma )}}={\displaystyle \frac{18(1-\beta \gamma )}{(\mathrm{\Delta }-1)(1-\beta \gamma )+17(1+\beta \gamma )}}\le {\displaystyle \frac{18}{\mathrm{\Delta }}}.$

接下来我们考虑。 对于每个 $y_1\in J_{d_1}$，我们从 35 和 $\gamma \le 1$ 推断出

$$e^{y_1}\le \frac{\lambda }{{\gamma }^{d_1}}\le \frac{{\lambda }_c}{{\gamma }^{\mathrm{\Delta }-1}}\le \frac{18\gamma }{\theta (\mathrm{\Delta }-1)}.$$

因此，

$$|h(y_1)|=\frac{1-\beta \gamma }{\beta e^{y_1}+\gamma e^{-y_1}+(1+\beta \gamma )}\le \frac{1-\beta \gamma }{\frac{\theta (\mathrm{\Delta }-1)}{18}+(1+\beta \gamma )}\le \frac{18}{\mathrm{\Delta }}.$$

S.3。 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 和 $\gamma >1$。

让 $\overline{y}=\frac{y_1+y_2}{2}$、$\overline{d}=\frac{d_1+d_2}{2}$、$d_L=\lfloor \overline{d}\rfloor$ 和 $d_R=\lceil \overline{d}\rceil$。 我们首先考虑一些简单的情况。 如果$\overline{d}\le 2$那么很容易看出

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le 1\le \frac{6}{d_1+d_2+2}.$$

如果 $\overline{d}>2$ 和 $d_L\le \overline{\mathrm{\Delta }}$，那么我们从 37 推断出

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1-\sqrt{\beta \gamma }}{1+\sqrt{\beta \gamma }}=\frac{1}{\overline{\mathrm{\Delta }}}\le \frac{2}{d_1+d_2-2}\le \frac{6}{d_1+d_2+2}.$$

因此，下面我们可以假设$\overline{d}>2$和$d_L>\overline{\mathrm{\Delta }}$。

由于参数 $(\beta ,\gamma ,\lambda )$ 直至 $\mathrm{\Delta }$ 都是唯一的，因此我们有 $\lambda \in 𝒜$ 其中的制度 $𝒜$ 由 Eq. 10 给出。 观察一下

$$𝒜\subseteq (0,{\lambda }_1(d_L))\cup ({\lambda }_2(d_R),\mathrm{\infty })\cup ({\lambda }_2(d_L),{\lambda }_1(d_R))$$

其中最后一个间隔仅在 时才为非空。 这意味着 $\lambda$ 至少包含在三个间隔之一中。 我们通过分别考虑这三种情况来建立界限。

情况 1：。 根据柯西-施瓦茨不等式，我们有

$\sqrt{|h(y_1)|\cdot |h(y_2)|}$ $=\sqrt{{\displaystyle \frac{1-\beta \gamma }{\beta e^{y_1}+\gamma e^{-y_1}+(1+\beta \gamma )}}}\cdot \sqrt{{\displaystyle \frac{1-\beta \gamma }{\beta e^{y_2}+\gamma e^{-y_2}+(1+\beta \gamma )}}}$

$\le {\displaystyle \frac{1-\beta \gamma }{\sqrt{(\beta e^{y_1}+\gamma e^{-y_1})(\beta e^{y_2}+\gamma e^{-y_2})}+(1+\beta \gamma )}}.$ (12)

因此，我们得到

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1-\beta \gamma }{\gamma e^{-\overline{y}}+(1+\beta \gamma )}.$$

由于$y_i\in J_{d_i}$对于$i=1,2$和$\gamma >1$，我们从35推断出

$$e^{\overline{y}}\le \frac{\lambda }{{\gamma }^{\overline{d}}}\le \frac{{\lambda }_1(d_L)}{{\gamma }^{d_L}}\le \frac{18\gamma }{\theta (d_L)},$$

其中$\theta (d_L)=d_L(1-\beta \gamma )-(1+\beta \gamma )$。 它遵循

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1-\beta \gamma }{\gamma e^{-\overline{y}}+(1+\beta \gamma )}\le \frac{1-\beta \gamma }{\frac{\theta (d_L)}{18}+(1+\beta \gamma )}\le \frac{36}{d_1+d_2+2}.$$

情况 2：$\lambda >{\lambda }_2(d_R)$。 类似地，我们从 Eq. 12 得到

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1-\beta \gamma }{\beta e^{\overline{y}}+(1+\beta \gamma )}.$$

由于$y_i\in J_{d_i}$对于$i=1,2$和，我们从35推断出

$$e^{\overline{y}}\ge \lambda {\beta }^{\overline{d}}\ge {\lambda }_2(d_R){\beta }^{d_R}\ge \frac{\theta (d_R)}{18\beta },$$

其中$\theta (d_R)=d_R(1-\beta \gamma )-(1+\beta \gamma )$。 它遵循

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1-\beta \gamma }{\beta e^{\overline{y}}+(1+\beta \gamma )}\le \frac{1-\beta \gamma }{\frac{\theta (d_R)}{18}+(1+\beta \gamma )}\le \frac{36}{d_1+d_2+2}.$$

情况 3：。 我们可以假设$d_1\ge d_2$。 通过 Eq. 12，我们得到

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1-\beta \gamma }{\sqrt{\beta \gamma }{e}^{\frac{y_2-y_1}{2}}+(1+\beta \gamma )}.$$

由于 $y_i\in J_{d_i}$ 对于 $i=1,2$ 和 ，我们有

$$e^{y_2-y_1}\ge {\beta }^{d_2}{\gamma }^{d_1}\ge {\beta }^{d_L}{\gamma }^{d_R}.$$

同时，我们从 35 推断出

这意味着

$$\sqrt{\beta \gamma }{e}^{\frac{y_2-y_1}{2}}\ge \sqrt{{\beta }^{d_L+1}{\gamma }^{d_R+1}}\ge \frac{\sqrt{\theta (d_L)\theta (d_R)}}{18}\ge \frac{\theta (d_L)}{18}.$$

它遵循

$$\sqrt{|h(y_1)|\cdot |h(y_2)|}\le \frac{1-\beta \gamma }{\sqrt{\beta \gamma }{e}^{\frac{y_2-y_1}{2}}+(1+\beta \gamma )}\le \frac{1-\beta \gamma }{\frac{\theta (d_L)}{18}+(1+\beta \gamma )}\le \frac{36}{d_1+d_2+2}.\mathit{∎}$$

E.3 技术引理的证明

35 的证明。

1. 对于每个 我们有

$${\lambda }_c\le \frac{{\gamma }^{d+1}{d}^d}{{(d-1)}^{d+1}}=\frac{{\gamma }^{d+1}}{d-1}{\left(\frac{d}{d-1}\right)}^d\le \frac{4{\gamma }^{d+1}}{d-1},$$

对于所有整数 $d>1$，最后一个不等式是从 ${(\frac{d}{d-1})}^d\le 4$ 得出的。

2. 对于每个 我们有

$$x_1(d)=\frac{2\gamma }{\theta (d)+\sqrt{\theta {(d)}^2-4\beta \gamma }}\le \frac{2\gamma }{\theta (d)}.$$

观察函数 $\frac{x+\gamma }{\beta x+1}$ 在 时在 $x$ 中单调递增，因此我们推断

$$\frac{x_1(d)+\gamma }{\beta x_1(d)+1}\le \frac{\frac{2\gamma }{\theta (d)}+\gamma }{\frac{2\beta \gamma }{\theta (d)}+1}=\gamma \cdot \frac{2+d(1-\beta \gamma )-(1+\beta \gamma )}{2\beta \gamma +d(1-\beta \gamma )-(1+\beta \gamma )}=\gamma \cdot \frac{d+1}{d-1}.$$

所以，

$${\lambda }_1(d)=x_1(d){\left(\frac{x_1(d)+\gamma }{\beta x_1(d)+1}\right)}^d\le \frac{2\gamma }{\theta (d)}\cdot {\gamma }^d\cdot {\left(\frac{d+1}{d-1}\right)}^d\le \frac{18{\gamma }^{d+1}}{\theta (d)}$$

对于所有整数 $d>1$，最后一个不等式是从 ${(\frac{d+1}{d-1})}^d\le 9$ 得出的。

第二部分可类似证明。 对于每个 我们有

$$x_2(d)=\frac{\theta (d)+\sqrt{\theta {(d)}^2-4\beta \gamma }}{2\beta }\ge \frac{\theta (d)}{2\beta },$$

因此，

$$\frac{x_2(d)+\gamma }{\beta x_2(d)+1}\ge \frac{\frac{\theta (d)}{2\beta }+\gamma }{\frac{\theta (d)}{2}+1}=\frac{1}{\beta }\cdot \frac{d(1-\beta \gamma )-(1+\beta \gamma )+2\beta \gamma }{d(1-\beta \gamma )-(1+\beta \gamma )+2}=\frac{1}{\beta }\cdot \frac{d-1}{d+1}.$$

然后我们得出结论：

$${\lambda }_2(d)=x_2(d){\left(\frac{x_2(d)+\gamma }{\beta x_2(d)+1}\right)}^d\ge \frac{\theta (d)}{2\beta }\cdot \frac{1}{{\beta }^d}\cdot {\left(\frac{d-1}{d+1}\right)}^d\ge \frac{\theta (d)}{18{\beta }^{d+1}},$$

对于所有整数 $d>1$，最后一个不等式再次从 ${(\frac{d+1}{d-1})}^d\le 9$ 得出。 ∎

37 的证明。

我们从 AM-GM 不等式推断出

$$|h(y)|=\frac{|1-\beta \gamma |}{\beta e^y+\gamma e^{-y}+1+\beta }\le \frac{|1-\beta \gamma |}{2\sqrt{\beta \gamma }+1+\beta }=\frac{|1-\sqrt{\beta \gamma }|}{1+\sqrt{\beta \gamma }}.\mathit{∎}$$

附录F铁磁情况的证明

F.1 26的证明

26 的证明。

自始至终，我们都使用“微不足道的势”函数$\mathrm{\Psi }(y)=y$。 请注意，$\psi (y)=1$ 是一个常数函数。 现在，我们证明收缩和有界性。 我们分为三种情况。

1. 我们首先证明Contraction部分。 到37，对于所有$y\in [-\mathrm{\infty },+\mathrm{\infty }]$，我们有

   $$\left|h(y)\right|\le \frac{|1-\sqrt{\beta \gamma }|}{1+\sqrt{\beta \gamma }}\le \frac{1-\delta }{\mathrm{\Delta }-1}.$$

   现在让我们证明有界性条件。 由上面的不等式我们有

   $$\left|h(y)\right|\le \frac{1}{\mathrm{\Delta }-1}\le \frac{1.5}{\mathrm{\Delta }}$$

   对于$\mathrm{\Delta }\ge 3$。

2. 对于 Contraction 部分，从 $\log (\lambda \max \{1,1/{\gamma }^{\mathrm{\Delta }-1}\})\le y_i\le \log (\lambda \max \{1,{\beta }^{\mathrm{\Delta }-1}\})$ 开始，我们有

   $\left|{\displaystyle \frac{\partial H_d(𝒚)}{\partial y_i}}\right|$ $=\left|h(y_i)\right|={\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\gamma e^{-y_i}+\beta e^{y_i}}}\le {\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\gamma e^{-y_i}}}$

   $\le {\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\frac{\gamma }{\lambda \max \{1,{\beta }^{\mathrm{\Delta }-1}\}}}}.$

   由于我们假设 $\lambda \le (1-\delta )\frac{\gamma }{\max \{1,{\beta }^{\mathrm{\Delta }-1}\}\cdot ((\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta })}$，因此我们有上限

   ${\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{1-\delta }}}$ $=(1-\delta ){\displaystyle \frac{\beta \gamma -1}{(\mathrm{\Delta }-1-\delta )\beta \gamma -(\mathrm{\Delta }-1+\delta )}}$

   $=(1-\delta ){\displaystyle \frac{\beta \gamma -1}{(\mathrm{\Delta }-1-\delta )(\beta \gamma -1)+2\delta }}$

   $\le {\displaystyle \frac{1-\delta }{\mathrm{\Delta }-1-\delta }}\le (1-\mathrm{\Theta }(\delta )){\displaystyle \frac{1}{\mathrm{\Delta }-1}}.$

   现在，我们证明有界性条件。 请注意，从 $\lambda \le \frac{\gamma }{\max \{1,{\beta }^{\mathrm{\Delta }-1}\}\cdot ((\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta })}$ 开始，就得出 $y\le \log (\lambda \max \{1,{\beta }^{\mathrm{\Delta }-1}\})\le \log \left(\frac{\gamma }{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}\right)$。 简单的计算表明 $\frac{\gamma }{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}\le \sqrt{\frac{\gamma }{\beta }}$ ，因此到 37 时，我们有

   $\left|h(y)\right|$ $\le \left|h\left(\log \left({\displaystyle \frac{\gamma }{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}}\right)\right)\right|\le {\displaystyle \frac{(\beta \gamma -1)e^{\log \left(\frac{\gamma }{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}\right)}}{e^{\log \left(\frac{\gamma }{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}\right)}+\gamma }}$

   $=(\beta \gamma -1){\displaystyle \frac{1}{1+(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}}={\displaystyle \frac{\beta \gamma -1}{(\mathrm{\Delta }-2)(\beta \gamma -1)-1}}\le O(1/\mathrm{\Delta }).$

3. 对于 Contraction 部分，从 $\log (\lambda \max \{1,1/{\gamma }^{\mathrm{\Delta }-1}\})\le y_i\le \log (\lambda \max \{1,{\beta }^{\mathrm{\Delta }-1}\})$ 开始，我们有

   $\left|{\displaystyle \frac{\partial H_d(𝒚)}{\partial y_i}}\right|$ $=\left|h(y_i)\right|={\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\gamma e^{-y_i}+\beta e^{y_i}}}\le {\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\beta e^{y_i}}}$

   $\le {\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\beta \lambda \max \{1,1/{\gamma }^{\mathrm{\Delta }-1}\}}}.$

   由于我们假设 $\lambda \ge \frac{1}{1-\delta }\cdot \frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{\beta \cdot \min \{1,1/{\gamma }^{\mathrm{\Delta }-1}\}}$，因此我们有上限

   ${\displaystyle \frac{\beta \gamma -1}{1+\beta \gamma +\frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{1-\delta }}}$

   正如我们在上面的情况 2 中计算的那样，它的上限再次为 $(1-\mathrm{\Theta }(\delta ))\frac{1}{\mathrm{\Delta }-1}$。

   现在，我们证明有界性条件。 请注意，从 $\lambda \ge \frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{\beta \min \{1,1/{\gamma }^{\mathrm{\Delta }-2}}$ 开始，就得出 $y\ge \log (\lambda \min \{1,1/{\gamma }^{\mathrm{\Delta }-1}\}\ge \log \left(\frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{\beta }\right)$。 简单的计算表明 $\frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{\beta }\ge \sqrt{\frac{\gamma }{\beta }}$ ，因此到 37 时，我们有

   $\left|h(y)\right|$ $\le \left|h\left(\log \left({\displaystyle \frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{\beta }}\right)\right)\right|\le (\beta \gamma -1){\displaystyle \frac{1}{\beta \cdot \frac{(\mathrm{\Delta }-2)\beta \gamma -\mathrm{\Delta }}{\beta }+1}}$

   $={\displaystyle \frac{\beta \gamma -1}{(\mathrm{\Delta }-2)(\beta \gamma -1)-1}}\le O(1/\mathrm{\Delta }).\mathit{∎}$

F.2 27的证明

在本小节中，我们使用 [GL18] 的结果来证明 27。 它们的潜在函数由其边际比率的导数隐式定义为

${\mathrm{\Phi }}^{\prime }(R)=\varphi (R)=\min \{{\displaystyle \frac{\beta \gamma -1}{\alpha \gamma \log \frac{\lambda +\gamma }{\beta \lambda +1}}},{\displaystyle \frac{1}{R\log \frac{\lambda }{R}}}\}$

对于仅依赖于 $\beta ,\gamma ,\lambda$ 的常量 $0\le \alpha \le 1$（有关精确定义，请参阅 [GL18])。 在我们的背景下，对数比率的相应潜力是

${\mathrm{\Psi }}^{\prime }(y)=\psi (y)=e^y\varphi (e^y)=\min \{{\displaystyle \frac{\beta \gamma -1}{\alpha \gamma \log \frac{\lambda +\gamma }{\beta \lambda +1}}}{e}^y,{\displaystyle \frac{1}{\log \frac{\lambda }{e^y}}}\}$

并且受常数限制，具体取决于 $\log (\lambda /{\gamma }^{\mathrm{\Delta }-1})\le y\le \log \lambda$ 的 $\beta ,\gamma ,\lambda ,\mathrm{\Delta }$。

[GL18] 中的主要技术成果之一是表明树递归与势函数 $\mathrm{\Phi }$ 收缩，导数 $\varphi$ 的边界为存在仅依赖于 $\beta ,\gamma ,\lambda$ 的正常数 $C_1,C_2$ 的感觉，使得 $C_1\le \varphi (R)\le C_2$ 对于所有 $0\le R\le \lambda$ 而言。 [GL18]将此类函数称为通用势函数。

在我们的上下文中，我们可以得到 $\mathrm{\Psi }$ 是一个 $(\alpha ,c)$ 势函数，它满足 4，但有一个取决于 $\gamma ,\mathrm{\Delta }$ 的常数 $c$。 事实上，最坏的情况，我们有

$\underset{y_1,y_2}{\max }{\displaystyle \frac{\psi (y_2)}{\psi (y_1)}}\ge {\displaystyle \frac{\psi (\log \lambda )}{\psi (\log (\lambda /{\gamma }^{\mathrm{\Delta }-1}))}}={\displaystyle \frac{\lambda \frac{\beta \gamma -1}{\alpha \gamma \log \frac{\lambda +\gamma }{\beta \lambda +1}}}{\frac{\beta \gamma -1}{\alpha \log \frac{\lambda +\gamma }{\beta \lambda +1}}\cdot \frac{\lambda }{{\gamma }^{\mathrm{\Delta }}}}}={\gamma }^{\mathrm{\Delta }-1}.$

更准确地说，我们从 [GL18] 得到以下结果，以对数边际比率表示。

Theorem 38.

假设$\beta ,\gamma ,\lambda$是满足$\beta \le 1\le \gamma$、$\sqrt{\beta \gamma }\ge 1$和的非负实数。 那么对于取决于 $\beta ,\gamma ,\lambda$ 的常数 和取决于 $\beta ,\gamma ,\lambda ,\mathrm{\Delta }$ 的常数 $c>0$ 来说，函数 $\mathrm{\Psi }$ 是一个 $(\alpha ,c)$ 势函数。

与5结合，这使得$O(n^C)$与仅取决于$\beta ,\gamma ,\lambda ,\mathrm{\Delta }$的常量$C$混合。 我们注意到这比[GL18]中的相关性衰减结果弱，因为$C$不依赖于$\mathrm{\Delta }$，因此对于任意图表。

附录 G 混合速度稍快

在本节中，我们通过更仔细地考虑我们基于收缩证明的（非平凡）谱独立性界限与我们获得的（平凡）谱独立性界限之间的权衡，稍微优化某些反铁磁2自旋系统的混合时间结果在 Section A.2 中用于处理恒定大小的图形。

Proposition 39。

假设 $[n]$ 子集上的分布 $\mu$ 对于 ${\eta }_i\le \min \{a,(n-i-1)b\}$ 来说是 $({\eta }_0,\mathrm{\dots },{\eta }_{n-2})$ 谱独立的，对于某些 $a\ge 0$ 和$0\le b\le 1$。 那么从$\mu$采样的格劳伯动力学具有至少$\frac{1}{n}\cdot \mathrm{\Omega }{\left(\frac{a}{bn}\right)}^a$的谱间隙

证明。

假设我们已经以 $c$ 为条件，将元素的一部分“输入/输出”。 所得分布既是$b(1-c)n$-光谱独立的，又是$a$-光谱独立的。 边界$b(1-c)n$优于$a$的确切阈值$c$由下式给出

$c=1-{\displaystyle \frac{a}{bn}}$

我们注意到这样的 $c$ 仅在 $0\le 1-\frac{a}{bn}\le 1$ 或等效的 $bn\ge a$ 时才有意义。 现在，我们基于固定至多 $c$ 顶点分数，对所有条件分布应用 $a$ 谱独立界限。 否则我们应用$(n-i-1)b$-谱独立性。 我们获得最终的光谱间隙下界

${\displaystyle \frac{1}{n}}\cdot {(1-b)}^{(1-c)n}\cdot {\displaystyle \prod _{k=0}^{cn}}\left(1-{\displaystyle \frac{a}{n-k-1}}\right)$

观察一下

${(1-b)}^{(1-c)n}={(1-b)}^{\frac{a}{b}}\gtrsim \exp (-a)$

我们还有

${\displaystyle \prod _{k=0}^{cn}}\left(1-{\displaystyle \frac{a}{n-k-1}}\right)$ $\gtrsim \exp \left(-a{\displaystyle \sum _{k=0}^{cn}}{\displaystyle \frac{1}{n-k-1}}\right)$

$\gtrsim \exp \left(-a\left(\underset{\approx \log n}{\underbrace{{\displaystyle \sum _{k=0}^{n-2}}{\displaystyle \frac{1}{n-k-1}}}}-\underset{\approx \log (1-c)n}{\underbrace{{\displaystyle \sum _{k=cn+1}^{n-2}}{\displaystyle \frac{1}{n-k-1}}}}\right)\right)$

$\gtrsim \exp \left(-a\cdot \log {\displaystyle \frac{1}{1-c}}\right)$

$\gtrsim \exp \left(-a\log {\displaystyle \frac{bn}{a}}\right)$

$\gtrsim {\left({\displaystyle \frac{a}{bn}}\right)}^a$

将它们放在一起，我们就得到了所需的下界。 ∎

有了这个结果，我们可以将其应用于具有 $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }},\gamma \le 1$ 和 $\beta =0,\gamma \le 1$ 的反铁磁模型，因为查看 28 的证明，我们有这样的系统 $Cn$-大致与$C\le O(1/\mathrm{\Delta })$光谱无关。

Corollary 40 （软约束）。

修复整数$\mathrm{\Delta }\ge 3$、。 令$\beta ,\gamma ,\lambda \ge 0$为满足$\frac{\overline{\mathrm{\Delta }}-2}{\overline{\mathrm{\Delta }}}\le \sqrt{\beta \gamma }\le \frac{\overline{\mathrm{\Delta }}-1}{\overline{\mathrm{\Delta }}+1}$和$\gamma \le 1$的非负实数。 进一步假设 $(\beta ,\gamma ,\lambda )$ 最多可达 $\mathrm{\Delta }$ 且具有间隙 。 然后，对于每个 $n$ 顶点图 $G$，其最大度数至多为 $\mathrm{\Delta }$，从具有参数 $(\beta ,\gamma ,\lambda )$ 以$O{\left(\frac{\overline{\mathrm{\Delta }}\cdot n}{\mathrm{\Delta }}\right)}^{O(1/\delta )}$ 步骤混合。

Corollary 41 （硬约束）。

修复整数 $\mathrm{\Delta }\ge 3$，修复 $\beta =0$，并让 $0\le \gamma \le 1,\lambda \ge 0$ 最多为 $\mathrm{\Delta }$ 唯一，间隙为 。 然后，对于每个 $n$ 顶点图 $G$，其最大度数至多为 $\mathrm{\Delta }$，从具有参数 $(\beta ,\gamma ,\lambda )$-以$O{\left(\frac{n}{\mathrm{\Delta }}\right)}^{O(1/\delta )}$步骤混合。