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

Abstract

I show that there exist universal constants $C(r)<\infty$ such that, for all loopless graphs $G$ of maximum degree $\le r$, the zeros (real or complex) of the chromatic polynomial $P_G(q)$ lie in the disc $|q|<C(r)$. Furthermore, $C(r)\le \mathrm{7.963906...}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 $|1+v_e|\le 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. I also show that, for all loopless graphs $G$ of second-largest degree $\le r$, the zeros of $P_G(q)$ lie in the disc $|q|<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.

Comments: 47 pages (LaTeX). Revised version contains slightly simplified proofs of Propositions 4.2 and 4.5. Version 3 fixes a silly error in my proof of Proposition 4.1, and adds related discussion. To appear in Combinatorics, Probability & Computing