• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,075 questions , 2,226 unanswered
5,348 answers , 22,757 comments
1,470 users with positive rep
818 active unimported users
More ...

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

+ 6 like - 0 dislike

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
asked Jul 26, 2012 in Theoretical Physics by john mangual (310 points) [ no revision ]
retagged Dec 6, 2014

1 Answer

+ 2 like - 0 dislike

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

This post imported from StackExchange MathOverflow at 2014-12-06 09:48 (UTC), posted by SE-user Igor Rivin
answered Jul 26, 2012 by Igor Rivin (40 points) [ no revision ]

Your answer

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):
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:
Then 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).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights