Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions

Source abstract

We show that there exist universal constants C ( r ) < ∞ such that, for all loopless graphs G of maximum degree [les ] r , the zeros (real or complex) of the chromatic polynomial P G ( q ) lie in the disc [mid ] q [mid ] < C ( r ). Furthermore, C ( r ) [les ] 7.963907 r . This result is a corollary of a more general result on the zeros of the Potts-model partition function Z G ( q , { v e }) in the complex antiferromagnetic regime [mid ]1 + v e [mid ] [les ] 1. The proof is based on a transformation of the Whitney–Tutte–Fortuin–Kasteleyn representation of Z G ( q , { v e }) to a polymer gas, followed by verification of the Dobrushin–Kotecký–Preiss condition for nonvanishing of a polymer-model partition function. We also show that, for all loopless graphs G of second-largest degree [les ] r , the zeros of P G ( q ) lie in the disc [mid ] q [mid ] < C ( r ) + 1. Along the way, I give a simple proof of a generalized (multivariate) Brown–Colbourn conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.