论文标题
在独立性多项式的复杂根上
On complex roots of the independence polynomial
论文作者
论文摘要
从Shearer（1985）（以及Scott and Sokal（2005））的工作中知道，最多最大$ d+1 $的独立性多项式$ z_g（λ）$，只要$ d+1 $就不会消失。最近，Peters and Regts（2019）和Bencs和Csikvári（Arxiv：1807.08963）给出了该结果的大量扩展。在本文中，我们的动机是进一步扩展这些结果并在$ \reλ\ leq 0 $时找到零自由区域。 首先，我们提供了新的几何标准，用于建立零零区域以及进行半rigol的数值探索。然后，我们通过在左半平面中建立两个新的无零区域来提供两个（严格）使用这些标准的示例。我们还使用我们的框架来改善Bencs和Csikvári（Arxiv：1807.08963）的结果。通过直接应用Barvinok的插值方法，结合了由于PATEL和REGT引起的扩展，这些结果还意味着新的无零区域中有界程度图的独立性多项式的确定性多项式时间近似算法。
It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial $Z_G(λ)$ of a graph $G$ of maximum degree at most $d+1$ does not vanish provided that $\vertλ\vert \leq \frac{d^d}{(d+1)^{d+1}}$. Significant extensions of this result have recently been given in the case $\Re λ\geq 0$ by Peters and Regts (2019) and Bencs and Csikvári (arxiv:1807.08963). In this paper, our motivation is to further extend these results and find zero free regions when $\Re λ\leq 0$. We begin by giving new geometric criteria for establishing zero-free regions as well as for carrying out semi-rigorous numerical explorations. We then provide two examples of the (rigorous) use of these criteria, by establishing two new zero-free regions in the left-half plane. We also improve upon the results of Bencs and Csikvári (arxiv:1807.08963) for the right half-plane using our framework. By a direct application of the interpolation method of Barvinok, combined with extensions due to Patel and Regts, these results also imply deterministic polynomial time approximation algorithms for the independence polynomial of bounded degree graphs in the new zero-free regions.
