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.

$\endgroup$
  • 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 Jun 10 '15 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 Jun 10 '15 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 Jun 10 '15 at 0:55
  • $\begingroup$ Remotely related question about interpolating the Tutte polynomial from the hyperbola: mathoverflow.net/questions/173259/… $\endgroup$ – joro Jun 10 '15 at 11:48

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.