Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 by A Abdesselam and arXiv:math-ph/0107005 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

share|improve this question
add comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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