In this introductory talk, I begin by showing how the chromatic and flow polynomials are special cases of the multivariate Tutte polynomial, and I sketch why it is often advantageous to "think multivariate", even when one is ultimately interested in a univariate specialization. I then explain briefly why the complex zeros of these polynomials are of interest to statistical physicists in connection with the Lee-Yang picture of phase transitions. Finally, I summarize what is known -- and above all, what is _not_ known -- about the complex zeros of these polynomials.
A general reference for this talk is:
arXiv:math/0503607 [math.CO] Alan D. Sokal The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
More details on various aspects can be found in:
arXiv:math/0301199 [math.CO] Gordon Royle, Alan D. Sokal The Brown-Colbourn conjecture on zeros of reliability polynomials is false
arXiv:math/0202034 [math.CO] Young-Bin Choe, James G. Oxley, Alan D. Sokal, David G. Wagner Homogeneous multivariate polynomials with the half-plane property
arXiv:cond-mat/0012369 [cond-mat.stat-mech] Alan D. Sokal Chromatic roots are dense in the whole complex plane
arXiv:cond-mat/9904146 [cond-mat.stat-mech] Alan D. Sokal Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
view more