论文标题
相关衰减和分区功能的零属性的缺失
Correlation Decay and the Absence of Zeros Property of Partition Functions
论文作者
论文摘要
（复杂）零属性的缺失是Barvinok \ cite {Barvinok2017Combinatorics}开发的插值方法的核心，用于设计各种图形计数和计算分区函数问题的确定性近似算法。解决相同问题的早期方法包括基于相关衰减属性的方法。值得注意的是，这两种方法有时应用或几乎重合的图形类别。在本文中，我们表明这不仅仅是巧合。我们确定，如果插值方法适用于满足自我还原性能的图表家庭，则该家族具有相关性衰减特性的形式，该型在距离$ω（\ log n）$处是渐近强空间混合（SSM），其中$ n $是图表的nodes nodes。这特别适用于正式图，例如图形是有限的晶格子集。 我们的证明是基于相关分区函数的某个图形多项式表示。该表示是插值方法本身的多项式时间算法设计的核心。我们猜想我们的结果适用于所有人，而不仅仅是可正常的图。
Absence of (complex) zeros property is at the heart of the interpolation method developed by Barvinok \cite{barvinok2017combinatorics} for designing deterministic approximation algorithms for various graph counting and computing partition functions problems. Earlier methods for solving the same problem include the one based on the correlation decay property. Remarkably, the classes of graphs for which the two methods apply sometimes coincide or nearly coincide. In this paper we show that this is more than just a coincidence. We establish that if the interpolation method is valid for a family of graphs satisfying the self-reducibility property, then this family exhibits a form of correlation decay property which is asymptotic Strong Spatial Mixing (SSM) at distances $ω(\log n)$, where $n$ is the number of nodes of the graph. This applies in particular to amenable graphs, such as graphs which are finite subsets of lattices. Our proof is based on a certain graph polynomial representation of the associated partition function. This representation is at the heart of the design of the polynomial time algorithms underlying the interpolation method itself. We conjecture that our result holds for all, and not just amenable graphs.
