Counting independent sets up to the tree threshold
Counting independent sets up to the tree threshold
复制标题
DOI：
10.1145/1132516.1132538
复制
发表时间：
2006-05
期刊：
影响因子：
--
通讯作者：
Dror Weitz
中科院分区：
文献类型：
--
作者：
Dror Weitz
考虑具有活动λ的图G的加权独立集的近似计数问题，即，其中独立集I的权重为λ|我|.本文提出了一种新的分析方法，得到了一个确定性的逼近方案，该方案对任意最大度为Δ且λc=（Δ-1）Δ-1/（Δ-2）Δ的图都可以在多项式时间内运行.这改进了先前已知的λ ≤（2 <$Δ-2）的一般界。新的机制包括λ=1（均匀权重）和Δ ≤ 5的有趣情况。以前的界限要求Δ ≤ 4的一致近似计数，有证据表明，对于Δ ≥ 6的问题是困难的。注意，λc是度为Δ的正则树上吉布斯测度唯一性的临界活动，即，对于λ ≤ λc，根在独立集中的概率渐近独立于远低于它的叶子上的构型。事实上，我们的分析集中在建立上述加权分布中相关性随距离的衰减。我们证明，在任何最大度Δ相关性的图上，相关性随距离衰减的速度至少与在相同度的正则树上一样快。这解决了统计物理学中的一个公开猜想。我们的比较一般的图与树使用的算法参数产生的近似方案上述。此外，根据现有的论点，建立所有图和λc的相关性衰减给出了Glauber动力学在这个区域中快速混合。然而，从衰减的相关性的快速混合的动态的含义是只知道举行的图的次指数增长，因此，我们的结果，关于Glauber动态仅限于这一类的图。
Consider the problem of approximately counting weighted independent sets of a graph G with activity λ, i.e., where the weight of an independent set I is λ|I|. We present a novel analysis yielding a deterministic approximation scheme which runs in polynomial time for any graph of maximum degree Δ and λc=(Δ-1)Δ-1/(Δ-2)Δ. This improves on the previously known general bound of λ ≤ (2 ‾ Δ-2). The new regime includes the interesting case of λ=1 (uniform weights) and Δ ≤ 5. The previous bound required Δ ≤ 4 for uniform approximate counting and there is evidence that for Δ ≥ 6 the problem is hard. Note that λc is the critical activity for uniqueness of the Gibbs measure on the regular tree of degree Δ, i.e., for λ ≤ λc the probability that the root is in the independent set is asymptotically independent of the configuration on the leaves far below. Indeed, our analysis is focused on establishing decay of correlations with distance in the above weighted distribution. We show that on any graph of maximum degree Δ correlations decay with distance at least as fast as they do on the regular tree of the same degree. This resolves an open conjecture in statistical physics. Our comparison of a general graph with the tree uses an algorithmic argument yielding the approximation scheme mentioned above. Also, by existing arguments, establishing decay of correlations for all graphs and λc gives that the Glauber dynamics is rapidly mixing in this regime. However, the implication from decay of correlations to rapid mixing of the dynamics is only known to hold for graphs of subexponential growth, and hence, our result regarding the Glauber dynamics is limited to this class of graphs.