7
$\begingroup$

Let $G$ be a connected undirected graph. Then the number $ST(G)$ of spanning trees in $G$ equals the following specific value of the Tutte polynomial of $G$: $ST(G)=T_G(1,1)$.

On the other hand, Kirchhoff's matrix tree theorem expresses $ST(G)$ as a principal minor of Laplacian of $G$.

The question is wether the whole Tutte polynomial or at least some other values can be expressed as determinants. If in general they can't, I wonder what is behind this phenomenon.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Determinants of what exactly? Since the Tutte polynomial is NP-hard to compute, we will need a large or complicated matrix. $\endgroup$
    – Chris Godsil
    Commented Jun 10, 2015 at 0:26
  • $\begingroup$ @ChrisGodsil I suppose that it may be related. Wiki page on Tutte polynomial lists several cases when it may be computed in polynomial time: hyperbola $(x-1)(y-1)=1$ and several isolated points, journals.cambridge.org/action/… Maybe, these are the points in which some formula appears to be determinantal? $\endgroup$
    – Fedor Petrov
    Commented Jun 10, 2015 at 0:47
  • 2
    $\begingroup$ The wikipedia page (en.wikipedia.org/wiki/Tutte_polynomial#Gaussian_elimination) seems to make the rather vague assertion that all evaluations for which the Tutte polynomial is computable in polynomial time are actually determinants or Pfaffians. $\endgroup$
    – Sam Hopkins
    Commented Jun 10, 2015 at 0:55
  • $\begingroup$ Remotely related question about interpolating the Tutte polynomial from the hyperbola: mathoverflow.net/questions/173259/… $\endgroup$
    – joro
    Commented Jun 10, 2015 at 11:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .