Let $G$ be a finite connected graph. Let $K$ be a 2-dimensional complex such that $K^{(1)} = G$, $\tilde{H}_2(K)=0$ and $\tilde{H}_1(K)=\Bbb Z_m$. Show that $\det\partial_2^t∂_2 =m^2 ·k(G).$

Over the above statement, the $\tilde{H}$ notates the reduced simplicial homology and $k(G)$ notates the number of spanning trees of given graph G.

I can't figure out where to start to prove the square of boundary operator results to be same as $m^2\cdot k(G)$?


This follows from Remark 4.17 / Proposition 4.10 of "Cuts and flows of cell complexes" by Duval, Klivans and Martin. Their formula (as applied to your problem, by taking $\Sigma=\Upsilon=K$) states:

$$ \det(\partial^t_2\partial_2)=\sum_\Gamma |\mathbf{T}(\tilde H_{1}(K,\Gamma))|^2. $$

Here $\mathbf{T}(\cdot)$ denotes the torsion subgroup and the sum over $\Gamma$ runs over all "relatively acyclic" subcomplexes of $K$ (Definition 3.1). Since $\tilde{H}_1(K)$ is torsion, the discussion before Proposition 3.2 shows that the $\Gamma$ are in fact the spanning trees of $G$.

Furthermore, the relative homology groups $\tilde{H}_1(K,\Gamma)$ are all isomorphic to $\tilde{H}_1(K)=\mathbb{Z}_m$ because all the $\Gamma$'s are trees and hence contractible. The result is that the sum evaluates to $m^2 k(G)$ as desired.

Here follow a few general comments. The above formula is an interesting higher-dimensional variant of the Kirchhoff Matrix-Tree theorem which expresses the number of spanning trees of a graph in terms of the determinant of the "up-down" Laplacian $L^{ud}=\partial\partial^t$ (with a row and vertex removed). Contrast this with the "down-up Laplacian" $L^{du}=\partial_i^t\partial_i$ that's considered here. These two matrices are closely related (physicists might call them "supersymmetric partners") since the multisets of their nonzero eigenvalues are identical. However, it seems that $L^{ud}$ shows up more frequently in practice and hence is much more studied. I could be showing my ignorance but other than the above formula, I haven't seen much else on $L^{du}$ in the literature.

The "up-down / down-up" terminology can be found in Duval, Klivans and Martin's survey on simplicial and cellular trees which includes several higher-dimensional generalizations of Kirchhoff (all involving $L^{ud}$ though!).

  • $\begingroup$ from the lecture note of the class of algebraic topology recommended to handle with. $\endgroup$ – Beverlie Jun 2 '18 at 7:02
  • $\begingroup$ In your link there's no proposition 4.11 only 4.1 exist. $\endgroup$ – Beverlie Jun 2 '18 at 7:04
  • $\begingroup$ Sorry, Prop. 4.11 was a typo for Prop. 4.10, as cited in Remark 4.17. This is quite a nice problem: which lecture notes by which professor? $\endgroup$ – j.c. Jun 2 '18 at 10:34
  • $\begingroup$ why is it so good? I even don't reach the level to check how good it is. There's another pb set from the professor: math.stackexchange.com/questions/2804986/… $\endgroup$ – Beverlie Jun 2 '18 at 10:54
  • $\begingroup$ chat.stackexchange.com/rooms/78346/algebraic-topology will you come in here? $\endgroup$ – Beverlie Jun 2 '18 at 11:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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