On a conjecture of Sokal concerning roots of the independence polynomial

Abstract

A conjecture of Sokal (2001) regarding the domain of non-vanishing for independence polynomials of graphs, states that given any natural number $\Delta \ge 3$, there exists a neighborhood in $\mathbb{C}$ of the interval $[0,\frac{(\Delta -1{)}^{\Delta -1}}{(\Delta -2{)}^{\Delta }})$ on which the independence polynomial of any graph with maximum degree at most $\Delta$ does not vanish. We show here that Sokal's Conjecture holds, as well as a multivariate version, and prove optimality for the domain of non-vanishing. An important step is to translate the setting to the language of complex dynamical systems.

We have updated the file partly based on some comments from a referee. The file is now 20 pages and contains one figure. Accepted in Michigan Mathematical Journal

References in corpus (3)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• FPTAS for #BIS with Degree Bounds on One Side
• Inapproximability of the independent set polynomial in the complex plane

Cited by in corpus (4)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Zeros of Holant problems: locations and algorithms
• $PC$-polynomial of graph