May 5, 2016

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:

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.

Posted at May 5, 2016 11:30 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2880

Re: Which Paths Are Orthogonal to All Cycles?

I don’t know the correct graph-theoretic term, so I will call two paths substantially distinct if 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 be strictly less than the 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 distinct paths 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.

Posted by: Greg Egan on May 6, 2016 1:11 AM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Nice! Some casual readers may wonder:

“But what if the path $\gamma_1$ is a loop?”

The point is that in this case, the 1-chain it defined by this path is a cycle, and if this is orthogonal to all cycles it’s orthogonal to itself, hence it vanishes. So this case is easy.

Posted by: John Baez on May 6, 2016 1:57 AM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

So, now we’re assuming without loss of generality that our surface is connected, and choosing two vertices $v,w$ on the graph embedded in this surface, and seeking two ‘substantially distinct’ paths from $v$ to $w$.

It seems helpful to find paths that aren’t ridiculously redundant. After all, if a path from $v$ to $w$ uses all the edges of our graph, no other path can be substantially distinct from it.

Let’s say a path is irredundant if it doesn’t go through the same vertex twice. Given any path from $v$ to $w$, we can always make it irredundant as follows. Suppose it goes through the vertex $x$ twice. Then it’s of the form $\gamma \delta \epsilon$ where $\delta$ starts and ends at $x$. Then $\gamma \epsilon$ is another, strictly shorter, path from $v$ to $w$. By repeating this move we must eventually reach an irredundant path from $v$ to $w$.

(Note that if we apply this procedure to a loop that starts and ends at $v = w$, we’ll eventually reach the trivial loop, with no edges at all, that starts an ends at this vertex.)

An irredundant path can never go over the same edge twice, in either direction. That is, it can never contain an edge $e$ twice, nor can it contain can it edge $e$ and its inverse $e^{-1}$, nor can it contain $e^{-1}$ twice

Thus, by working with irredundant paths we can fix what seems like a little hole in Greg’s result. He wrote:

$\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$ [….]

That’s true when $\gamma_1$ is irredundant, but not in general. Luckily we can always make $\gamma_1$ and $\gamma_2$ irredundant before running the argument, so this shouldn’t be a serious problem!

An irredundant path can still be absurdly circuitous: for example, it can visit every vertex of our graph, or even every edge. But, it’s a step toward finding a path from $v$ to $w$ that’s efficient enough that we can find another substantially distinct path.

Posted by: John Baez on May 6, 2016 2:26 AM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Thanks for pointing out that hole in my argument! I wasn’t thinking clearly.

Here’s a slightly different approach that might cope better with arbitrary paths. Given our path $\gamma_1$, we just need another path $\gamma_2$ with the same endpoints such that:

$\langle \gamma_1, \gamma_2 \rangle \neq \langle \gamma_1, \gamma_1 \rangle$

Then we can join $\gamma_1$ and $\gamma_2^{-1}$ to make a loop that’s not orthogonal to $\gamma_1$.

Consider some edge $e_i$ of $\gamma_1$, and suppose it starts and ends on vertices $v_{i,1}$ and $v_{i,2}$. There are two obvious alternative paths from $v_{i,1}$ to $v_{i,2}$, given by the two faces incident on $e_i$: you just go around either face, in the opposite direction to $e_i$, using all the other edges of that face except $e_i$.

We want to construct the path $\gamma_2$ by taking $\gamma_1$ and substituting one of these “detours” in place of one of its edges, $e_i$. Generically, you’d expect the inner product of $\gamma_1$ and $e_i$ to differ from the inner product of $\gamma_1$ and the detour around at least one of the faces. Of course we can’t appeal to that … but my hunch is that the only paths where the inner products remain the same for every possible such substitution would have to be loops.

Does that sound plausible? Provable?

Posted by: Greg Egan on May 6, 2016 4:44 AM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Hmm, my last suggestion might not be all that helpful, since requiring the edge and the detour to have different inner products with the path is really just the same as requiring the path to have a non-zero inner product with the loop around the whole face that’s being used to construct the detour. So it’s really just saying that if a path has a non-zero inner product with the loop around some face, here’s how to construct another loop with which the path has a non-zero inner product!

Posted by: Greg Egan on May 6, 2016 6:13 AM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

On Mathoverflow, Ilya Bogdanov wrote:

If a path $p$ is not simple, then it contains a cycle $c$, and $\langle c,p\rangle=|c| \; > \; 0$. Thus we may assume that $p$ is simple, so $p$ has the form $v_0\to v_1\to\cdots\to v_n$ with $v_0,v_1,\dots,v_n$ distinct.

Let $G$ be the underlying (undirected) graph of our initial graph. Let $G'$ be the subgraph of graph $G$ obtained by removing the edges (not vertices!) of $p$. If the component of $v_n$ in $G'$ contains no other $v_i$, then the edge $(v_{n-1},v_n)$ is a bridge in $G$, so this edge contradicts the condition imposed on the faces. Thus there exists a path in $G'$ from $v_n$ to $v_i$ for some $i$. This path, augmented by $v_i\to v_{i+1}\to\cdots\to v_n$, provides a cycle having a positive product with $p$.

I’ve added links to two terms from graph theory.

A bridge is an edge of a graph whose deletion increases the number of connected components — or equivalently, it’s an edge that’s not contained in any cycle.

According to Wikipedia, a simple path is “one which contains no repeated vertices (in other words, it does not cross over itself)”. If so, this is just what I was calling an irredundant path.

Wikipedia says “a path is a trail in which all vertices (except possibly the first and last) are distinct.” They also say “a trail is a walk in which all edges are distinct.”

This is a bit confusing, since it seems to be saying a simple path is a path that’s not a loop, but I don’t think that’s what they really mean. I think different writers here were using different conventions!

So, I’ll need to be careful about this terminology. Elsewhere Wikipedia says:

A walk is an alternating sequence of vertices and edges, starting and ending at a vertex, in which each edge is adjacent in the sequence to its two endpoints. In a directed graph the ordering of the endpoints of each edge in the sequence must be consistent with the direction of the edge. Some sources call walks paths, while others reserve the term “path” for a simple path (a walk without repeated vertices or edges). Walks are also sometimes called chains. A walk is open if its starts and ends at two different vertices, and closed if it starts and ends at the same vertex. A closed walk may also be called a cycle. Alternatively, the word “cycle” may be reserved for a simple closed walk (one without repeated vertices or edges except for the repetition of the starting and final vertex). A walk without repeated edges (but with vertex repetition allowed) may be called a trail and a closed trail may be called a tour.

It sounds like a complete mess.

Posted by: John Baez on May 6, 2016 5:10 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

I like the idea of Ilya Bogdanov’s proof, but I don’t see how to make it rigorous. If a path $p$ is not simple it contains a loop $c$, but we don’t always have $\langle c, p \rangle = |c|$, and indeed we can have $\langle c, p \rangle = 0.$

There are various kinds of counterexamples: here’s one. Suppose $p = a b c b^{-1} c^{-1}$ where $b, c$ are loos that start and end at the same point but share no edges, and $a$ is path sharing no edges with $b$ or $c$. Then $p$ is not simple, and it contains a loop $c$, but $\langle p, c \rangle = 0$.

Posted by: John Baez on May 8, 2016 10:40 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

I haven’t thought deeply about the case of a triangulation, but shouldn’t the 1-chains have a Hodge decomposition similar to how 1-forms do in cohomology? If that’s the case, then the paths you are looking for are simply the co-exact chains. i.e. Chains in the image of $\partial^*: C_0 \to C_1$. You could also characterize them by saying $\partial^* \gamma = 0$ and $\partial\gamma \neq 0$, where the first condition refers to $\partial^*:C_1 \to C_2$ and states that the path is coclosed and the second rules out the paths which are both closed and coclosed (i.e. “harmonic”). The first condition should be thought of as counting the signed incidence on each face.
Posted by: Adam on May 6, 2016 6:33 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

I haven’t thought deeply about the case of a triangulation, but shouldn’t the 1-chains have a Hodge decomposition similar to how 1-forms do in cohomology?

Yes! And this works for any graph drawn on a surface whose complement consists of open disks, not just graphs coming from triangulations.

Thanks for bringing up Hodge theory. I had tried to solve my problem using Hodge theory, but I wasn’t able to use the standard manipulations involving $\partal, \partial^*$ and the inner product to settle the question I was really interested in:

Question: Suppose we have a graph $\Gamma$ embedded in a surface $S$ such that $S - \Gamma$ is a union of open disks whose closures are embedded closed disks. Any path in $\Gamma$ gives a 1-chain $c \in C^1(\Gamma,\mathbb{R})$. If this 1-chain is orthogonal to all 1-cycles, must it vanish?

The condition about ‘embedded closed disks’ can’t be omitted from this statement — that’s what makes it tricky. But Ilya Bogdanov seems to have proved a stronger version that avoids mentioning the surface $S$ altogether:

Stronger Claim: Suppose $\Gamma$ is a graph having no edge whose removal would increase the number of connected components. Any path in $\Gamma$ gives a 1-chain $c \in C^1(\Gamma,\mathbb{R})$. If this 1-chain is orthogonal to all 1-cycles, it vanishes.

Is there a nice proof of this using Hodge theory?

Posted by: John Baez on May 6, 2016 7:05 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

If this 1-chain is orthogonal to all 1-cycles, must it vanish?

Let’s say $G$ was connected for simplicity. Suppose that $G$ had an edge $e$ where, if it was removed, $G$ would have two connected components. Call them $G_0$ and $G_1$. Let’s create a zero chain $\alpha = \sum_{v \in V(G)} \alpha_v [v]$ such that $\alpha_{v} = 0$ if $v\in G_0$ and $\alpha_v = 1$ if $v\in G_1$. Then $\partial^* \alpha =e$ and, since $e$ is coexact, $e$ is orthogonal to all cycles.

Posted by: Adam on May 6, 2016 10:57 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Oops. Surrounded by small children with inversely proportional voices, I did not quite write what I should have. What I should have said was that: you should start with such a coexact/orthogonal path $\gamma$. Then if there were some path – disjoint from the edges of $\gamma$ – which connected distinct vertices of $\gamma$, then we could complete it using edges of $\gamma$ to arrive at a contradiction. (They aren’t orthogonal.)

This means that deleting any edge of $\gamma$ will separate $G$, contradicting the hypothesis.

That doesn’t really use Hodge theory, but my thoughts that used Hodge theory were getting overly complicated.

Posted by: Adam on May 6, 2016 11:53 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

I like the general idea of this argument, but I haven’t yet been able to make it rigorous. Here is where the problems creep in:

Then if there were some path – disjoint from the edges of $\gamma$ – which connected distinct vertices of $\gamma$, then we could complete it using edges of $\gamma$ to arrive at a contradiction.

There may be no path disjoint from the edges of $\gamma$. The path $\gamma$ may use all the edges in our graph, and even use them repeatedly.

(It turns out that what I defined to be a ‘path’ in this post, many graph theorists call a ‘walk’. But I will stick with my terminology for now.)

Posted by: John Baez on May 8, 2016 10:28 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Here’s a thought that’s more Hodge-like: As $\gamma$ is co-closed, take some $\partial^*$ primitive $\alpha$, which is just an integer valued function of the vertices. Now, we can think of the graph as being grouped by the level sets of $\alpha$ and the only edges which travel between these level-set groupings are the edges of $\gamma$. Since $\gamma$’s coefficient’s are all $\pm 1$, we know that those edges can only go between “adjacent” level sets.

So suppose that the graph is in a surface as you describe and take some 2-simplex $\sigma$ in the surface. Observe that $\alpha$ can vary by at most 1 over the vertices of $\sigma$ — otherwise $\gamma$ has an edge of higher multiplicity.

Now, some $\sigma$ are going to have $\alpha$ constant on their vertices and so $\gamma$ must not include any of the edges from such a simplex.

The other possibility is that $\alpha$ varies by 1 over the vertices of $\sigma$. i.e. one of them is one different. However, in such a situation $\gamma$ must either have two edges going into (or out of) this vertex. That’s not a walk.

Posted by: Adam on May 20, 2016 8:03 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Hodge theory seems like a bad idea (or perhaps I am interpreting it too literally) because this seems to be all about the integral structure on the chain groups. Indeed, the statement (or rather, the generalization of it which seems most natural to me) is false with rational coefficients!

Consider the tetrahedron, with vertices $v_1$, $v_2$, $v_3$ and $v_4$. Write $e_{ij}$ for the edge $v_i \to v_j$. Then the chain

\tfrac{1}{2} e{14} + \tfrac{1}{4}(e{12}+e{24}+e{13}+e{14})$has boundary$v1-v4$and is orthogonal to every cycle. So the question is to understand the finite group$C0/\partial \mathrm{Ker}(\partial^{\ast}: C1 \to C2)$, which one can think of as the "integral failure of Hodge theory", and see that$u-v$is not in it for any vertices$u$and$v\$.

Posted by: David Speyer on May 9, 2016 3:43 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Thanks! That’s very helpful. I think I have a proof of the conjecture by now, and I’ll try to write it up today. But it’s still nice to set it in a context.

At some earlier stage I meant to look up everything I could on ‘integral Hodge theory for graphs’ — or more generally CW complexes equipped with some natural inner products on their chain groups. There should be some additional structure, beyond what’s visible in ordinary Hodge theory, arising from the fact that the range of each Laplacian $\partial^\ast \partial + \partial \partial^\ast$ is not big enough to be a complement to the kernel of that Laplacian, etc. — in short, various refinements that occur when you’re doing linear algebra over $\mathbb{Z}$ instead of a field.

That’s not mainly what I’m interested in now — I just need to prove this conjecture to make progress on topological crystallography — but it seems like a nice subject that someone should study, or have already studied.

Posted by: John Baez on May 9, 2016 5:34 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

You’re welcome! I also believe I have a proof, now posted at http://mathoverflow.net/a/238391/297

Posted by: David Speyer on May 9, 2016 5:51 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

David Jekel and I have recently written a paper about this very subject, entitled Torsion of the Graph Laplacian: Sandpiles, Electrical Networks, and Homological Algebra. It turns out that you can get some pretty interesting graph invariants by messing around with the algebraic properties of the Laplacian!

Posted by: Avi Levy on May 10, 2016 7:28 PM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

Thanks for pointing out your paper! Interesting!

Posted by: John Baez on May 21, 2016 4:03 AM | Permalink | Reply to this

Re: Which Paths Are Orthogonal to All Cycles?

After thinking more I’ve decided to avoid all mention of surfaces in this problem, since they turn out to be unnecessary. Here’s a new statement of the question:

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 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 a 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 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, let’s suppose $\Gamma$ has no bridges, meaning edges whose removal increases the number of connected components. The edge with the arrow on it in the picture above is a bridge.

Question: Suppose $\Gamma$ is a graph with no bridges. Any 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: I’m defining a path $\gamma$ to be 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

$c(\gamma) = \pm e_1 \pm e_2 \pm \; \cdots \;\pm e_m.$

Question: If $\Gamma$ is a graph with no bridges, and $\gamma$ is a path in $\Gamma$ such that the inner product of $c(\gamma)$ with every cycle vanishes, must we have $c(\gamma) = 0$?

The answer is yes, and I have two proofs now.

One, by David Speyer, uses ideas connected to Hodge theory.

Another, by Ilya Bogdanov and Greg Egan, explicitly constructs a 1-cycle $c$ with $\langle c(\gamma), c \rangle \ne 0$ whenever $\gamma$ is path with $c(\gamma) \ne 0$ in a bridgeless graph.

Posted by: John Baez on May 21, 2016 3:58 AM | Permalink | Reply to this

Post a New Comment