### Which Paths Are Orthogonal to All Cycles?

#### Posted by John Baez

Greg Egan and I have been thinking about topological crystallography, and I bumped into a question about the homology of a graph embedded in a surface, which I feel someone should have already answered. Do you know about this?

I’ll start with some standard stuff. Suppose we have a directed graph $\Gamma$. I’ll write $e : v \to w \,$ when $e$ is an edge going from the vertex $v$ to the vertex $w$. We get a vector space of **0-chains** $C_0(\Gamma,\mathbb{R})$, which are formal linear combinations of vertices, and a vector space of **1-chains** $C_1(\Gamma,\mathbb{R})$, which are formal linear combinations of edges. We also get a **boundary operator**

$\partial : C_1(\Gamma,\mathbb{Z}) \to C_0(\Gamma,\mathbb{Z})$

sending each edge $e: v \to w$ to the difference $w - v$. A **1-cycle** is 1-chain $c$ with $\partial c = 0$. There is an inner product on 1-chains for which the edges form an orthonormal basis.

Any path in the graph gives a 1-chain. *When is this 1-chain orthogonal to all 1-cycles?*

To make this precise, and interesting, I should say a bit more.

To make this interesting, I need to rule out some obvious possibilities. If we have a graph consisting of two triangles connected by an edge, the path consisting of that one edge will be orthogonal to all 1-cycles:

To rule out this sort of situation, suppose the graph is embedded in a compact surface $S$. The complement of the graph will be a union of open sets called **faces**. Let’s assume each face is an open disk, and let’s assume its closure is a closed disk embedded in $S$. So, each edge is incident to two faces, and these two faces are *distinct*.

This rules out the graph above, embedded in a sphere in the obvious way, since the edge with the arrow on it is incident to just one face: the 8-sided face outside the picture!

**Question:** A path in such an embedded graph gives a 1-chain. If this 1-chain is orthogonal to all 1-cycles, must it vanish?

To make this precise: a **path** is a finite sequence of edges $e : v \to w$ and their formal ‘inverses’ $e^{-1}: w \to v$, like this:

$e_1^{\pm} : v_0 \to v_1,$ $e_2^{\pm} : v_1 \to v_2 ,$ $\dots$ $e_n^{\pm} : v_{n-1} \to v_n$

The corresponding 1-chain is the linear combination

$c = \pm e_1 \pm e_2 \pm \; \cdots \;\pm e_m$

**Question:** If the inner product of $c$ with every cycle vanishes, must we have $c = 0$?

I believe someone should have settled this by now, since it sounds easy, and the space of 1-chains orthogonal to all 1-cycles has been studied quite a lot! It’s called the **cut space** of the graph.

A **cut** is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a **cut-set**, the set of edges that have one endpoint in each subset of the partition. If we take the sum of all those edges, we get a 1-chain orthogonal to all cycles. It’s known that the cut space is spanned by 1-chains coming from cuts in this way. For example, in the graph I drew, the edge with the arrow on it spans the cut space.

A proof can be found here:

- Norman Biggs,
*Algebraic Graph Theory*.

However, I suspect there’s a lot more known about this subject!

By the way, we can use our surface to introduce a vector space of **2-chains**, $C_2(\Gamma, \mathbb{R})$, which are formal linear combinations of faces, and picking an orientation on each face gives us a boundary operator

$\partial : C_2(\Gamma,\mathbb{Z}) \to C_1(\Gamma,\mathbb{Z})$

which combined with the other one obeys

$\partial \partial = 0$

My assumption that “each edge is incident to two faces, and these two faces are distinct” implies that for every edge $e$ there is a face $f$ with

$\langle e, \partial f \rangle = \pm 1$

So, in particular, no single edge is orthogonal to all 1-cycles.

## Re: Which Paths Are Orthogonal to All Cycles?

I don’t know the correct graph-theoretic term, so I will call two paths

substantially distinctif the intersection of their sets of directed edges is not equal to the set for either individual path. The inner product of two substantially distinct paths will bestrictly less thanthe number of edges in either path.Suppose we can prove that for any two distinct vertices in the graphs of interest to us, there are always at least two

substantially distinctpaths between those vertices.Then we can argue as follows: if $\gamma_1$ is any path that is not a loop, and it runs from vertex $v$ to vertex $w$, then there must be a second, substantially distinct path $\gamma_2$ from $v$ to $w$. We can then form a loop $c$ by following $\gamma_1$ and then $\gamma_2^{-1}$. This loop can’t be orthogonal to $\gamma_1$, since we have:

$\langle c, \gamma_1 \rangle = \langle \gamma_1, \gamma_1 \rangle - \langle \gamma_2, \gamma_1 \rangle$

The first term on the RHS is the number of edges in $\gamma_1$, while the second term must be less than that since $\gamma_1$ and $\gamma_2$ are substantially distinct.

So, for any path $\gamma_1$ that is not a loop, we can construct a loop that is not orthogonal to that path.

Now we just have to prove the assumption … or find a counterexample.