matrix-tree theorem via supersymmetry (i.e. Grassman algebras)

2012-07-26T21:21:54Z

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

Answer by Igor Rivin for matrix-tree theorem via supersymmetry (i.e. Grassman algebras)

2012-07-27T00:04:10Z

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

matrix-tree theorem via supersymmetry (i.e. Grassman algebras) - MathOverflow

matrix-tree theorem via supersymmetry (i.e. Grassman algebras)

Answer by Igor Rivin for matrix-tree theorem via supersymmetry (i.e. Grassman algebras)