Is there a matrix whose permanent counts 3-colorings?

Question

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.)

Answer 1

"The number of edge 3-colorings of a planar cubic graph as a permanent" by David E. Scheim gives a permanent formula for the number of edge-3-colorings of planar cubic graphs (i.e. the number of 3-coloring of graphs which are line graphs of cubic planar graphs.)

This is generalized (using some results of Ellingham and Goddyn) to the case of n-colorings of n-regular planar graphs in "Colorings and orientations of matrices and graphs" by Uwe Schauz. This paper interprets Ryser's permanent formula as a statement about colorings and gives a "matrix form" of a theorem of Alon and Tarsi.

This doesn't answer your question but I hope you find the above references interesting. On the other hand about the fact that the Laplacian matrix generalizes to the Laplace operator on graphs, I wanted to mention that, in turn, it generalizes to the Laplacian on vector bundles on graphs. I learned about this generalization in the talk that Kenyon gave this year at the JMM. This new approach generalizes Kirkhoff's theorem from spanning trees to cycle-rooted-spanning-forests.

Answer 2

I do not know too much about the topic, but Valiant also defined the VNP classes: http://delivery.acm.org/10.1145/810000/804419/p249-valiant.pdf?key1=804419&key2=2034149521&coll=GUIDE&dl=GUIDE&CFID=65423911&CFTOKEN=83322167

There is also a notion of reducibility there and PERMANENT (with many other counting problems is complete) while the number of colorings is not there, so probably there is no simple reduction but unfortunately I am really not familiar with these notions.

Answer 3

I'm afraid I can't answer your excellent question... but perhaps you'll be interested in this vaguely relevant remark. It gives a formula (originally by MacMahon) for the number of $n \times n$ Latin squares, but has a graph-theoretic interpretation that is related.

Let $G$ be the "rook's graph", that is, the simple graph with vertex set $\{(i,j):1 \leq i,j \leq n\}$ and an edge between $(i,j)$ and $(i',j')$ whenever $i=i'$ or $j=j'$. Define the $n \times n$ square matrix $X=(x_{ij})$ where $x_{ij}$ are variables. Then the number of $n$-colourings of $G$ is the coefficient of $\prod_{i=1}^n \prod_{j=1}^n x_{ij}$ in $\text{per}(X)^n$ (this is also the number of $n \times n$ Latin squares).