Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I cannot imagine how cohomology is related to graph theory, actually I read solid definition from wiki, and to be honest, I cannot understand it. e.g I know what is homotopy (in simple term), group of functions such that I can continuously convert each of them to another one, and I think this is useful for understanding homology, but, is there similar visualization method for cohomology? (I'm not looking for exact definition, I want to imagine it, actually this is in graph theoretic concept). for more information see introduction of this paper. I want to understand it in this paper, how is useful? how to imagine it?

P.S1: my field is not related to group theory, and as in introduction author wrote, this paper doesn't need deep group theoretic definition! and I don't want to be deep in group theory. Just looking for simple way to understand them.

P.S2: I think I can imagine what is free group (which is in introduction of paper), at least by Calay graph seems to be easy to imagine it.

P.S3: I also asked this in math.stackexchange but I think this is something between two field and may I get some mathematical answer there and some others here (from CS point of view) to understand it well.

share|improve this question
1  
"Wanna" is not an English word. –  Dave Clarke Jan 22 '13 at 11:11
    
@DaveClarke, may be its origin is from other languages, but is also english: oxforddictionaries.com/definition/english/wanna?q=wanna also see this :dictionary.reference.com/browse/wanna –  user742 Jan 22 '13 at 11:16
2  
Should this be in math.SE? –  Peter Shor Jan 22 '13 at 16:55
1  
As far as the use of "wanna" is concerned. It may be fine in informal conversational English, but is never used in written form. –  Nicholas Mancuso Jan 23 '13 at 2:27
1  
@NicholasMancuso: Utter nonsense. The word is absolutely used in informal writing, a fact which is easily verified empirically, and is perfectly acceptable and clearly understood in that context. The (inconsistent and mostly arbitrary, but expected on this site) demands of formal writing style have little to do with the English language as a whole. –  C. A. McCann Jan 25 '13 at 17:31

1 Answer 1

Apparently all algebraic topology is useful for is earning imaginary internet points. More than I expected, I guess... (Actually now that I've finished writing I expect to lose points on this...)

tl;dr: Honestly, I don't think anyone here can give you an easy way to really understand what homology and cohomology are, with just a short description. I made an attempt below, but I took a whole course on the subject and I still don't really know what they are. Particularly if you don't know, or care to know, what a group is. These things are groups, that's sort of the whole point. As they relate to graph theory, you can treat a graph as a simplicial complex of dimension 1. Thus you can consider the homology and cohomology groups of the graph and use them to understand the topology of the graph. Here are some notes by Herbert Edelsbrunner on homology and cohomology, the latter of which provides a useful example.

Before I can define cohomology I must first make sure you understand the definition of homology. For simplicity I'll describe everything using simplicial complexes, but (co)homology can be, and usually are, defined for more complex complexes (see what I did there?). Simplicial complexes are enough for graph theory, at least as far as I've seen.

It turns out that it's really difficult to try to create homeomorphisms between two topological spaces to show that they're topologically equivalent. It's even harder to try an show that no such homeomorphism exists. So the idea is to establish topological invariants, a property that must be equal for two topological spaces if they are topologically equivalent. If the invariant isn't the same for both spaces, then they can't possibly be topologically equivalent. Homology and cohomology groups are two such invariants. They attempt to put a group structure on a topological space, so that we can work with groups and homomorphisms instead of topological spaces and homeomorphisms. Computer scientists like homology groups because they are easy to compute and lead to fast algorithms. The downside is they're much more difficult to visualize.

So how do we describe a topological space in such a way that we can place a group structure on it? Well we build our topological space with a set of simplicies, called a simplicial complex. A 0-dimensional simplex is a vertex, a 1-dim simplex is an edge, 2-simplex is a triangle, 3-simplex is a tetrahedron, etc. A valid simplicial complex must obey certain rules about how it's simplices connect to one another: the intersection of two simplices must also be a simplex in the set and all subsimplces must be in the set. Notice that graphs can be thought about in this way.

It makes sense to talk about sums of simplices of the same dimension $p$, what we call $p$-chains. So a $p$-chain can be written as $\sum_{i} a_i \sigma_i$ where $\sigma_i$ is a $p$-simplex and $a_i$ is an integer. With this operation we can define the group of $p$-chains $(C_p,+)$, or just $C_p$.

We also have one more operation called the boundary operator, which takes a chain to it's boundary. So for an edge $(v,u)$ in some graph, the boundary is just the sum of its vertices $u+v$. The boundary operator of a $p$-simplex $\sigma = [u_0,\ldots, u_1]$ is defined as $\partial \sigma = \sum_{i}[u_0, \ldots, \hat{u_i}, \ldots, u_n]$ where $\hat{u_i}$ means that we remove the $u_i$ simplex and create a sum of $p-1$-simplices. To apply the boundary operator to a $p$-chain $c$, we just apply it to each of it's $p$-simplices, $\partial c = \sum_{i}a_i \partial \sigma_i$.

Now there are two very important types of chains which we use to construct homology groups, cycles and boundaries. A $p$-cycles is a $p$-chain $c$ with no boundary, meaning $\partial c = 0$. A $p$-boundary $c$ is a $p$-chain that is the boundary of some $p+1$-chain $d$, $c = \partial d$. Once again we can define groups $Z_p$ (our group $p$-cycles) and $B_p$ (our group of $p$-boundaries). The group $B_p$ is a subgroup of $Z_p$ which is a subgroup of $C_p$.

Homology groups are not a group of functions where one element can be deformed into another. Intuitively, what the homology group is trying to do is characterize the different loops. Think of a torus (donut) which has two distinct loops, colored in the image below. I can move the blue loop anywhere around the torus, but it's still the same loop because it differs only by it's boundary.

The elements of a homology group are equivalence classes, where two $p$-cycles in the simplicial complex are in the same equivalence class if and only if they differ only by a boundary chain. Meaning if you take two cycles $c,d \in Z_p$, and there exists boundaries $a,b \in B_p$ such that $c+a = d+b$, then $c$ and $d$ are in the same equivalence class. They are constructed as the quotient groups $H_p = Z_p/B_p$.

The two different loops of a torus

Now cohomology is much less geometrically intuitive and motivated by algebraic considerations.

We define cohomology groups in terms of cochains. A $p$-cochain is a homomorphism $\psi: C_p \rightarrow G$, where $G$ is the group used for the coefficients $a_i$ (usually $\mathbb{Z}$ or $\mathbb{Z_2}$). Instead of considering a group of chains, we consider the group of cochains, all homomorphisms between $C_p$ and $G$ denoted as $C^p=Hom(C_p, G)$.

Similarly we can define a boundary operator on cochains, as the dual homomorphism of $\partial$, which we denote $\delta: C^{p} \rightarrow C^{p+1}$. Notice that since the boundary operator $\partial$ took $p+1$-chains to $p$-chains, the dual homomorphism takes $p$-cochains to $p+1$-cochains. Now consider a $(p-1)$-cochain $\psi$ and $\partial c$ a $p-1$-chain. The coboundary operator $\delta$ requires that $\psi$ applied to $\partial c$ is the same as $\delta \psi$ applied to $c$.

Once we have the coboundary operator, we can define cocycle and coboundary groups, denoted $Z^{p}$ and $B^{p}$, just as we did before. Then the $p$th cohomology group is a set of equivalence classes where two cocylces are equivalent iff they differ by a coboundary. They are constructed as the quotient groups $H^{p}=Z^{p}/B^{p}$. Do you see why this is much less geometrically intuitive?

share|improve this answer
    
Thank you very much, thoughtful answer, I read it right now, but I think I should read it again tomorrow (with good look to your references). –  user742 Jan 22 '13 at 19:18

Your Answer

 
discard

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