UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Bounds on the complex zeros of (Di)Chromatic polynomials and Potts-model partition functions

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

[thumbnail of 9063.pdf]
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.

Type: Article
Title: Bounds on the complex zeros of (Di)Chromatic polynomials and Potts-model partition functions
Open access status: An open access version is available from UCL Discovery
Keywords: GROUND-STATE ENTROPY, RANDOM-CLUSTER MEASURES, PIROGOV-SINAI THEORY, EVERY PLANAR MAP, CHROMATIC POLYNOMIALS, STRIP GRAPHS, ASYMPTOTIC LIMITS, BRANCHED POLYMER, SURFACE TENSIONS, SPIN SYSTEMS
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/9063
Downloads since deposit
207Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item