Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T07:44:56.744Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  12 April 2001

ALAN D. SOKAL
Affiliation:
Department of Physics, New York University, 4 Washington Place, New York, NY 10003, USA (e-mail: sokal@nyu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 PG(q) lie in the disc [mid ]q[mid ] < C(r). Furthermore, C(r) [les ] 7.963907r. This result is a corollary of a more general result on the zeros of the Potts-model partition function ZG(q, {ve}) in the complex antiferromagnetic regime [mid ]1 + ve[mid ] [les ] 1. The proof is based on a transformation of the Whitney–Tutte–Fortuin–Kasteleyn representation of ZG(q, {ve}) 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 PG(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.

Information

Type
Research Article
Copyright
2001 Cambridge University Press