Updates
- [Jul 16:] The topic of spanning forests appears in theoretical physics: Some annotations from an article [a bit detailed because I use it to test openrev.org which some local grad students (developing the project) have shown me today]: (23): l=|E|-|V|+1 is a typical definition of the first Betti number which takes the point of view that a graph has only 0 and 1 dimensional components. This is the Euler-Poincare formula b0-b1 =v0 - v1 in the connected case where b0=1. [this definition of the first Betti number works in general, also if one looks (like me) at graphs at geometric objects which can have arbitrary dimension and which is more parallel to continuum geometry and topology]. A tree as defined as a connected subgraph graph with l=0 and spanning subtree as a tree as a subtree which contains all vertices. A spanning forest is a subgraph containing all vertices where each connected component is a tree. Again, one can say that these are subgraphs containing all vertices for which b1=0. (27) The first Symanzik polynomial is U = sum_T prod_{e in E-T} x_e, where each edge e has a variable xe attached and the sum is over all trees T. The Kirchhoff polynomial of a graph is a sum over all spanning trees K = sum_T prod_{e in T} x_e. The relation between these two polynomials is given in (34) as U= prod_{e in E} x_e K(1/x1,..1/x_n). The Laplacian in (35) is the graph Laplacian, where each edge is replaced by a variable x_e. If L(I,J) is the submatrix where I,J are removed and L(I)=L(I,I), the matrix tree theorem can be written as the polynomial identity K = det(L(i)). The number of spanning trees is then K(1,1,1...1). For k-forests there are similar formulas. The all minors matrix-tree theorem looks at the subset F(I) of spanning k-forests, where edges in I were deleted (43) (a special case of (42) tells that det(L(I,J)) = sum_F in F(I) prod_e in F x_e and allows to count the number of k forests. There is a all minors matrix theorem which is an expansion with external edges. Remarks to this: all this terminology is part of the matrix theorem. New is to put variables x_e for the edges which allows to rewrite things algebraically with polynomials in the edge variables. Already Biggs book has looked at more general minors. This paper nowhere computes the number of rooted spanning trees. For Symanzik polynomials, there is a Mathematica demonstration.
- [Jul 17:] A question in math overflow asks about the number of spanning forests. The answer given by David Speyer uses an expansion and mentions: it is highly unlikely that there is a reasonable formula which gives you an exact count because it means computing the Tutte polynomial at (1,2) which is #P complete. where the itallic is a bit condensed citation. The Tutte polynomial of a graph G=(V,E) is T(x,y) = sum_H (x-1)(b0(H)-b0) (y-1)b1(H), where A sums over all subgraphs H=(V,A) with the same vertex set. Here bi are the Betti numbers. Since only the Betti numbers appear, Tutte polynomial is natural. The polynomial appears also as the Whitney rank generating function R(x,y) = T(1-x,1-y) or the Tutte dichromatic polynomial Q(x,y) = T(1-x,1-y) x-b_0. Clearly T(1,2) counts the number of subgraphs H of G with the same vertex set. This is the number of spanning forests. My paper on rooted spanning forests on the other hand computes the number of rooted spanning forests. This is a different number. For the triangle K3 for example, we have 7 different spanning forests. But 16 different rooted spanning forests. While the first number is hard to compute for a general graph, I show that the second number can be computed in polynomial time.
- July 17: the google matrix A= d E + L where E is the matrix with 1 everywhere and d is a damping factor is the key to the page rank algorithm A handout of mine about this. Now since E/n is the projection onto the eigenspace of the eigenvalue 0 we can rewrite matrix theorems: det(A) = dn Det(L) so that for d=1/n^2, the determinant of the google matrix counts the number of spanning trees in the network.
- July 18: We noted that Chung and Zhao has a matrix forest theorem for the San Diego Laplacian which involves a double sum with weights involving the degrees of the vertices. The double sum is over the number of trees as well as the roots and does not really count the number of forests. It seems that the combinatorial Laplacian catches the combinatorics better than the normalized Laplacian.
- July 18: More literature search revealed that Chebotarev and Shamis have found the matrix theorem as stated already. Since our proof is new and based on a much stronger result in linear algebra, it allows an upgrade: a matrix tree theorem for colored trees. We know that det(L+k) is the number of rooted spanning forests, where edges can have k colors. We also can interpret det(L-k) as the number of rooted even spanning k-colored spanning forests minus the number of rooted odd spanning k-colored spanning forests. An Update was also resubmitted to the ArXiv.