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

Bill Jackson; Alan D. Sokal

doi:10.1016/j.jctb.2009.03.002

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

Bill Jackson, Alan D. Sokal

Research output: Contribution to journal › Article › peer-review

Abstract

The chromatic polynomial P_G (q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (- ∞, 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.

Original language	English (US)
Pages (from-to)	869-903
Number of pages	35
Journal	Journal of Combinatorial Theory. Series B
Volume	99
Issue number	6
DOIs	https://doi.org/10.1016/j.jctb.2009.03.002
State	Published - Nov 2009

Keywords

Characteristic polynomial
Chromatic polynomial
Chromatic root
Dichromatic polynomial
Flow polynomial
Flow root
Graph
Matroid
Potts model
Tutte polynomial
Zero-free interval

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2009.03.002

Cite this

@article{5be47c4d09f24ccab463cb69e258fca8,

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

abstract = "The chromatic polynomial PG (q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (- ∞, 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 ZG (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.",

keywords = "Characteristic polynomial, Chromatic polynomial, Chromatic root, Dichromatic polynomial, Flow polynomial, Flow root, Graph, Matroid, Potts model, Tutte polynomial, Zero-free interval",

author = "Bill Jackson and Sokal, {Alan D.}",

note = "Funding Information: We wish to thank James Oxley for correspondence concerning Proposition 6.5, and Tibor Jord{\'a}n for conversations concerning Proposition 6.2 and its k-connected generalization. We also wish to thank the Isaac Newton Institute for Mathematical Sciences, University of Cambridge, for generous support during the programme on Combinatorics and Statistical Mechanics (January–June 2008), where this work was completed. This research was supported in part by U.S. National Science Foundation grants PHY-0099393 and PHY-0424082.",

year = "2009",

month = nov,

doi = "10.1016/j.jctb.2009.03.002",

language = "English (US)",

volume = "99",

pages = "869--903",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "6",

}

TY - JOUR

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

AU - Jackson, Bill

AU - Sokal, Alan D.

N1 - Funding Information: We wish to thank James Oxley for correspondence concerning Proposition 6.5, and Tibor Jordán for conversations concerning Proposition 6.2 and its k-connected generalization. We also wish to thank the Isaac Newton Institute for Mathematical Sciences, University of Cambridge, for generous support during the programme on Combinatorics and Statistical Mechanics (January–June 2008), where this work was completed. This research was supported in part by U.S. National Science Foundation grants PHY-0099393 and PHY-0424082.

PY - 2009/11

Y1 - 2009/11

N2 - The chromatic polynomial PG (q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (- ∞, 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 ZG (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.

AB - The chromatic polynomial PG (q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (- ∞, 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 ZG (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.

KW - Characteristic polynomial

KW - Chromatic polynomial

KW - Chromatic root

KW - Dichromatic polynomial

KW - Flow polynomial

KW - Flow root

KW - Graph

KW - Matroid

KW - Potts model

KW - Tutte polynomial

KW - Zero-free interval

UR - http://www.scopus.com/inward/record.url?scp=72049120149&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=72049120149&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2009.03.002

DO - 10.1016/j.jctb.2009.03.002

M3 - Article

AN - SCOPUS:72049120149

SN - 0095-8956

VL - 99

SP - 869

EP - 903

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 6

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this