5 November 2013

14:30

Mark Jerrum

Abstract

<p>The Tutte polynomial of a graph $G$ is a two-variable polynomial
$T(G;x,y)$, which encodes much information about~$G$. The number of
spanning trees in~$G$, the number of acyclic orientations of~$G$, and the
partition function of the $q$-state Potts model are all specialisations of
the Tutte polynomial. Jackson and Sokal have studied the sign of the Tutte
polynomial, and identified regions in the $(x,y)$-plane where it is
``essentially determined'', in the sense that the sign is a function of
very simple characteristics of $G$, e.g., the number of vertices and
connected components of~$G$. It is natural to ask whether the sign of the
Tutte polynomial is hard to compute outside of the regions where it is
essentially determined. We show that the answer to this question is often
an emphatic ``yes'': specifically, that determining the sign is \#P-hard.
In such cases, approximating the Tutte polynomial with small relative
error is also \#P-hard, since in particular the sign must be determined.
In the other direction, we can ask whether the Tutte polynomial is easy to
approximate in regions where the sign is essentially determined. The
answer is not straightforward, but there is evidence that it often ``no''.
This is joint work with Leslie Ann Goldberg (Oxford).</p>