Timeline for Determinantal formulae for Tutte polynomial
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2015 at 11:48 | comment | added | joro | Remotely related question about interpolating the Tutte polynomial from the hyperbola: mathoverflow.net/questions/173259/… | |
| Jun 10, 2015 at 0:55 | comment | added | Sam Hopkins | 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. | |
| Jun 10, 2015 at 0:47 | comment | added | Fedor Petrov | @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? | |
| Jun 10, 2015 at 0:26 | comment | added | Chris Godsil | Determinants of what exactly? Since the Tutte polynomial is NP-hard to compute, we will need a large or complicated matrix. | |
| Jun 10, 2015 at 0:01 | history | asked | Fedor Petrov | CC BY-SA 3.0 |