Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids

Abstract

The chromatic polynomial P_G(q) of a loopless graph G is known to be nonzero (with explicitly known sign) on the intervals (-\infty,0), (0,1) and (1,32/27]. Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial Z_G(q,v). The proofs are quite simple, and employ deletion-contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27.

LaTeX2e, 49 pages, includes 5 Postscript figures

References in corpus (1)

• The Brown-Colbourn conjecture on zeros of reliability polynomials is false

Cited by in corpus (7)

• Approximating the partition function of the ferromagnetic Potts model
• Inapproximability of the Tutte polynomial of a planar graph
• Is the five-flow conjecture almost false?
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• A motivic approach to phase transitions in Potts models
• Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs