2022/04/11 by Ferenc Bencs, Péter Csíkvári, Bencs, Ferenc +5 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Polynomial and algebraic computation
paper · doi:10.48550/arxiv.2204.04868
openalex publication_date 2022/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial ZG(λ) of a graph G of maximum degree at most d+1 does not vanish provided that \vertλ\vert ≤ \fracdd(d+1)d+1. Significant extensions of this result have recently been given in the case \Re λ≥ 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 λ≤ 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.