This site is being phased out.

Homology groups of graphs

From Mathematics Is A Science
Revision as of 17:25, 28 November 2015 by imported>WikiSysop
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

The algebra of plumbing

We have been looking at the subsets of the sets of nodes and edges to study the topology of the graph. Next, we will pursue this analysis via a certain kind of algebra. We introduce this algebra with the following metaphor:

One can think of a graph as a plumbing system that consists of a network of pipes and joints. There is no water yet.

Pipes and joints.png

To approach the topology of this system from the algebraic point of view, let's also assume that each joint and each pipe is equipped with an on-off switch.

Suppose the plumbers are told only to “flip the switch” when necessary. Then two consecutive flips cause the switch to return to its original position. Furthermore, a sequence of such commands will result in a simple command: either “flip the switch” again or “do nothing”. Of course, these two commands are represented as $1$ and $0$ and combining these commands is captured by the binary arithmetic of ${\bf Z}_2$: $$0+0=0,\ 1+0=1,\ 0+1=1,\ 1+1=0.$$

Now, this activity is happening at every joint. The plumber – call him the joints guy – receives complaints from the tenants about a possible leak in a given joint and a request to flip its switch.

Pipes and joints switches 1.png

Then a combined request is to flip a selection of switches, such as:

  • flip switches at joints $A, B, ...$.

The joints listed may appear several times or never. Requests may be issued at any time and combined with the outstanding one. The plumber may, using binary arithmetic, reduce his workload one joint at a time. Also, he can add two or more work requests. If the joints are ordered, these requests can be recorded in a vector format, coordinate-wise. For example, $(1,0,1,0,…)$ means: flip the first and third switches, etc. Then $$(1,0,1,0,…)+(1,1,1,0,…)=(0,1,1,0,…).$$ Therefore, the algebra is that of this group: $$\left( {\bf Z}_2 \right)^n=\underbrace{{\bf Z}_2\oplus{\bf Z}_2\oplus ... \oplus {\bf Z}_2}_\text{n times},$$ where $n$ is the number of the joints in the network.

Alternatively, we name the joints: $A,B,...$, and then record the requests as: $A+C+A+...$. Of course, $A+A=0$, where $0$ is the “do nothing” request.

Also, there is another plumber – call him the pipes guy – who flips the switches of pipes by request from the tenants. A combined request is to take care of a selection of pipes, such as:

  • flip switches of pipes $a,b, ...$.
Pipes and joints switches 2.png

Again, the pipes listed may appear several times and the requests may be issued at any time and combined with the outstanding one, using binary arithmetic. The set of all requests form a group: $\left( {\bf Z}_2 \right)^m,$ where $m$ is the number of the pipes in the network.

Now, there is no overlap between the activities of the two plumbers so far, and there is no relation between any two joints, or any two pipes, or a joint and a pipe. However, what if the pipes guy doesn't show up for work? Then one may try to replace his request, such as

  • flip the switch of pipe $a$,

with a request for the joints guy. The choice of a substitution is obvious, if imperfect:

  • flip the switches at ends of pipe $a$.
Pipes and joints switches related.png

The result is a function, from pipes to joints: $$a=AB \ \mapsto \ A+B.$$ This is the key -- an algebraic way to link the network together.

Exercise. How can the pipes guy try to help the joints guy?

The tenant only knows the plumbing in his apartment and the plumbers only flip switches. However, if one has access to all plumbing requests and, especially the substitutions, he can use the algebra described above to understand the topology of the whole network. We proceed to develop this theory.

Chains of nodes and chains of edges

We will now approach topology of graphs in a fully algebraic way as the first step in our study of homology theory.

Suppose we are given a graph $G$:

  • the set of nodes $N$, and
  • the set of edges $E \subset N\times N$, without repetitions.

We have seen the importance of subsets of these sets. First, combinations of nodes form components:

Graph 0-chains.png

Second, combinations of edges form paths (and loops):

Graph 1-chains.png

In order to deal with these sets, we follow the idea from the last section and impose algebra on vertices and edges in the following very deliberate manner.

Definition. We define chains as formal sums of nodes or edges $$a_1+a_2+...+a_s$$ that follow this cancellation rule: $$x+x=0.$$

It's as if revisiting a node or an edge removes it from consideration...

A chain of edges

  • cannot include doubles (such as $AA$), and
  • cannot include edges with opposite directions (we assume $AB=BA$), but
  • can include repetitions, and
  • can include $0$.

Notation. The following notation will be used throughout the book. The set of chains of nodes, or $0$-chains, is: $$C_0=C_0(G):=\{ \Sigma_i A_i: A_i \in N\}.$$ The set of chains of edges, or $1$-chains, is: $$C_1=C_1(G):=\{ \Sigma_i A_iB_i: A_iB_i \in E\}.$$ These sets include $0$ as the chain with all coefficients equal to $0$.

Example. Consider this graph $G$:

  • $N=\{A,B,C,D\}$,
  • $E=\{AB,BC,CA,CD\}$.

Its realization is shown below:

Graph example 2.png

Then, $$\begin{array}{llllll} C_0 = & \{0,\\ & A,B,C,D,\\ &A+B,B+C,C+D,D+A,A+C,B+D,\\ &A+B+C,B+C+D,C+D+A,D+A+B,\\ &A+B+C+D\},\\ C_1 = & \{0,\\ & AB,BC,CA,CD,\\ &AB+BC,BC+CA,...\}. \end{array}$$

$\square$

We recognize these as abelian groups. Recall that an abelian group is a set $X$ with a binary operation called addition $$x,y\in X \Rightarrow x+y\in X,$$ such that

  • the addition is associative and commutative;
  • it contains the identity element $0\in X$ that satisfies: $x+0=x, \forall x \in X$; and
  • it contains the inverse element $-x$ of each $x\in X$ that satisfies $x+(-x)=0$.

Exercise. Prove this conclusion.

In fact, we can rewrite these groups via their generators: $$\begin{array}{lllll} C_0 = & <A,B,C,D >,\\ C_1 = & < AB,BC,CA,CD >. \end{array}$$ Recall that the rank of an abelian group is the minimal number of its generators. Then $$\operatorname{rank} C_0=4,\operatorname{rank} C_1=4.$$

Definition. The group of chains of nodes of the graph $G$ is given by: $$C_0(G)=< N_G >,$$ and the group of chains of edges by: $$C_1(G)=< E_G >.$$

If we fix the ordered sets of nodes $N$ and edges $E$ as the bases of these groups, the chains can be written coordinate-wise as column-vectors: $$A=\left[ \begin{array}{llllll} 1 \\ 0 \\ 0\\ 0 \end{array} \right], B=\left[ \begin{array}{lllll} 0 \\ 1 \\ 0\\ 0 \end{array} \right],..., A+B=\left[ \begin{array}{lllll} 1 \\ 1 \\ 0\\ 0 \end{array} \right],... $$ We can rewrite these chains of nodes in a more compact way using transposition: $$A=[1,0,0,0]^T,\ B=[0,1,0,0]^T,\ ...,A+B=[1,1,0,0]^T,\ ...;$$ as well as the chains of edges: $$AB=[1,0,0,0]^T,\ BC=[0,1,0,0]^T,\ ...,AB+BC=[1,1,0,0]^T,\ ...$$

The boundary operator

Now, the relation between the edges $E$ and the nodes $N$ is simple:

the two end-points of an edge are nodes of the graph.

However, since there are two nodes for each edge, we cannot capture this relation via a function $E \to N$. But it can be done for the groups of chains! This is the key step:

the boundary of an edge, $AB$, is a chain of two nodes, $A+B$.

To define a function that will give us all boundaries of all edges of the graph $G$, we set its value for each edge, $AB \in E_G$, first: $$\partial (AB) = A+B.$$ The next step is to extend it to the rest of the chains by “additivity” (or “linearity”): $$\partial (x+y) = \partial (x) + \partial (y).$$ Recall that a function that satisfies this identity “preserves the operations” of the group and such functions are called homomorphisms. The extension step is simple: $$\partial \left( \sum _i x_i \right) = \sum _i \partial (x_i),$$ where $x_i$ are the edges.

Example. Here is an example of a chain of edges (blue) and its boundary, a chain of nodes (red):

Boundary operator on graph.png

Some nodes appear twice (orange) and are cancelled, also seen in this algebra: $$\begin{array}{llll} \partial (AB +BC+CD)&=\partial (AB)+\partial (BC)+\partial (CD) \\ &= (A+B)+(B+C)+(C+D) \\ &=A+(B+B)+(C+C)+D\\ &=A+0+0+D\\ &=A+D. \end{array}$$

$\square$

As a crucial step, for any graph $G$ we have a homomorphism $$\partial = \partial _G: C_1(G) \to C_0(G),$$ called the boundary operator. We will demonstrate that this operator contains -- in the algebraic form -- all information about the topology of the graph!

Example. Let's present the boundary operator for the graph from the last section:

Graph example 2.png

We have, of course,

  • 1. $\partial (AB)=A+B,$
  • 2. $\partial (BC)=B+C,$
  • 3. $\partial (CA)=C+A,$
  • 4. $\partial (CD)=C+D.$
Graph example 2 boundaries.png

Re-write these coordinate-wise:

  • 1. $\partial ([1,0,0,0]^T)=[1,1,0,0]^T$,
  • 2. $\partial ([0,1,0,0]^T)=[0,1,1,0]^T$,
  • 3. $\partial ([0,0,1,0]^T)=[1,0,1,0]^T$,
  • 4. $\partial ([0,0,0,1]^T)=[0,0,1,1]^T$.

Therefore, the matrix of $\partial$ is, using these as columns, $$D = \left[ \begin{array}{llllll} 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{array} \right].$$ At this point, we (or the computer!) can easily find the boundary of any chain via simple matrix multiplication, as shown here: $$\partial (AB+BC) = \left[ \begin{array}{llllll} 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{lllll} 1 \\ 1 \\ 0 \\ 0 \end{array} \right]. $$ $\square$

Exercise. Compute all boundaries of all chains of edges for this graph.

Holes vs cycles

We already know that the issue is challenging because multiple cycles may go around a single hole:

Holes and cycles.png

We won't examine them all one by one but, instead, use the boundary operator to capture the relation between them.

In fact, the topology of (any realization of) the graph is hidden in the algebra, as we shall see. And this algebra is revealed by the behavior of graph's boundary operator. For example, compare

  • topology: the boundary of a loop is empty,
  • algebra: the boundary of a cycle is zero.

Example. Let's test the latter: $$\begin{array}{lllll} \partial (AB +BC+CA)&=\partial (AB)+\partial (BC)+\partial (CA) \\ &= (A+B)+(B+C)+(C+A) \\ &=A+A+B+B+C+C\\ &=0. \end{array}$$ $\square $

Exercise. State and prove this statement in general.

Definition. A $1$-chain is called a $1$-cycle if its boundary is zero. The group of $1$-cycles of graph $G$ is $$Z_1= Z_1(G):=\{x\in C_1(G): \partial _G x=0\}.$$

Of course this is simply the kernel of the boundary operator: $$Z_1(G):=\ker \partial _G.$$

Note: “C” in $C_0,C_1$ stands for “chain”, while “Z” in $Z_1$ stand for “Zyklus”, “cycle” in German.

We know that kernels are subgroups. Indeed, a quick proof shows that the kernel is closed under the operations of the group: $$\begin{array}{llllll} x,y \in \ker \partial & \Rightarrow & \partial (x)=\partial (y)=0 \\ &\Rightarrow & \partial (x+y)=\partial (x) +\partial (y)=0+0=0 \\ &\Rightarrow & x+y \in \ker \partial. \end{array}$$

This makes $Z_1$ a subgroup of $C_1$. The “size” of a group is measured by its rank (or, in the language of linear algebra, its dimension).

Example. Some simple algebra is sufficient to find the group of cycles for our example graph:

Graph example 2.png

We use the result above, $\partial (AB +BC+CA)=0$, and a direct examination of $C_1$ to conclude that $$\partial (x)=0 \Rightarrow x=AB +BC+CA \text{ or }0.$$

Graph example 2 cycle.png

Therefore, $$\begin{array}{llllll} Z_1 &=< AB +BC+CA >=\{0,AB +BC+CA\},\\ \operatorname{rank} Z_1 &=1. \end{array}$$ That's how we know that there is only one hole!

$\square$

So, our algebraic-topological conclusion is that for any graph $G$, $$\# \text{ of holes of } |G| = \operatorname{rank} \ker \partial _G.$$ In linear algebra, the number $\dim \ker \partial$ is known as the “nullity” of the linear operator.

Exercise. Compute $Z_1(G)$, where $G$ is the graph with $7$ edges realized as the figure eight.

Components vs boundaries

What about the components? The problem we are to solve is often called component labeling:

Graph component labeling.png

Let's review what we know. We defined, in parallel, two equivalence relations in two different realms and then counted their equivalence classes:

  • Topology: Two points $x,y \in X$ in set $X$ are homologous, $x \sim y$, if there is a path between them. Then the number of path-components of $X$ is the number of homology classes of points in $X$.
  • Combinatorics: Two nodes $A,B \in N_G$ in graph $G$ are homologous, $A \sim B$, if there is a path of edges between them. Then the number of edge-components of $G$ is the number of homology classes of nodes in $G$.

Now, let's try to understand what we need to change in the latter in order to make our analysis fully algebraic: we need to progress from nodes and edges to chains of nodes and edges. We approach the problem in a fashion similar to that in the last subsection:

  • Algebra: Two chains of nodes $P,Q \in C_0(G)$ in graph $G$ are homologous, $P \sim Q$, if there is a path (or paths?) of edges between them. This equivalence classes should form some group and the number of components of $G$ will be the rank of this group.

First we realize that

a path of edges from $A$ to $B$ = a chain of edges the boundary of which is $A+B$.

Indeed, consider this example.

Example. Suppose we are given a graph:

Boundaries of chains.png

Then $$\begin{array}{llllll} \partial (a+b+c+d)&=A+B &\Leftrightarrow &A \sim B,\\ \partial (u+v) &=X+Y &\Leftrightarrow &X \sim Y. \end{array}$$

But these chains of edges don't have to be just paths. Why not two paths? Why not just join these two into one chain:

Boundaries of chains 1.png

Does this make sense algebraically? Yes: $$\partial (a+b+c+d+u+v)=A+B +X+Y \Leftrightarrow A +X\sim B+Y.$$ After all, $\partial$ is additive!

A more precise way to understand the result is given by this equivalence: $$\partial (a+b+c+d+u+v)=A+B +X+Y \Leftrightarrow A +X+ B+Y \sim 0.$$

$\square$

So, our definition is very simple.

Definition. Two chains of nodes $P,Q \in C_0(G)$ in graph $G$ are homologous, $P \sim Q$, if there is a chain of edges $w \in C_1(G)$ with $\partial (w)=P+Q$.

In particular, a chain of nodes $P \in C_0(G)$ in graph $G$ is homologous to zero $0$, $P \sim 0$, if there is a chain of edges $w$ with $\partial (w)=P$. In other words,

$P \sim 0$ iff $P$ is the boundary of a $1$-chain.

Exercise. Prove that $P \sim Q \Leftrightarrow P + Q \sim 0$.

Definition. A $0$-chain is called a $0$-boundary if it is the boundary of some $1$-chain. The group of $0$-boundaries of graph $G$ is defined as: $$B_0=B_0(G):=\{P\in C_0(G):\ P=\partial_G(w) \text{ for some } w\in C_1(G) \}.$$

Of course, this definition can be restated as: $$B_0(G):=\operatorname{Im} \partial _G.$$

We know that the images of groups under homomorphisms are subgroups. Indeed, a quick proof shows that this set is closed under the operations: $$\begin{array}{llllll} x,y\in \operatorname{Im} \partial &\Rightarrow & x=\partial (X),y=\partial (Y)\\ &\Rightarrow & x+y=\partial (X)+ \partial (Y)=\partial (X+Y) \\ &\Rightarrow & x+y\in \operatorname{Im} \partial. \end{array}$$

This makes $B_0$ a subgroup of $C_0$.

Example. Let's find the group of boundaries for our example graph:

Graph example 2.png

The group is generated by the values of the boundary operator on the edges, which we have already found: $$\partial (AB)=A+B,\partial (BC)=B+C,\partial (CA)=C+A,\partial (CD)=C+D.$$ So, we compute: $$\begin{array}{llllll} B_0 &=&< A+B,B+C,C+A,C+D >\\ &=&< A+B,B+C,C+D > \\ &=& \{0,\\ &&A+B,B+C,C+A,C+D,B+D,A+D,\\ &&A+B+C+D\},\\ \operatorname{rank} B_0=3. \end{array}$$ It follows that $\operatorname{rank} C_0-\operatorname{rank} B_0 = 1$. That's how we know that there is only one component!

$\square$

Exercise. Modify the above analysis when edge $AD$ is added.

The boundary group isn't the goal of our quest however. This group represents the redundancy that needs to be removed from the group of chains!

Quotients in algebra

Let's review the quotient construction for abelian groups and vector spaces as it will re-appear many times.

We are given an abelian group $L$ and a subgroup $M$ (or a vector space $L$ and a subspace $M$). How do we “remove” $M$ from $L$? The simple answer of $L \setminus M$ won't work because it's not a group!

Instead, we “collapse” $M$ to $0$:

$x \sim 0$ if $x \in M$.
Vector subspace and eq relation 1.png

The question now is, of course, what about the rest of $L$?

For the end-result to be a group we need to make sure that the equivalence relation we are constructing respects the algebraic operations of $L$. We then extend the above equivalence $\sim$ to the whole $L$ by invoking its algebra:

$x \sim y$ if $x - y \sim 0$,

or

$x \sim y$ if $x - y \in M$.

Then the equivalence class of $v \in L$ is $$[v] := \{x:\ x - v \in M \} = \{x = v + m:\ m \in M \} = v + M.$$ We have proved the following.

Theorem. The equivalence class of $v \in L$ in $L/M$ is a coset of the group (or the affine subspace of the vector space) produced when $M$ is “shifted” by $v$: $$[v] := v + M.$$

Example. For example, suppose $M$ is the diagonal in $L={\bf R}^2$: $$M = \{(r,r): \ r \in {\bf R} \}.$$

Then each equivalence class is a line:

Vector subspace and eq relation.png

We can clearly see the partition induced by this equivalence relation.

Further we have: $$[v] := \{v + (r,r): \ r \in {\bf R} \} = v + M.$$ In other words, the elements of $L / M$ are the lines parallel to $M$. We notice, of course, that these lines appear to be in a 1-1 correspondence with the points of the other diagonal line $y=-x$.

Vector subspace and quotient.png

A visualization of free abelian groups, such as $L={\bf Z}^2$, would be similar; those lines will be dotted.

$\square$

Theorem. The quotient set $L/M$ is a group with the operation of addition:

  • $[u] + [v] = [u + v],\ u,v\in L$,

and, in the case of vector spaces, also scalar multiplication:

  • $q[u] = [qu], u\in L, q\in {\bf R}$.

The new group is denoted by $L/M$ as we've chosen to “divide” rather than “subtract”. Indeed: $${\bf R}^n / {\bf R}^m = {\bf R}^{n-m},\ n>m.$$

Then it's easy to see that the operations on $L/M$ are well defined: $$[v] + [u] := (v + M) + (u + M) = v + u + (M + M) = v + u + M =: [v + u],$$ and $$q[v] := q(v + M) = qv + qM = qv + M =: [qv].$$

Example. Finite groups, such as ${\bf Z}_p$, are harder to visualize in comparison to vector spaces. The advantage is that such a group is nothing but a list. Let's compute, from the definition, $$\left( {\bf Z}_2 \oplus {\bf Z}_2 \right) / <(1,0)> .$$ Since ${\bf Z}_2=\{0,1\}$, we have the numerator: $$L=\{(0,0), (1,0),(0,1),(1,1)\},$$ and the denominator $$M=\{0,1\}.$$ Then we compute the cosets: $$\begin{array}{lllllll} &[(0,0)]&:=(0,0)+M=(0,0)+\{(0,0),(1,0)\} \\ &&=\{(0,0)+(0,0),(0,0)+(1,0)\}&=\{(0,0),(1,0)\}&=M=:0; \\ &[(1,0)]&:=(1,0)+M=(1,0)+\{(0,0),(1,0)\} \\ &&=\{(1,0)+(0,0),(1,0)+(1,0)\}&=\{(1,0),(0,0)\}&=M=:0; \\ &[(0,1)]&:=(0,1)+M&=(0,1)+\{(0,0),(1,0)\} \\ &&=\{(0,1)+(0,0),(0,1)+(1,0)\}&=\{(0,1),(1,1)\}; \\ &[(1,1)]&:=(1,1)+M&=(1,1)+\{(0,0),(1,0)\} \\ &&=\{(1,1)+(0,0),(1,1)+(1,0)\}&=\{(1,1),(0,1)\}. \end{array}$$ So, we've found the quotient with the generator explicitly presented: $$L/M=< \{(0,1),(1,1)\} >.$$ $\square$

Exercise. Compute, from the definition, $$\left( {\bf Z}_2 \oplus {\bf Z}_2 \right) / <(1,1)> .$$

Exercise. Compute, from the definition, $${\bf Z} / <2> .$$

Theorem. For a finitely-generated abelian group $L$ and its subgroup $M$, we have $$\operatorname{rank} L / M = \operatorname{rank}L - \operatorname{rank}M,$$ and for a finitely-dimensional vector space $L$ and its subspace $M$, $$\dim L / M = \dim L - \dim M.$$

Note that the dimension behaves like the logarithm!

Example. In the above example, we can collapse the equivalence classes in a particular way so that they “form” a line. The line is $y = -x$ and it is perpendicular to $M$. Then, one may, informally, suggest an isomorphism of vector spaces: $$L \cong M \times L/M. $$

Vector subspace and quotient space.png

However, a choice of any other line through $0$, other than $M$ itself, would be just as valid an illustration of this idea.

$\square$

Example. To illustrate $L/M={\bf R}^3 / {\bf R}^2$, these are the equivalence classes, given algebraically:

Equivalence classes of subspace.png

and as sets of points:

Parallel planes.png

$\square$

Exercise. Sketch an illustration for ${\bf R}^3 / {\bf R}^1$.

Homology as a quotient group

Below we visualize what we are after:

Graph components as homology classes.png

Here, each color corresponds to an element of our group including zero (white). Meanwhile, we mark one -- with a star -- in each as a representative.

Indeed, we are after the components of the graph. They are exactly what's left once the boundaries are removed from consideration. As discussed above, we remove a subgroup $B$ from group $C$ not by deletion but by taking the quotient $H=C / B$ modulo $B$:

Quotient group.png

Here the denominator $B$ becomes the zero of the new group.

This is how the construction applies to the chains of nodes: $$x \sim y \Leftrightarrow x-y\in B_0 .$$ Since we are using the binary addition, this is equivalent to: $$x \sim y \Leftrightarrow x+y\in B_0 .$$

This quotient group is the group of components of the graph: $$C_0(G)/_{\sim} = C_0(G) / B_0(G).$$ Its elements are the equivalence classes of our equivalence relation as well as the cosets of the group of boundaries: $$[0]=B_0,\ [x]=x+B_0,\ [y]=y+B_0,...$$

Example. For our example graph, $\operatorname{rank} B_0=\operatorname{rank}C_0-1$ and, therefore, the group of components is $1$-dimensional. Once again, a single component! $\square$

Then, our algebraic-topological conclusion is $$\# \text{ of components of } G =\operatorname{rank}C_0 - \operatorname{rank}\operatorname{Im} \partial_G .$$

More commonly, the group we have constructed is called the $0$th homology group: $$H_0 = H_0(G) := C_0(G) / B_0(G).$$ Meanwhile, the cycle group $Z_1$ of a graph is also called the $1$st homology group: $$H_1 = H_1(G) := \ker \partial _G.$$

We will see later that, for an arbitrary dimension $n$ and an arbitrary space $X$, the homology group $H_n(X)$ of $X$ captures the interaction between:

  • the $n$-cycles in $X$, that come from looking at dimension $n-1$, and
  • the $n$-boundaries in $X$, that come from looking at dimension $n+1$.

It is defined as $$H_n(G) := Z_n(G) / B_n(G).$$ As we have seen, this analysis applied to graphs is much simpler than that because there are only two classes of chains. Then:

  • in dimension $n=0$, “everybody is a cycle”, $Z_0=C_0$; while
  • in dimension $n=1$, “nobody is a boundary”, $B_1=0$.

Exercise. Explain why $Z_0=C_0,\ B_1=0$.

Exercise. What conditions does a pair of abelian groups $H_0,H_1$ has to satisfy so that there is a graph $G$ with $H_i=H_i(G),\ i=0,1$?

This is the summary of homology theory for graphs:

Boundaries and cycles.png

An example of homological analysis

Let's now present the complete analysis of the topology of a graph.

Example. Consider this simple graph $G$: $$N=\{A,B,C,D\},$$ $$E=\{AB,BC\}.$$

Its realization may be this:

Graph example 3.png

The groups of chains are fully listed: $$\begin{array}{lllll} C_0 = & \{0,\\ & A,B,C,D,\\ &A+B,B+C,C+D,D+A,A+C,B+D,\\ &A+B+C,B+C+D,C+D+A,D+A+B,\\ &A+B+C+D\}, \\ \operatorname{rank}C_0=4;\\ C_1 = & \{0,\\ & AB,BC,\\ &AB+BC\}, \\ \operatorname{rank}C_1=2. \end{array}$$

Based on the ranks of these groups, the boundary operator $\partial : C_1 \to C_0$, is given by a $4\times 2$ matrix. It satisfies:

  • 1. $\partial (AB)=A+B$,
  • 2. $\partial (BC)=B+C$;

or written coordinate-wise:

  • 1. $\partial ([1,0]^T)=[1,1,0,0]^T$,
  • 2. $\partial ([0,1]^T)=[0,1,1,0]^T$.

Therefore, the matrix of $\partial$ is: $$\partial = \left[ \begin{array}{lllll} 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 0 & 0 \end{array} \right].$$

The boundaries of all the chains of edges are then computed: $$\begin{array}{lllll} \partial (AB) & = A+B &\ne 0,\\ \partial (BC) & = B+C &\ne 0,\\ \partial (AB+BC) & = A+B+B+C=A+C &\ne 0. \end{array}$$ Therefore, the group of cycles is $$\begin{array}{lllll} Z_1 & =\ker \partial = \{ x \in C_1: \partial x=0\}=\{0\},\\ \operatorname{rank}Z_1 & =0. \end{array}$$ Conclusion: There are no holes.

The group of boundaries is computed next: $$\begin{array}{lllll} B_0 & =\operatorname{Im } \partial = < A+B, B+C >=\{0,A+B,B+C,C+A\},\\ \operatorname{rank} B_0 & =2. \end{array}$$

The homology group is then: $$H_0= C_0 / B_0,$$ with the zero element $$[0]=B_0=\{0,A+B,B+C,C+A\}.$$ Therefore, the rest of the cosets are computed by adding element by element: $$\begin{array}{lllll} \left[ A \right] &= A+B_0 & = \{A,B,A+B+C,C\},\\ \left[ D \right] &= D+B_0 & = \{D,D+A+B,D+B+C,D+C+A\},\\ \left[ A \right] + \left[ D \right] = \left[ A + D \right] & = A+D+B_0 & = \{A+D,D+B,A+D+B+C,D+C\}. \end{array}$$ And that is also the list of elements of the homology group: $$\begin{array}{lllll} H_0 & = < [A],[D] > = \{[0],[A],[D],[A]+[D]\}, \\ \operatorname{rank}H_0 & =2. \end{array}$$ We can also see this result by: $$\operatorname{rank}H_0 = \operatorname{rank}(C_0 / B_0)=\operatorname{rank}C_0 - \operatorname{rank}B_0 =4-2=2.$$

Conclusion: The number of components is $2$.

$\square$

Exercise. Modify the above analysis for the case when (a) a new node is added with no new edges, and (b) a new edge is added with no new nodes.

Exercise. Provide a similar analysis for the graph: $$N=\{1,2,3,4\},$$ $$E=\{23,34,42\}.$$

Exercise. In a similar fashion compute the homology groups of the graph of $n$ edges arranged in (a) a string, (b) a circle, (c) a star.

Exercise. In a similar fashion compute the homology groups of the graph of edges arranged in an $n\times m$ grid.

Exercise. Compute the homology groups of an arbitrary tree.