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

+ 6 like - 0 dislike
132 views

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

This post imported from StackExchange MathOverflow at 2014-12-06 09:48 (UTC), posted by SE-user john mangual
retagged Dec 6, 2014

 Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead. To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL. Please consult the FAQ for as to how to format your post. This is the answer box; if you want to write a comment instead, please use the 'add comment' button. Live preview (may slow down editor)   Preview Your name to display (optional): Email me at this address if my answer is selected or commented on: Privacy: Your email address will only be used for sending these notifications. Anti-spam verification: If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:$\varnothing\hbar$ysicsOverflowThen drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds). To avoid this verification in future, please log in or register.