MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

One can define cochain complexes of (combinatorial) graphs, where each term is a vector space of linear combinations of certain (isomorphism classes of) graphs, and where the differential $d$ is a signed sum of edge contractions. One can understand the kernel of $d$ by understanding the image (and hence the cokernel) of its adjoint $d^*$. It is easy to see that $d^*$ takes a graph to some linear combination of all possible "edge expansions" (some of which may be isomorphic graphs!). The exact values of the coefficients in this linear combination are perhaps less obvious. If one identifies the dual to the graph complex as a vector space of graphs via the pairing $\langle \Gamma_i, \Gamma_j\rangle = \delta_{ij}|\mathrm{Aut}(\Gamma_i)|$, those coefficients turn out to be all $(\pm)1$. (This allows one to deduce the STU and IHX relations in finite-type invariants via graph cohomology.)

In the case of "unitrivalent" graphs (which is all I'm interested in), I have written a somewhat complicated proof justifying these coefficients (or automorphism factors, depending on how you look at it). But if someone else has already written down this proof (or a shorter one, or a more general one), I'd be happy to know about it. Similarly, I'd be happy to get a hint as to why this is obvious, if that's the case.

share|cite|improve this question
Karen Vogtmann and I wrote a proof in a slightly different context in our paper "Morita classes in the homology of $Aut(F_n)$ vanish after one stabilization." – Jim Conant Aug 22 '13 at 14:35
Look at Prop 1 of our paper, restricted to $\delta_C$ and $d_C$. – Jim Conant Aug 22 '13 at 14:37
Jim, I would have voted your comment as the accepted answer if it had been an "answer". Since Victor gave exactly the same proof in his comment (and since my question said I was interested in a short proof in the absence of a reference), I'll vote his answer as the accepted one. In any case, at this point, the only consequences these answers have are on my own edification. – Robin Koytcheff Aug 31 '13 at 19:20
up vote 3 down vote accepted

One just needs to check that with your definition of pairing, one always gets $\langle d^*\Gamma_1,\Gamma_2\rangle=\pm\langle\Gamma_1,d\Gamma_2\rangle$. Notice that the right-hand side counts the number of homeomorphisms (counted with signs) between $\Gamma_1$ and $\Gamma_2/e$, where $e$ runs through the set of edges of $\Gamma_2$. The left-hand side counts the number of ways to expand $\Gamma_1$ in a vertex $v$ and then define a homeomorphism of the resulting graph with $\Gamma_2$. One can clearly define a bijection between these two sets, since both sets can be written as a union over the vertices $v$ of $\Gamma_1$ and the edges of $\Gamma_2$ of the sets of homeomorphisms $\Gamma_1\to\Gamma_2/e$ that send $v$ to the vertex in $\Gamma_2$ obtained from $e$.

I am sorry I can not provide any reference, but it seems pretty standard.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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