On complex roots of the independence polynomial

The independence polynomial of a graph is the generating polynomial of all its independent sets. Formally, given a graph G, its independence polynomial ZG (λ) is given by ΣIλ|I|, where the sum is over all independent sets I of G. The independence polynomial has been an important object of study in both combinatorics and computer science. In particular, the algorithmic problem of estimating ZG(λ) for a fixed positive λ on an input graph G is a natural generalization of the problem of counting independent sets, and its study has led to some of the most striking connections between computational complexity and the theory of phase transitions. More surprisingly, the independence polynomial for negative and complex values of λ also turns out to be related to problems in statistical physics and combinatorics. In particular, the locations of the complex roots of the independence polynomial of bounded degree graphs turn out to be very closely related to the Lovász local lemma, and also to the questions in the computational complexity of counting. Consequently, the locations of such zeros have been studied in many works. In this direction, it is known from the work of Shearer [29] and of Scott and Sokal [27] - inspired by the study of the Lovász local lemma - that the independence polynomial ZG (λ) of a graph G of maximum degree at most d + 1 does not vanish provided that . Significant extensions of this result have recently been given in the case when λ is in the right half-plane (i.e., when ℜλ ≥ 0) by Peters and Regts [26] and Bencs and Csikvári [9]. In this paper, our motivation is to further extend these results to find new zero free regions not only in the right half plane, but also in the left half-plane, that is, when ℜλ ≤ 0. We give new geometric criterions 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 criterions, by establishing two new zero-free regions in the left-half plane. We also extend the results of Bencs and Csikvári [9] for the right half-plane using our framework. By a direct application of the interpolation method of Barvinok [5], combined with extensions due to Patel and Regts [25], our results also imply deterministic polynomial time approximation algorithms for the independence polynomial of bounded degree graphs in the new zero-free regions.

• View at Publisher

Free Full Text ( Final Version , 2mb )