Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean:
Kirchhoff's theorem says that if you take the Laplacian matrix of a graph, and chop off a row and a column, then the determinant of the resulting matrix is equal to the number of spanning trees of the graph. It would be nice to have some analogue of this for other points of the Tutte polynomial, but this is in general too much to ask: the determinant can be computed in polynomial time, but problems such as counting 3-colorings are #P-hard.
However, if we use the permanent instead of the determinant, we don't run into these complexity-theoretic issues, at least. So, given a graph G on n vertices, can we construct a matrix of size around nxn whose permanent is the number of 3-colorings of G?
(The secret underlying motivation here is a vague personal hope that we can extend the analogy between the Laplacian matrix and the Laplacian operator [no, the naming isn't a total coincidence] to analogies between other matrices and general elliptic operators, and then prove some sort of "index theorem," which could [even more speculatively, here] help us understand why graph isomorphism is hard, prove or construct a counterexample to the reconstruction conjecture, prove the Riemann hypothesis, and achieve world peace forever.)
No comments:
Post a Comment