The matrix tree theorem for weighted graphs

Question

I am interested in the general form of the Kirchoff Matrix Tree Theorem for weighted graphs, and in particular what interesting weightings one can choose.

Let $G = (V,E, \omega)$ be a weighted graph where $\omega: E \rightarrow K$, for a given field $K$; I assume that the graph is without loops.

For any spanning tree $T \subseteq G$ the weight of the tree is given to be, $$m(T) = \prod_{e \in T}\omega(e)$$ and the tree polynomial (or statistical sum) of the graph is given to be the sum over all spanning trees in G, $$P(G) = \sum_{T \subseteq G}m(T)$$ The combinatorial laplacian of the graph G is given by $L_G$, where: $$L_G = \begin{pmatrix} \sum_{k = 1}^n\omega(e_{1k}) & -\omega(e_{12}) & \cdots & -\omega(e_{1n}) \\\ -\omega(e_{12}) & \sum_{k = 1}^n\omega(e_{2k}) & \cdots & -\omega(e_{2n})\\\ \vdots & \vdots & \ddots & \vdots \\\ -\omega(e_{1n}) & -\omega(e_{2n}) & \cdots & \sum_{k = 1}^n\omega(e_{nk}) \end{pmatrix} $$

where $e_{ik}$ is the edge between vertices $i$ and $k$, if no edge exists then the entry is 0 (this is the same as considering the complete graph on n vertices with an extended weighting function that gives weight 0 to any edge not in G). The matrix tree theorem then says that the tree polynomial is equal to the absolute value of any cofactor of the matrix. That is,

$$P(G) = \det(L_G(s|t))$$

where $A(s|t)$ denotes the matrix obtained by deleting row $s$ and column $t$ from a matrix $A$.

By choosing different weightings one would expect to find interesting properties of a graph G. Two simple applications are to give the weighting of all 1's. Then the theorem allows us to count the number of spanning trees with ease (this yields the standard statement of the Matrix Tree Theorem for graphs). Alternatively, by giving every edge a distinct formal symbol as its label then by computing the relevant determinant, the sum obtained can be read as a list of all the spanning trees.

My question is whether there are other interesting weightings that can be used to derive other interesting properties of graphs, or for applied problems.

Answer 1

A very interesting weighting is obtained by just working with directed multigraphs (dimgraphs). 7 or 8 years ago, I applied the matrix-tree theorem applied to dimgraphs in conjunction with the BEST theorem to provide a structure theory for the equilibrium thermodynamics of hybridization for oligomeric (short) DNA strands.

Briefly, the SantaLucia model of DNA hybridization takes a finite word $w$ on four letters (A, C, G, T) and associates to it various thermodynamical characteristics (e.g., free energy $\Delta G$ of hybridization) based on the sequence. Assuming the words are cyclic (which is not fair, but also not a very bad approximation practically), one has $\Delta G (w) = \sum_k \Delta G (w_kw_{k+1})$ where the index $k$ is cyclic and the 16 parameters $\Delta G(AA), \dots, \Delta G(TT)$ are given.

Assuming for convenience that the $\Delta G(\cdot,\cdot)$ are independent over $\mathbb{Q}$, it is not hard to see that $\Delta G$ projects from the space of all words of length $N$ to the space of dimgraphs on 4 vertices (again, A, C, G, T) with $N$ edges, where (e.g.) an edge from A to G corresponds to the subsequence AG. Using matrix-tree and BEST provides a functional expression for the number of words of length $N$ with a given number of AA's, AC's, ... and TT's, and thus for the desired $\Delta G$.

Going a step further, one can use generalized Euler-Maclaurin identities for evaluating sums of functions over lattice polytopes to characterize the space of all (cyclic) words of length $N$ with $\Delta G$ lying in a narrow range. This effectively completes the structure theory and shows how one can construct DNA sequences having desired thermodynamical and combinatorial properties. Among other things, I used this to design a protocol for (as David Harlan Wood put it) "simulating simulated annealing by annealing DNA".

Answer 2

For signed graphs we have an interesting matrix-tree theorem. A signed graph is a graph with the additional structure of edge signs (weights) being either +1 or -1. We say that a cycle in a signed graph is balanced if the product of the edges in the cycle is +1. A signed graph is balanced if all of its cycles are balanced. Otherwise, we say a signed graph is unbalanced.

We say a subgraph $H$ of a connected signed graph $G$ is an essential spanning tree of $\Gamma$ if either

1) $\Gamma$ is balanced and $H$ is a spanning tree of $G$, or

2) $\Gamma$ is unbalanced, $H$ is a spanning subgraph and every component of $H$ is a unicyclic graph with the unique cycle having sign -1.

The matrix-tree theorem for signed graphs can be stated as follows:

Let $G$ be a connected signed graph with $N$ vertices and let $b_k$ be the number of essential spanning subgraphs which contain $k$ negative cycles. Then

$$ \det(L(G))=\sum_{k=0}^n 4^k b_k.$$

For some references see:

T. Zaslavsky, Signed Graphs, Discrete Appl. Math, 4 (1982), 47-74.

S. Chaiken, A combinatorial proof of the all minors matrix tree theorem. SIAM J. Algebraic Discrete Methods, 3 (1982), 319-329.

Signed graphs are used in spin glass theory and network applications.

Considering mixed graphs, which are directed graphs that have some undirected edges, we actually get the same theory. This is immediate since the matrix definitions are identical for signed graphs and mixed graphs. This seems to escape many of the people studying matrix properties of mixed graphs however. See:

R. Bapat, J. Grossman and D. Kulkarni, Generalized Matrix Tree Theorem for Mixed Graphs, Lin. and Mult. Lin. Algebra, 46 (1999), 299-312.

Answer 3

One can use the matrix-tree theorem with a suitable weight in order to compute the resultant of two polynomials in one variable. This is done in this 1908 article by Arthur Lee Dixon. There is also an older 1860 article by Borchardt in a similar vein.

Answer 4

You may replace each weight $\omega(e_{ij})$ to $\omega(e_{ij})x_j$, where $x_1,\ldots,x_n$ are free variables, also let's think that the graph may be directed (but loopless), so $\omega(e_{ij})\ne \omega(e_{ji})$ in general. Now the sum in each row of the matrix $$ L_G = \begin{pmatrix} \sum_{k = 1}^n\omega(e_{1k})x_k & -\omega(e_{12})x_2 & \cdots & -\omega(e_{1n})x_n \\\ -\omega(e_{21})x_1 & \sum_{k = 1}^n\omega(e_{2k})x_k & \cdots & -\omega(e_{2n})x_n\\\ \vdots & \vdots & \ddots & \vdots \\\ -\omega(e_{n1})x_1 & -\omega(e_{2n})x_n & \cdots & \sum_{k = 1}^n\omega(e_{nk}) x_k\end{pmatrix}$$ equals 0, but not in every column. It yields that the cofactors of all elements in the same row are equal (the quick proof why: replace corresponding row to a row $(0,\ldots,0,1,0\ldots,0,-1,0\ldots,0$ with $1$ and $-1$ at the places corresponding to two cofactors, the sum in each row is still 0, thus determinant is 0, but it equals to the difference of two cofactors). But not in each column. The cofactor of any element in $s$-th row equals to the sum $$ \det(L_G(s|t))=\sum_{T} m(T)\prod_{i=1}^n x_i^{\deg_{in}(i)},\quad\quad (\star) $$ where the sum is taken over all directed trees rooted at $s$ (that means that for any vertex $v$ there exists a unique directed path in $T$ from $v$ to $s$), and $m(T)=\prod_{e_{ij}\in T} \omega(e_{ij})$. So we get enumeration of the (rooted) trees according to degree sequence. In the undirected case, any usual (undirected) tree corresponds to a unique $s$-rooted directed tree, and $\deg_{in}(v)=\deg(v)-1+\delta_{sv}$ for any vertex $v$.

By the way, in this formulation (which is of course a priori equivalent to the formulation without $x_i$'s) there is a short inductive proof. Note that if $x_s=0$, then the sum of columns of $L_G(s|s)$ is 0, therefore in this case we have $\det(L_G(s|s))=0$. Thus if $n>1$, then any monomial in both RHS and LHS of $(\star)$ is divisible by $x_s$. Since both sides are polynomials of degree at most $n-1$, it follows that any monomial in any of them does not contain some variable $x_v$, $v\ne s$. Therefore it suffices to fix any $v\ne s$ and prove $(\star)$ when $x_v=0$. If $G_1=G\setminus v$, then we have $L_G(s|s)=L_{G_1}(s|s)\cdot \sum_{k=1}^n \omega(e_{vk})x_k$ (look at $v$-th column of $L_G$), and also $$ \sum_{T:\deg_{in}(v)=0} m(T)\prod_{i=1}^n x_i^{\deg_{in}(i)}= \left(\sum_{T_1} m(T_1)\prod_{i\ne v} x_i^{\deg_{in}(i)}\right) \sum_{k=1}^n \omega(e_{vk})x_k, $$ where $T_1$ runs over all $s$-rooted trees of $G_1$. This follows from the obvious bijection $T\rightarrow T\setminus v=:T_1$. So, $(\star)$ when $x_v=0$ follows from $(\star)$ for $G_1$, and we complete the induction step.

Answer 5

Another interesting weighting comes from stochastic matrices, and was used by Tuncel and me to find a completely new invariant for Markov shifts (Douglas Lind and Selim Tuncel, A Spanning Tree Invariant for Markov Shifts, Codes, Systems, and Graphical Models, IMA Volumes in Mathematics and its Applications 123 (2001), 487--497).

Let $P=[p_{ij}]$ be an $r \times r$ stochastic matrix, so that $p_{ij}\ge0$ and row sums are all 1. Let $G_P$ denote the directed graph with $r$ vertices and with one edge from $i$ to $j$ if and only if $p_{ij}>0$ and no other edges. Assume that $G_P$ is irreducible. The shift of finite type $X_P$ determined by $G_P$ is the space of all bi-infinite trips on $G_P$, which is compact. Also, $P$ determines a unique probability measure $\mu_P$ (called the Parry measure) that is invariant under the left shift $\sigma_P $ on $X_P$. These measure-preserving transformations are key examples in ergodic theory and have been extensively studied.

Given $P$, assign an edge in $G_P$ from $i$ to $j$ the weight $p_{ij}>0$. If $T$ is a spanning tree in $G_P$, define the weight of $T$ to be the product of the weights of its edges. Finally, define $\tau(P)$ to be the sum of the weights of all spanning trees in $G_P$.

If $Q$ is another such matrix, of possibly a different size, we say that the dynamical systems $(X_P,\sigma_P,\mu_P)$ and $(X_Q,\sigma_Q,\mu_Q)$ are block isomorphic if there is a shift commuting measure-preserving homeomorphism between them. The main result is that $\tau$ is an invariant of block isomorphism.

We initially observed this experimentally using Mathematica. The $\tau$ invariant is defined using a simple finite sum, and differs from more standard dynamical invariants like entropy that use asymptotic limiting behavior.

Answer 6

A somewhat different take on weighted trees is taken in this paper:

Jakobson, Dmitry; Rivin, Igor, Extremal metrics on graphs. I, Forum Math. 14, No. 1, 147-163 (2002). ZBL0995.05072.

In particular, the graphs where optimal weighting has all weights one are the so-called "equiarboreal" graphs - ones where there is the same number of trees through every edge.