Sokal, AD; (2001) Bounds on the complex zeros of (Di)Chromatic polynomials and Potts-model partition functions. COMB PROBAB COMPUT , 10 (1) 41 - 77.

Preview

PDF 9063.pdf Download (434kB)

Abstract

We show that there exist universal constants C(r) < <infinity> such that, for all loopless graphs G of maximum degree less than or equal to r, the zeros (real or complex) of the chromatic polynomial P-G(q) lie in the disc \q\ < C(r). Furthermore. C(r) <less than or equal to> 7.963907r. 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)\ less than or equal to 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-Kotecky-Preiss condition for nonvanishing of a polymer-model partition function. We also show that, for all loopless graphs G of second-largest degree less than or equal to 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.

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as CSVJSONXML

Archive Staff Only

View Item