On a conjecture of Sokal concerning roots of the independence polynomial
arXiv:1701.08049
Abstract
A conjecture of Sokal (2001) regarding the domain of non-vanishing for independence polynomials of graphs, states that given any natural number , there exists a neighborhood in of the interval on which the independence polynomial of any graph with maximum degree at most 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.
arXiv commentWe 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 (5)
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- 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
- Approximating permanents and hafnians