Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the relationship between homology and graph theory? Can we form simplicial complexes from a graph $G$ and compute their homology groups? Are there any practical results in looking at the homology of simplicial complexes formed from a graph?

share|improve this question
1  
The discretized configuration space of a graph is a very interesting cell complex associated to a graph, and the homotopy-theory of it is quite rich. Similarly you can make "graph colouring complexes" associated to graphs and I believe them to be interesting but I don't know if people study this latter topic. For the former topic, look up the work of Rob Ghrist and Aaron Abrams. –  Ryan Budney Mar 22 '11 at 15:58

3 Answers 3

up vote 8 down vote accepted

There are a lot of interesting simplicial complexes one can create from a graph. Jakob Jonsson wrote a book called "Simplicial complexes of graphs," which defined a plethora of them. One of my favorite such complexes is the independence complex. The vertex set is the same as that of the graph, and there is a simplex $[v_0,\ldots,v_n]$ whenever no pair of the vertices $v_0,\ldots,v_n$ lie on an edge. It is a fascinating problem to compute the homology even for simple graphs. For example, I would love to know the homology of the independence complex for the 1-skeleton of the n-dimensional cube, but this appears to be a hard problem. Related to the independence complex is the so-called Theta complex which is "Alexander dual" to it in the combinatorial topology sense. See my paper with Oliver Thistlethwaite, where we get our feet wet analyzing the homology of the theta complex of k-skeleta of cubes.

While I'm plugging my own work, there is another notion, called graph homology, in which one constructs an algebraic chain complex whose generators are equivalence classes of decorated graphs. The boundary operator is usually defined by contracting edges of a graph one at a time. As far as I know, this was first considered by Kontsevich. Karen Vogtmann and I give a detailed exposition of various kinds of graph homology here.

share|improve this answer

See if you can find a copy of Massey - "A Basic Course in Algebraic Topology". Section VIII.3 is "Homology of Finite Graphs"

Also Hatcher has some stuff - he states that a graph is a 1-dimensional CW complex, and it is indeed possible to take the homology groups.

Here is a nice looking result from Massey (quoted verbatim)

Let $(X,X_0)$ be a finite, regular graph. Then $H_q(X)=0$ for $q>1,H_1(x)$ is a free abelian group and $\mathrm{Rank}(H_0(x))-\mathrm{Rank}(H_1(x)) = \mathrm{Euler \ Characteristic}$ (where here the Euler Characteristic is $V-E$)

share|improve this answer
2  
Also note, that you will have $H_0(X) = \text{free abelian group generated by pathcomponents}$ and $H_1(X) = \text{free abelian group generated by cycles}$ –  Alexander Thumm Mar 22 '11 at 6:47

In addition to Qwirk's answer: the result is actually pretty easy to prove.

Let $G$ be a connected graph (otherwise consider its connected components). Consider a spanning tree $T$ of $G$ and let $n$ be the number of edges not in $T$. It's an easy application of the Van Kampen theorem to show that $\pi_1(G,x_0) \cong F_n$ is the free group of rank $n$. Therefore is $H_1(G; \mathbb Z) \cong \mathbb Z^n$ ($H_1$ is the abelianization of $\pi_1$).

Now, since $T$ is a tree we must have $$E - n = V - 1 \implies E - V = n - 1 = \mbox{rk}(H_1(G)) - \mbox{rk}(H_0(G))$$ where $H_0(G) \cong \mathbb Z$ because the graph is connected.

Since $G$ is a one-dimensional CW-complexes the higher homology groups are trivial.

share|improve this answer
    
Is it possible to prove it using simplicial homology? –  Haikal Yeo Apr 30 '13 at 12:37

Your Answer

 
discard

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.