2026-07-25T09:51:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25128 2026-02-09T08:06:32Z ddc:004 open_access

On the Roots of Independence Polynomial: Quantifying the Gap Prakash, Om Sharma, Vikram Independence Polynomial Root separation Zero-free regions The independence polynomial of a graph G is the generating polynomial corresponding to its independent sets of different sizes. More formally, if a_k(G) denotes the number of independent sets of G of size k then I(G,z) := ∑_k (-1)^k a_k(G) z^k. The study of evaluating I(G,z) has several deep connections to problems in combinatorics, complexity theory and statistical physics. Consequently, the roots of the independence polynomial have been studied in detail. In particular, many works have provided regions in the complex plane that are devoid of any roots of the polynomial. One of the first such results showed a lower bound on the absolute value of the smallest root β(G) of the polynomial. Furthermore, when G is connected, Goldwurm and Santini established that β(G) is a simple real root of I(G,z) smaller than one. An alternative proof was given by Csikvári. Both proofs do not provide a gap from β(G) to the smallest absolute value amongst all the other roots of I(G,z). In this paper, we quantify this gap. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Om Prakash and Vikram Sharma 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.48 urn:nbn:de:0030-drops-251281 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.48 eng https://creativecommons.org/licenses/by/4.0/legalcode