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

Alan D. Sokal

    Research output: Contribution to journalArticle

    Abstract

    We show that there exist universal constants C(r) < ∞ such that, for all loopless graphs G of maximum degree ≤ r, the zeros (real or complex) of the chromatic polynomial PG(q) lie in the disc |q| < C(r). Furthermore, C(r) ≤ 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 |1 + ve| ≤ 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 ≤ r, the zeros of PG(q) lie in the disc |q| < C(r) + 1. Along the way, I give a simple proof of a generalized (multivariate) Brown-Colboum conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.

    Original languageEnglish (US)
    Pages (from-to)41-77
    Number of pages37
    JournalCombinatorics Probability and Computing
    Volume10
    Issue number1
    DOIs
    StatePublished - 2001

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Statistics and Probability
    • Computational Theory and Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions'. Together they form a unique fingerprint.

  • Cite this