Zero-free regions for the independence polynomial on restricted graph classes

2025/10/01 by Jerrum, Mark, Patel, Viresh
#05 #68 #82 #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #G.2.1 #G.2.2 #Mathematical Physics (math-ph)

paper · doi:10.48550/arxiv.2510.01466

Abstract

Generalising the Heilman-Lieb Theorem from statistical physics, Chudnovsky and Seymour [J. Combin. Theory Ser. B, 97(3):350--357] showed that the univariate independence polynomial of any claw-free graph has all of its zeros on the negative real line. In this paper, we show that for any fixed subdivded claw H and any Δ, there is an open set F ⊆ ℂ containing [0, ∞) such that the independence polynomial of any H-free graph of maximum degree Δ has all of its zeros outside of F. We also show that no such result can hold when H is any graph other than a subdivided claw or if we drop the maximum degree condition. We also establish zero-free regions for the multivariate independence polynomial of H-free graphs of bounded degree when H is a subdivided claw. The statements of these results are more subtle, but are again best possible in various senses.

Citations

• On the independent set polynomial of graphs and claw-free graphs
• The independence polynomial on recursive sequences of graphs
• Glauber dynamics for the hard-core model on bounded-degree H-free graphs
• On boundedness of zeros of the independence polynomial of tori
• A Unified Graph-Theoretic Framework for Free-Fermion Solvability
• Fast Sampling of b-Matchings and b-Edge Covers
• On complex roots of the independence polynomial
• The limit of the zero locus of the independence polynomial for bounded degree graphs
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Inapproximability of the independent set polynomial in the complex plane
• On trees with real rooted independence polynomial
• On a conjecture of Sokal concerning roots of the independence polynomial
• Spectrahedrality of hyperbolicity cones of multivariate matching polynomials
• Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial
• A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models

Related

• On complex roots of the independence polynomial
• On the independent set polynomial of graphs and claw-free graphs
• On the zeroes of hypergraph independence polynomials
• Optimal zero-free regions for the independence polynomial of bounded degree hypergraphs
• The limit of the zero locus of the independence polynomial for bounded degree graphs