On complex roots of the independence polynomial

DOI10.1137/1.9781611977554.CH29MaRDI QIDQ6396168zbMATH OpenFDO

Authors Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák

Publication date 11 April 2022

Full work available at URL https://doi.org/10.1137/1.9781611977554.CH29

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial $Z_G(lambda)$ of a graph $G$ of maximum degree at most $d+1$ does not vanish provided that $vertlambdavertleqfrac{d}^d(d+1{)}^{d+1}$. Significant extensions of this result have recently been given in the case $Relambdageq0$ by Peters and Regts (2019) and Bencs and Csikv'ari (arxiv:1807.08963). In this paper, our motivation is to further extend these results and find zero free regions when $Relambdaleq0$. 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'ari (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.

Cited in

(5)

• On the zeroes of hypergraph independence polynomials
• Zero-free regions for the independence polynomial on restricted graph classes
• Two-state spin systems with negative interactions
• Two-state spin systems with negative interactions
• The limit of the zero locus of the independence polynomial for bounded degree graphs

This page was built for publication: On complex roots of the independence polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396168)