The matrix-tree theorem states the number of spanning trees of a graph $G$ is equal to a modified determinant of the adjacency matrix or "graph Laplacian", $\Delta_G$:

$$\#\{ \text{spanning trees of }G \} = \lambda_1 \lambda_2 \dots \lambda_n = \lim_{\epsilon \to 0}\frac{ \det(\Delta_G - \epsilon I)}{\epsilon}.$$ Here $\lambda_1, \dots, \lambda_n$ are the eigenvalues.

Apparently, Matrix-Tree can be used to compute effective resistances between points in Electrical networks or show the number of distinct labelled trees of size n.

Grassman algebra (or supersymmetry) seems to be a great bookkeeping device which does a lot of the linear algebra for you. Maybe the proof of that result can be simplified here.

"Fermions" and 1-forms are similar objects. We can say $\psi_1\psi_2= - \psi_2 \psi_1$ or $ v \wedge w = - w \wedge v $. For fermions there's something called Berezin integration or Grassman integration.

$$ \int (a \psi + b ) d\psi= a \hspace{0.333in}\text{and}\hspace{0.333in} \int e^{\phi^T A \psi}\; d\phi d\psi = \det A$$ I am not sure what the analog is for 1-forms in the cotangent bundle of a manifold $T^1(\mathbb{R}^n)$.

Between the papers [arXiv:math.CO/0306396][6] by A Abdesselam and [arXiv:math-ph/0107005][7] by Brydges and Imbrie two approaches for proving this result arise:
  • Grassmann integration (above)
  • Forest-Root formula (below)

The Forest-Root formula says, for any compactly supported function:

$$ f(\mathbf{0}) = \sum_{(F,R)} \int_{\mathbb{C}^N} f^{(F,R)} (\mathbf{t}) \left(-\frac{d^2 z}{\pi} \right)^N $$ Here the variables $t_i = |z_i|^2$ and $t_{ij} = |z_i - z_j|^2$ and sum is over all possible roots and forests. Apparently it can be put even more concisely as:

$$\int_{\mathbb{C}^n} f(\tau) = f(0) $$

(for compactly supported functions) where the integral is over some ``supersymmetric" measure, $\tau = z \overline{z} + \frac{dz d\overline{z}}{2\pi i}$.

It also seems these kinds of "free-fermion" calculations lead to many generalizations of matrix-tree that I won't get into (including relations to Branched Polymers and Diffusion Limited Aggregation). Personally, I wonder what the cotangent bundle picture looks like for these.

The proofs in the two above papers are left as exercises, which more general results proven. Mainly, I just would like to see the proofs the no-frills Matrix-Tree theorem from either of these two starting points


1 Answer 1


Check out this talk by Alan Sokal, and references therein (on the title page).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.