在本文中，我们展示了一种构建确定性多项式时间近似算法的新方法，用于计算有界度图上的一大类图多项式的复值评估。特别是，我们的方法适用于 Tutte 多项式和独立多项式，以及复值自旋和边缘着色模型的配分函数。 更具体地说，我们定义一大类图多项式 $\mathcal C$ 并表明，如果 $p\in \cal C$ 并且在复平面中存在一个以零为中心的圆盘 $D$，使得 $p(G)对于所有有界度图 $G$，$ 不会在 $D$ 上消失，那么对于 $D$ 内部的每个 $z$，存在确定性多项式时间近似算法，用于评估 $z 处的 $p(G)$ $ ...
在本文中，我们考虑与图相关的某些众所周知的多项式，包括独立多项式和色多项式。这些多项式对图中的某些对象进行计数：在独立多项式的情况下为独立集，在色多项式的情况下为适当的着色。它们也被解释为统计物理学中的配分函数 ...
\emph{Sampling} 构成了各个领域的重要工具：从机器学习和组合优化到计算物理和生物学。采样算法的核心类是 \emph{马尔可夫链蒙特卡罗} 方法，该方法基于以所需采样分布作为其平稳分布的马尔可夫链的构造。许多传统的马尔可夫链，例如 \emph{Glauber 动力学}，不能随着维度的增加而很好地扩展 ...
通过实现 Sapozhenko 的图容器方法的算法版本，我们给出了用于近似二分图中独立集数量的新算法。我们的第一个算法适用于满足弱扩展条件的 $d$-正则二分图：当 $d$ 为常数，并且该图是二分 $\Omega( \log^2 d/d)$-expander 时，我们得到独立集数量的 FPTAS。以前，$d>5$ 的这种结果仅适用于满足随机二部图更强的扩展条件的图 ...
我们考虑设计算法来精确计算图 G 的独立集数量的问题。我们证明，当 G 被限制为强有序图类（弦二分图的超类）时，该问题存在一个多项式时间算法。我们还表明，对于有界团宽度的图来说，存在这样的算法 ...
对来自马尔可夫等价类的有向无环图 (DAG) 进行计数和均匀采样是图形因果分析中的基本任务。在本文中，我们证明这些任务可以在多项式时间内执行，解决了该领域长期存在的开放问题。我们的算法有效且易于实施 ...
对于一般反铁磁二自旋系统，包括硬核模型和反铁磁伊辛模型，当无限正则树处于唯一性时，最大度$\Delta$图上的配分函数存在$\mathsf{FPTAS}$区域作者：Li 等人 (2013)。此外，在树非唯一性区域中，Sly（2010）表明，除非$\mathsf{NP}=\mathsf{RP}$，否则不存在$\mathsf{FPRAS}$来估计配分函数 ...
在这篇简短的调查文章中，我们提出了一种基本但非常强大的方法来枚举图中的独立集合。三十多年前，克莱特曼和温斯顿首次采用了这种方法，随后被许多研究人员在不同的情况下多次使用。我们对该方法的介绍通过其在“现实生活”组合问题中的几种应用进行了说明 ...
我们给出了在一般图上具有强空间混合的二态反铁磁自旋系统的完整表征。我们证明，当且仅当系统在度数高达 $\Delta$ 的无限正则树上具有唯一的吉布斯测度时，二态反铁磁自旋系统在所有最大度数最多 $\Delta$ 的图上具有强空间混合。 Delta$，其中 $\Delta$ 可以是有界的，也可以是无界的。因此，当在度数高达 $\Delta 的无限正则树上满足唯一性条件时，最大度数最多为 $\Delta$ 的图上存在二态反铁磁自旋系统的配分函数 FPTAS $ ...
图论为统计物理学、网络分析和理论计算机科学等许多科学领域提供了基本概念。在这里，我们对图论进行教学介绍，分为三个部分。首先，我们介绍一些基本符号和图论问题，例如 ...