matrix-tree theorem via supersymmetry (i.e. Grassman algebras) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:42:10Z http://mathoverflow.net/feeds/question/103242 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103242/matrix-tree-theorem-via-supersymmetry-i-e-grassman-algebras matrix-tree theorem via supersymmetry (i.e. Grassman algebras) John Mangual 2012-07-26T21:21:54Z 2012-08-10T00:22:00Z <p>The <a href="http://math.mit.edu/~levine/18.312/alg-comb-lecture-19.pdf" rel="nofollow">matrix-tree theorem</a> 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$:</p> <p>$$\#\{ \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.</p> <p>Apparently, Matrix-Tree <a href="http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem" rel="nofollow">can be used</a> to compute effective resistances between points in Electrical networks or show the number of distinct labelled trees of size n.</p> <p><a href="http://en.wikipedia.org/wiki/Exterior_algebra" rel="nofollow">Grassman algebra</a> (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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Berezin_integral" rel="nofollow">Berezin integration</a> or <a href="http://en.wikipedia.org/wiki/Grassmann_integral" rel="nofollow">Grassman integration</a>.</p> <p>$$\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)$.</p> <p><hr> Between the papers <a href="http://front.math.ucdavis.edu/0306.5396" rel="nofollow">arXiv:math.CO/0306396</a> by A Abdesselam and <a href="http://front.math.ucdavis.edu/0107.4705" rel="nofollow">arXiv:math-ph/0107005</a> by Brydges and Imbrie two approaches for proving this result arise:</p> <ul> <li>Grassmann integration (above)</li> <li>Forest-Root formula (below)</li> </ul> <p>The <a href="http://www.newton.ac.uk/programmes/CSM/seminars/041109301.pdf" rel="nofollow">Forest-Root formula</a> says, for any compactly supported function:</p> <p>$$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:</p> <p>$$\int_{\mathbb{C}^n} f(\tau) = f(0)$$</p> <p>(for compactly supported functions) where the integral is over some supersymmetric" measure, $\tau = z \overline{z} + \frac{dz d\overline{z}}{2\pi i}$.</p> <p>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 <a href="http://arxiv.org/abs/0709.2325" rel="nofollow">Branched Polymers</a> and <a href="http://en.wikipedia.org/wiki/Diffusion-limited_aggregation" rel="nofollow">Diffusion Limited Aggregation</a>). Personally, I wonder what the cotangent bundle picture looks like for these.</p> <hr> <p>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</p> http://mathoverflow.net/questions/103242/matrix-tree-theorem-via-supersymmetry-i-e-grassman-algebras/103249#103249 Answer by Igor Rivin for matrix-tree theorem via supersymmetry (i.e. Grassman algebras) Igor Rivin 2012-07-27T00:04:10Z 2012-07-27T00:04:10Z <p>Check out <a href="http://interacting.math.cnrs.fr/rutgers_Dec_07_slides.pdf" rel="nofollow">this talk by Alan Sokal,</a> and references therein (on the title page).</p>