graph homology

The general formula for the 1st homology group of a topological space X is: $$H\_1(X)\; :=\; \backslash ker\; \backslash partial\_1\; \backslash big/\; \backslash operatorname\{im\}\; \backslash partial\_2$$ The example below explains these symbols and concepts in full detail on a graph.

Let X be a directed graph with 3 vertices {{mset|x, y, z}} and 4 edges {{mset|a: x → y, b: y → z, c: z → x, d: z → x}}. It has several cycles:

• One cycle is represented by the loop a+b+c. Here, the plus sign represents that all edges are travelled at the same direction. Since the addition operation is commutative, the + sign represents that the loops a + b + c, b + c + a, and c + a + b, all represent the same cycle.
• A second cycle is represented by the loop a + b + d.
• A third cycle is represented by the loop c − d. Here, the minus sign represents that the edge d is travelled backwards.

If we cut the plane along the loop a + b + d, and then cut at c and "glue" at d, we get a cut along the loop a + b + c. This can be represented by the following relation: (a + b + d) + (c − d) = (a + b + c). To formally define this relation, we define the following commutative groups:

• C₀ is the free abelian group generated by the set of vertices {{mset|x, y, z}}. Each element of C₀ is called a 0-dimensional chain.
• C₁ is the free abelian group generated by the set of directed edges {a,b,c,d}. Each element of C₁ is called a 1-dimensional chain. The three cycles mentioned above are 1-dimensional chains, and indeed the relation (a + b + d) + (c − d) = (a + b + c) holds in the group C₁.

Most elements of C₁ are not cycles, for example a + b, 2a + 5b − c, etc. are not cycles. To formally define a cycle, we first define boundaries. The boundary of an edge is denoted by the $\backslash partial\_1$ operator and defined as its target minus its source, so $\backslash partial\_1(a)=y-x,\; ~\; \backslash partial\_1(b)=z-y,\; ~\; \backslash partial\_1(c)=\backslash partial\_1(d)=x-z.$ So $\backslash partial\_1$ is a mapping from the group C₁ to the group C₀. Since a, b, c, d are the generators of C₁, this $\backslash partial\_1$ naturally extends to a group homomorphism from C₁ to C₀. In this homomorphism, $\backslash partial\_1(a+b+c)=\; \backslash partial\_1(a)+\backslash partial\_1(b)+\backslash partial\_1(c)\; =\; (y-x)+(z-y)+\; (x-z)\; =\; 0$. Similarly, $\backslash partial\_1$ maps any cycle in C₁ to the zero element of C₀. In other words, the set of cycles in C₁ generates the null space (the kernel) of $\backslash partial\_1$. In this case, the kernel of $\backslash partial\_1$ has two generators: one corresponds to a + b + c and the other to a + b + d (the third cycle, c − d, is a linear combination of the first two). So $\backslash ker\backslash partial\_1$ is isomorphic to Z².

In a general topological space, we would define higher-dimensional chains. In particular, C₂ would be the free abelian group on the set of 2-dimensional objects. However, in a graph there are no such objects, so C₂ is a trivial group. Therefore, the image of the second boundary operator, $\backslash partial\_2$, is trivial too. Therefore:$$H\_1(X)\; =\; \backslash ker\backslash partial\_1\; \backslash big/\; \backslash operatorname\{im\}\backslash partial\_2\; \backslash cong\; \backslash mathbb\{Z\}^2\; /\; \backslash mathbb\{Z\}^0\; =\; \backslash mathbb\{Z\}^2$$ This corresponds to the intuitive fact that the graph has two "holes". The exponent is the number of holes.

The above example can be generalized to an arbitrary connected graph G = (V, E). Let T be a spanning tree of G. Every edge in E \ T corresponds to a cycle; these are exactly the linearly independent cycles. Therefore, the first homology group H₁ of a graph is the free abelian group with {{abs|E \ T}} generators. This number equals {{abs|E}} − {{abs|V}} + 1; so: $$H\_1(X)\; \backslash cong\; \backslash mathbb\{Z\}^$$

The general formula for the 0th homology group of a topological space X is: $$H\_0(X)\; :=\; \backslash ker\; \backslash partial\_0\; \backslash big/\; \backslash operatorname\{im\}\; \backslash partial\_\{1\}$$

Returning to the graph with 3 vertices {{mset|x, y, z}} and 4 edges {{mset|a: x → y, b: y → z, c: z → x, d: z → x}}. Recall that the group C₀ is generated by the set of vertices. Since there are no (−1)-dimensional elements, the group C₋₁ is trivial, and so the entire group C₀ is a kernel of the corresponding boundary operator: $\backslash ker\; \backslash partial\_0\; =\; C\_0$ = the free abelian group generated by {{mset|x, y, z}}.

The image of $\backslash partial\_1$ contains an element for each pair of vertices that are boundaries of an edge, i.e., it is generated by the differences {{mset|y − x, z − y, x − z}}. To calculate the quotient group, it is convenient to think of all the elements of $\backslash operatorname\{im\}\; \backslash partial\_\{1\}$ as "equivalent to zero". This means that x, y and z are equivalent – they are in the same equivalence class of the quotient. In other words, $H\_0(X)$ is generated by a single element (any vertex can generate it). So it is isomorphic to Z.

The above example can be generalized to any connected graph. Starting from any vertex, it is possible to get to any other vertex by adding to it one or more expressions corresponding to edges (e.g. starting from x, one can get to z by adding y − x and z − y). Since the elements of $\backslash operatorname\{im\}\; \backslash partial\_\{1\}$ are all equivalent to zero, it means that all vertices of the graph are in a single equivalence class, and therefore $H\_0(X)$ is isomorphic to Z.

In general, the graph can have several connected components. Let C be the set of components. Then, every connected component is an equivalence class in the quotient group. Therefore: $$H\_0(X)\; \backslash cong\; \backslash mathbb\{Z\}^$$

Often, it is convenient to assume that the 0th homology of a connected graph is trivial (so that, if the graph contains a single point, then all its homologies are trivial). This leads to the definition of the reduced homology. For a graph, the reduced 0th homology is: $$\backslash tilde\{H\_0\}(X)\; \backslash cong\; \backslash mathbb\{Z\}^\{|C|-1\}.$$ This "reduction" affects only the 0th homology; the reduced homologies of higher dimensions are equal to the standard homologies.

A graph has only vertices (0-dimensional elements) and edges (1-dimensional elements). We can generalize the graph to an abstract simplicial complex by adding elements of a higher dimension. Then, the concept of graph homology is generalized by the concept of simplicial homology.

In the above example graph, we can add a two-dimensional "cell" enclosed between the edges c and d; let's call it A and assume that it is oriented clockwise. Define C₂ as the free abelian group generated by the set of two-dimensional cells, which in this case is a singleton {{mset|A}}. Each element of C₂ is called a 2-dimensional chain.

Just like the boundary operator from C₁ to C₀, which we denote by $\backslash partial\_1$, there is a boundary operator from C₂ to C₁, which we denote by $\backslash partial\_2$. In particular, the boundary of the 2-dimensional cell A are the 1-dimensional edges c and d, where c is in the "correct" orientation and d is in a "reverse" orientation; therefore: $\backslash partial\_2(A)=c-d$. The sequence of chains and boundary operators can be presented as follows: $$C\_2\; \backslash xrightarrow\{\backslash partial\_2\}\; C\_1\; \backslash xrightarrow\{\backslash partial\_1\}\; C\_0$$ The addition of the 2-dimensional cell A implies that its boundary, c − d, no longer represents a hole (it is homotopic to a single point). Therefore, the group of "holes" now has a single generator, namely a + b + c (it is homotopic to a+b+d). The first homology group is now defined as the quotient group: $$H\_1(X)\; :=\; \backslash ker\; \backslash partial\_1\; \backslash big/\; \backslash operatorname\{im\}\; \backslash partial\_2$$ Here, $\backslash ker\; \backslash partial\_1$ is the group of 1-dimensional cycles, which is isomorphic to Z², and $\backslash operatorname\{im\}\; \backslash partial\_2$ is the group of 1-dimensional cycles that are boundaries of 2-dimensional cells, which is isomorphic to Z. Hence, their quotient H₁ is isomorphic to Z. This corresponds to the fact that X now has a single hole. Previously. the image of $\backslash partial\_2$ was the trivial group, so the quotient was equal to $\backslash ker\; \backslash partial\_1$. Suppose now that we add another oriented 2-dimensional cell B between the edges c and d, such that $\backslash partial\_2(\backslash mathrm\{B\})=\backslash partial\_2(\backslash mathrm\{A\})=c-d$. Now C₂ is the free abelian group generated by {{mset|A, B}}. This does not change H₁ – it is still isomorphic to Z (X still has a single 1-dimensional hole). But now C₂ contains the two-dimensional cycle A − B, so $\backslash partial\_2$ has a non-trivial kernel. This cycle generates the second homology group, corresponding to the fact that there is a single two-dimensional hole: $$H\_2(X)\; :=\; \backslash ker\; \backslash partial\_2\; \backslash cong\; \backslash mathbb\{Z\}$$ We can proceed and add a 3-cell – a solid 3-dimensional object (called C) bounded by A and B. Define C₃ as the free abelian group generated by {{mset|C}}, and the boundary operator $\backslash partial\_3:\; C\_3\; \backslash to\; C\_2$. We can orient C such that $\backslash partial\_3(\backslash mathrm\{C\})=\backslash mathrm\{A\}\; -\; \backslash mathrm\{B\}$; note that the boundary of C is a cycle in C₂. Now the second homology group is: $$H\_2(X)\; :=\; \backslash ker\; \backslash partial\_2\; \backslash big/\; \backslash operatorname\{im\}\; \backslash partial\_3\; \backslash cong\; \{0\}$$ corresponding to the fact that there are no two-dimensional holes (C "fills the hole" between A and B).

In general, one can define chains of any dimension. If the maximum dimension of a chain is k, then we get the following sequence of groups: $$C\_k\; \backslash xrightarrow\{\backslash partial\_k\}\; C\_\{k-1\}\; \backslash cdots\; C\_1\; \backslash xrightarrow\{\backslash partial\_1\}\; C\_0$$ It can be proved that any boundary of a (k + 1)-dimensional cell is a k-dimensional cycle. In other words, for any k, $\backslash operatorname\{im\}\; \backslash partial\_\{k+1\}$(the group of boundaries of k + 1 elements) is contained in $\backslash ker\; \backslash partial\_k$ (the group of k-dimensional cycles). Therefore, the quotient $\backslash ker\backslash partial\_k\; \backslash big/\; \backslash operatorname\{im\}\; \backslash partial\_\{k+1\}$ is well-defined, and it is defined as the kth homology group: $$H\_k(X)\; :=\; \backslash ker\; \backslash partial\_k\; \backslash big/\; \backslash operatorname\{im\}\; \backslash partial\_\{k+1\}$$

{{reflist}}

Category:Homology theory

Category:Graph theory