There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a particular limit of the partition function of the $q$-state Potts model.

More generally we can consider the full Tutte polynomial $T(x,y)$ which is now a bivariate polynomial, and now precisely equivalent to the partition function of the $q$-state Potts model. Much work has been done on the values that this function takes and the theoretical difficulty of computing the values both for individual points and curves on the $xy$-plane.

An obvious thing that one might try in order to get a different angle on the roots of the chromatic, flow etc. polynomials is to consider the level curves of the Tutte polynomial in the $xy$-plane, particularly the curves corresponding to $T(x,y) = 0$.

If we do some computation, say for the Petersen graph, then a superficially interesting plot emerges, especially the zero curve.

enter image description here

As the Petersen graph has no $1$-colourings and $2$-colourings, then it must be the case that $T(0,0) = 0$ and $T(-1,0) = 0$ and indeed we see this. My question is therefore:

Question: Are there connections between the nature and/or location of the zero curves of the Tutte polynomial in the $xy$-plane and the structure of the graph?

This seems such an obvious thing to do that I am sure it must have been done before, so perhaps the dearth of published results means "no, you can't tell anything from these plots except the obvious", but I thought I would check here.

I also tried to find some literature on "zeros of bivariate polynomials" but I got lost in a maze of results about numerical computation of these curves.


As requested, here are the commands used to create this plot (in Sage):

x,y = var('x','y')
tp = graphs.PetersenGraph().tutte_polynomial()
xmin = -4
ymin = -4
delta = 5
tplot = contour_plot(tp,(x,xmin,xmin+delta),(y,ymin,ymin+delta),plot_points=400,colorbar="true",cmap="coolwarm")
  • 2
    $\begingroup$ I remember asking a question about these curves a while back, but there is no answer yet. mathoverflow.net/questions/103491/… $\endgroup$ – Gjergji Zaimi Oct 30 '15 at 4:24
  • $\begingroup$ @GjergjiZaimi I saw your question at the time, but $\mathbb{C}^2$ seems so much harder than $\mathbb{R}^2$, especially as it is hard to visualise, that I am hopeful that something is known in this case. $\endgroup$ – Gordon Royle Oct 30 '15 at 5:02
  • $\begingroup$ How hard is it to compute the Newton polygon of the Tutte polynomial from properties of the graph? Knowing that will give you the asymptotic behavior of the zero curve. Maybe this falls under "obvious" though. $\endgroup$ – j.c. Oct 30 '15 at 8:43
  • $\begingroup$ You might try asking Joanna Ellis-Monaghan or Iain Moffatt, who have been working on editing a comprehensive handbook on the Tutte polynomial. $\endgroup$ – Timothy Chow Oct 30 '15 at 17:32
  • 4
    $\begingroup$ The only place in the literature that I've seen where this is discussed is Christopher D. Wakelin's thesis eprints.nottingham.ac.uk/13978/1/259639.pdf In particular, chapter 4 has graphs similar to the one in this question, and some special cases are discussed. Zeros of the Tutte polynomial are extensively discussed by physicists but they seem to be interested in complex variables. $\endgroup$ – Slava Krushkal Oct 30 '15 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.