Graphs, trees and simplicial complexes

2016-11-04 ( 2020-11-12)

Graphs and simplicial complexes

A one-dimensional simplicial complex is a graph. That is, \(K=(X_ K,\Phi_ K)\) where \(V(K) = X_ K\) is the set of vertices and \(\Phi_ K\) is the set of simplexes, with \(\Phi_ K = \Phi^1_ K \cup \Phi^0_ K\), where \(E(K) = \Phi^1_ K\) are the 1-dimensional simplexes (termed edges of \(K\)) and \(\Phi^0_ K = \{ \{P\} : P \in X_ K \}\) are the \(0\)-dimensional simplexes (sometimes termed again vertices of \(K\)).

A subgraph \(X \subset K\) is a graph with as vertices a subset of vertices of \(K\), and as edges a subset of the edges of \(K\).

A path (walk?) in \(K\) of length \(l\) form a vertex \(P_ 0\in X_ K\) to a vertex \(P_ l \in X_ K\) is a sequence \(P_ 0, \ldots, P_ l\) of \(l+1\) vertices such such that for each \(j=0,\ldots, l-1\) \[ \{ P_ j, P_ {j+1} \} \in \Phi^1_ K. \] If the vertices \(P_ 0, \ldots, P_ {l}\) are all distinct (except possibly \(P_ 0 = P_ l\)), then the path is a simple path.

Remark: This terminology is not uniform in the literature. For many authors, paths in graph theory are what here we call simple paths. Note that if \(x,y\) are vertices and there exists a path from \(x\) to \(y\) of length \(l\), then there exists a simple path from \(x\) to \(y\) of length \(\leq l\). In fact, assume that there is a path \(x=P_ 0, \ldots, P_ l=y\). If it is not simple, then there exists indices \(i,j\) such that \(i \lt j\) and \(P_ i = P_ j\). Hence there is a path \(x=P_ 0, \ldots, P_ {i-1}, P_ i=P_ j, P_ {j+1}, \ldots , P_ k =y\) skipping all indices between \(i\) and \(j\), with length \(\lt l\). By a finite number of iterations, the path will have no multiple vertices except the endpoints \(x\) and \(y\).

Definition: \(K\) is connected if there is a path between any two of its vertices.

Let \(\partial_ 1\from C_ 1(K) \to C_ 0 (K)\) be the unique non-trivial boundary homomorphism in the simplicial chain complex of \(K\).

Definition: \(K\) is acyclic if \(\partial_ 1\from C_ 1(K) \to C_ 0(K)\) has trivial kernel \(Z_ 1(K) = \ker \partial_ 1 = 0\).

In graph theory, a cycle in \(K\) is a subgraph of \(K\) where each vertex belongs to exactly two (neighbouring) edges. If it not difficult to see that if there is such a cycle, then it represents a non-zero algebraic cycle in \(C_ 1(K)\), and hence \(Z_ 1(K) \neq 0\). We sometimes use the terms geometric cycle (the subgraph) and algebraic cycle (the element of \(Z_ 1(K)\)).

(1)

A graph \(K\) is acyclic \(Z_ 1(K) = 0\) if and only if it does not contain a geometric cycle, i.e. a subgraph where each vertex belongs to exactly two edges.

Proof: Since a geometric non-trivial cycle is an algebraic cycle, if $Z_ 1(K) = 0 $ then there cannot be grometric cycles, and the “only if” part is proven. For the “if” part: assume \(z\in Z_ 1(K)\) is such that \[ z = \sum_ {j=1}^l \alpha_ j[P_ j,P_ {j+1}], \quad \forall j, \alpha_ j \neq 0 \] Let \(S\) denote the set of all the \(l\) edges (\(1\)-simplices) appearing in the sum of \(z\). The vertices \(P_ 1,\ldots, P_ {l+1}\) need not be distinct. Let \(X\) be the subgraph with as vertices the set of vertices of the edges in \(S\), and as edges the elements of \(S\). Note that each vertex in \(X\) belongs to at least two edges: if on the contrary there exists \(j\) (or \(j+1\)) such that \([P_ j,P_ {j+1}]\) is the only edge in \(S\) containing \(P_ j\) (or \(P_ {j+1}\)), then in the sum \(\partial_ 1(z)\) the term \(P_ j\) (or \(P_ {j+1}\)) has as coefficient \(\pm \alpha_ j \neq 0\), which is not possible since \(\partial_ 1(z) = 0\).

Now, take \([P_ 1,P_ 2]\). There exists an edge \(\sigma \in S\) such that \(P_ 2 \in \sigma\) and \(\sigma \neq [P_ 1,P_ 2]\), and let (permuting indices if necessary) assume \(\sigma = [P_ 2, P_ 3]\). Now, if \(P_ 3 = P_ 1\), then \(P_ 1, P_ 2, P_ 3\) together with the three consecutive edges is a geometric cycle, and we finish. Otherwise, \(P_ 3 \not\in \{ P_ 1, P_ 2\}\) (i.e. the three vertices are distinct), and there exists (up to permuting indices if necessary) \(P_ 4\not\in \{ P_ 2, P_ 3 \}\) such that \([P_ 3, P_ 4] \in S\). Either \(P_ 4 \in \{ P_ 1\}\) or not. If yes, then there is the geometric cycle \(P_ 1, P_ 2, P_ 3, P_ 4\) (with proper edges). If not, then \(P_ 1, P_ 2, P_ 3, P_ 4\) are all distinct; furthermore there is $P_ 5 { P_ 3, P_ 4 } $ such that \([P_ 4, P_ 5]\in S\). If \(P_ 5 \in \{P_ 1, P_ 2\}\), then we obtained a cycle \(P_ 1P_ 2 P_ 3 P_ 4 P_ 5\) (or \(P_ 2 P_ 3 P_ 4 P_ 5\). If not, then \(P_ 1, \ldots, P_ 5\) are all distinct.

We proceed in this way, and either we stop with a geometric cycle, or we obtain a sequence of distinct vertices \(P_ 1, \ldots, P_ n\) such that \([P_ j, P_ {j+1}] \in S\) for each \(j\). Since \(S\) is finite, the iteration has to stop at most in \(l\) steps. (/Proof)

Trees

Definition: A tree \(T\) is a connected acyclic graph.

(2)

A connected graph \(K\) is acyclic if and only if any two vertices can be connected by a unique simple path.

Proof: First, assume that \(K\) is connected and \(x\), \(y\) are two vertices of \(K\). Since \(K\) is connected, there is a simple path from \(x\) to \(y\). If there are two distinct simple paths from \(x\) to \(y\), \[ x=P_ 0, \ldots, P_ l = y, \quad x=Q_ 0, \ldots, Q_ k = y, \] then \[ z = \sum_ {j=0}^{l-1} [P_ j,P_ {j+1} ] - \sum_ {i=0}^{k-1} [Q_ i, Q_ {i+1}] \neq 0 \] but \(\partial_ 1 z = -x + y + x - y = 0\), hence $z Z_ 1(K) $. Therefore \(K\) is not acyclic.

On the other hand, if \(K\) is not acyclic, there exists a geometric cycle in \(K\), and two vertices joined by two distinct simple paths. (/Proof)

(3)

A connected graph \(K\) contains as subgraph a tree \(T\) having as vertices the same set of vertices of \(K\) (a spanning tree). It is maximal in the family of all subgraphs of \(K\) wich are trees.

Proof: Let \(X\) be the set of all subgraphs of \(K\) which are trees, ordered by inclusion. Such a set of subgraphs is finite and partially ordered, and hence it has maximal elements.
Let us show that a tree \(T\subset K\) is maximal in \(X\) if and only if it is a spanning tree, i.e. if and only if its vertices are the same as the vertices of \(K\).

If the set of vertices of \(T\) coincides with the set of vertices of \(K\), and \(T' \subset K\) is another tree such that \(T\subset T'\), \(T \neq T'\), then there exists an edge \([P,Q] \subset T'\) such that \([P,Q] \not\subset T\). But there is a (unique) simple path from \(P\) to \(Q\), which yield a cycle in \(T'\) together with the edge \([P,Q]\): this is impossible since \(T'\) is a tree and hence acyclic.

On the other hand, if the set of vertices of \(T\) does not coincide with the set of vertices of \(K\), then there exists \(Q\) vertex of \(K\) such that \(Q \not \in T\). Take \(P \in T\), and \(P=P_ 0, \ldots, P_ l = Q\) a simple path in \(K\) (which is connected). Let \(j\) be the minimum value of the index such that \(P_ j \in K\) but \(P_ {j+1} \not\in K\). The edge \(\sigma = [P_ j, P_ {j+1}]\) is not contained in \(T\), hence the subgraph \(T' = T \cup [P_ j, P_ {j+1}]\) is not equal to \(T\).
Now, if \(X\subset T'\) is a geometric cycle, then it cannot contain \([P_ j, P_ {j+1}]\) (since the only edge of \(T'\) containing \(P_ {j+1}\) is \(\sigma\)), and therefore \(X \subset T\). But \(T\) is a tree, and hence it does not have cycles. Thus, \(T'\) is acyclic. It is easy to show that \(T'\) is connected, and hence that it is a tree, and that \(T\) is not maximal. (/Proof)

Homology of a graph

(4)

The homology groups of a connected graph \(K\) are: \[ H_ 0(K) = \ZZ, \quad H_ 1(K) = \ZZ^{h_ 1} \] where \(h_ 1 =c_ 1 - c_ 0+1\), with \(c_ 0\) is the number of vertices of \(K\), \(c_ 1\) is the number of edges of \(K\).

Proof: Let \(T\subset K\) be a spanning tree, with -say- \(l+1\) vertices. By definition, \(Z_ 1(T) = 0\). Let \(R\) be a vertex of \(T\). It is possible to define an ascending chain of trees \(\{R\} = T_ 0 \subset T_ 1 \subset \ldots \subset T_ l = T\), such that the \(j\)-th tree \(T_ j\) has \(j+1\) vertices. Let \(P_ j\) denote the vertex of $T_ j $ which is not in \(T_ {j-1}\) (if \(j=0\), \(P_ 0 =R\)). Such a vertex, for \(j>0\), belongs to a unique edge in \(T_ j\): let \(P_ j'\) be the other vertex of such a simplex. Hence \(T_ j\) has \(j+1\) vertices and \(j\) edges, and therefore \(T\) has \(c_ 0\) vertices (the same as \(K\)), and \(c_ 0-1\) edges (after \(R\), \(T\) is obtained by adding iteratively \(l\) edges). Let \(Y\) denote the set of edges of \(K\) which are not in \(T\): it has \(r= c_ 1 - (c_ 0 - 1)= c_ 1 - c_ 0 + 1\) elements. Let $C_ 1(K) ^r $ denote the projection, defined as \[ \pi(\sigma) = \begin{cases} \sigma & \text{if $\sigma \in Y$} \\ 0 & \text{otherwise} \end{cases} \] Then \(\ker \pi \cap Z_ 1 (K) = 0\): in fact, if \(z \in \ker \pi \cap Z_ 1 (K) = 0\), then as \(\pi (z) = 0\), the support of \(z\) is in \(T\). Hence \(z\in Z_ 1(T) = 0\), and therefore \(z=0\). Therefore, the restriction of \(\pi\) to \(Z_ 1(K)\) is a monomorphism \(Z_1 (K) \to \ZZ[Y]\).

It is also onto: for any edge \(\sigma =[x,y]\in Y\), its vertices \(x,y\) belong to \(T\). There is a unique simple path in \(T\) from \(x\) to \(y\), say \(x=P_ 0, \ldots P_ k = y\). Then \[ z = [y,x] + \sum_ {j=0}^{k-1} [P_ j, P_ {j+1}] \in Z_ 1(K), \text{ and } \pi(z) = [y,x] = -\sigma. \] Thus \(H_ 1(K) = Z_ 1(K) = \ZZ^{r}\).

The \(0\)-dimensional homology of any connected graph is \(\ZZ\): consider the augmentation homomorphism \(\varepsilon \from C_ 0(K) \to \ZZ\), defined as \(\varepsilon [P] = 1\) for each vertex \(P\). Fix a vertex \(R\) of \(K\) For each \(j=1, \ldots, c_ 0\), let \(P_ j\) denote the \(j\)-th vertex in \(K\), and let \(P_ i^j\) (as \(i=0,\ldots, l_ j\)) denote the simple path such that \(P_ 0^j = R\), and \(P_ {l_ j}=P_ j\) Then, for each \(j\) \[ \partial_ 1 \left( [P_ 0^j,P_ 1^j] + \ldots [P_ {l_ j-1}^j,P_ {l_ j}^j] \right) = [P_ {l_ j}^j] - [ P_ 0^j ] = [P_ j] - [R ]. \] Let \(p_ j\) denote the sum \[p_ j = [P_ 0^j,P_ 1^j] + \ldots [P_ {l_ j-1}^j,P_ {l_ j}^j].\]

Hence if \(z = \sum_ {j=1} ^{c_ 0} \alpha_ j [P_ j] \in \ker \varepsilon\), \[ z = \sum_ {j=1}^ {c_ 0} \alpha_ j ([P_ j] - [R]) = \sum_ {j=1}^ {c_ 0} \alpha_ j (\partial_ 1 p_ j) \in B_ 0(K) \] is a boundary. Therefore \(B_ 0(K) = \ker \epsilon\), and \(H_ 0(K) = \ZZ\). (/Proof)

\(\newcommand{\rk}{\operatorname{rank}}\)

Remark: Given a short exact sequence of abelian groups \(0\to A \to B \to C \to 0\), one has \(\rk B = \rk A + \rk C\). Now, consider the two exact sequences \[ 0 \to B_ j \to Z_ j \to H_ j \to 0 \implies \rk Z_ j = \rk B_ j + \rk H_ j \] \[ 0 \to Z_ {j} \to C_ j \to B_ {j-1} \to 0 \implies \rk C_ j = \rk Z_ j + \rk B_ {j-1}, \] which implies \[\begin{aligned} \sum_ {j} (-1)^j \rk C_ j & = \sum_ {j} (-1)^j ( \rk Z_ j + \rk B_ {j-1}) = \\ &= \sum_ {j} (-1)^j \left( \left( \rk B_ j + \rk H_ j \right) + \rk B_ {j-1} \right) = \\ &= \sum_ {j} (-1)^j \rk B_ j + \sum_ {j} (-1)^{j+1} \rk B_ j + \sum_ {j} (-1)^j \rk H_ j \\ &= \sum_ {j} (-1)^j \rk H_ j \end{aligned} \] which in our context is \(c_ 0 - c_ 1 = h_ 0 - h_ 1\).