Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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:vwe : v \to w \, when ee is an edge going from the vertex vv to the vertex ww. We get a vector space of 0-chains C 0(Γ,)C_0(\Gamma,\mathbb{R}), which are formal linear combinations of vertices, and a vector space of 1-chains C 1(Γ,)C_1(\Gamma,\mathbb{R}), which are formal linear combinations of edges. We also get a boundary operator

:C 1(Γ,)C 0(Γ,) \partial : C_1(\Gamma,\mathbb{Z}) \to C_0(\Gamma,\mathbb{Z})

sending each edge e:vwe: v \to w to the difference wvw - v. A 1-cycle is 1-chain cc with c=0\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 SS. 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 SS. 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:vwe : v \to w and their formal ‘inverses’ e 1:wve^{-1}: w \to v, like this:

e 1 ±:v 0v 1, e_1^{\pm} : v_0 \to v_1, e 2 ±:v 1v 2, e_2^{\pm} : v_1 \to v_2 , \dots e n ±:v n1v n e_n^{\pm} : v_{n-1} \to v_n

The corresponding 1-chain is the linear combination

c=±e 1±e 2±±e m c = \pm e_1 \pm e_2 \pm \; \cdots \;\pm e_m

Question: If the inner product of cc with every cycle vanishes, must we have c=0c = 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(Γ,)C_2(\Gamma, \mathbb{R}), which are formal linear combinations of faces, and picking an orientation on each face gives us a boundary operator

:C 2(Γ,)C 1(Γ,) \partial : C_2(\Gamma,\mathbb{Z}) \to C_1(\Gamma,\mathbb{Z})

which combined with the other one obeys

=0 \partial \partial = 0

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

e,f=±1 \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:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2880

19 Comments & 0 Trackbacks

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 γ 1\gamma_1 is any path that is not a loop, and it runs from vertex vv to vertex ww, then there must be a second, substantially distinct path γ 2\gamma_2 from vv to ww. We can then form a loop cc by following γ 1\gamma_1 and then γ 2 1\gamma_2^{-1}. This loop can’t be orthogonal to γ 1\gamma_1, since we have:

c,γ 1=γ 1,γ 1γ 2,γ 1\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 γ 1\gamma_1, while the second term must be less than that since γ 1\gamma_1 and γ 2\gamma_2 are substantially distinct.

So, for any path γ 1\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 γ 1\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,wv,w on the graph embedded in this surface, and seeking two ‘substantially distinct’ paths from vv to ww.

It seems helpful to find paths that aren’t ridiculously redundant. After all, if a path from vv to ww 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 vv to ww, we can always make it irredundant as follows. Suppose it goes through the vertex xx twice. Then it’s of the form γδϵ\gamma \delta \epsilon where δ\delta starts and ends at xx. Then γϵ\gamma \epsilon is another, strictly shorter, path from vv to ww. By repeating this move we must eventually reach an irredundant path from vv to ww.

(Note that if we apply this procedure to a loop that starts and ends at v=wv = 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 ee twice, nor can it contain can it edge ee and its inverse e 1e^{-1}, nor can it contain e 1e^{-1} twice

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

c,γ 1=γ 1,γ 1γ 2,γ 1 \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 γ 1\gamma_1 [….]

That’s true when γ 1\gamma_1 is irredundant, but not in general. Luckily we can always make γ 1\gamma_1 and γ 2\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 vv to ww 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 γ 1\gamma_1, we just need another path γ 2\gamma_2 with the same endpoints such that:

γ 1,γ 2γ 1,γ 1\langle \gamma_1, \gamma_2 \rangle \neq \langle \gamma_1, \gamma_1 \rangle

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

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

We want to construct the path γ 2\gamma_2 by taking γ 1\gamma_1 and substituting one of these “detours” in place of one of its edges, e ie_i. Generically, you’d expect the inner product of γ 1\gamma_1 and e ie_i to differ from the inner product of γ 1\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 pp is not simple, then it contains a cycle cc, and c,p=|c|>0\langle c,p\rangle=|c| \; > \; 0. Thus we may assume that pp is simple, so pp has the form v 0v 1v nv_0\to v_1\to\cdots\to v_n with v 0,v 1,,v nv_0,v_1,\dots,v_n distinct.

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

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 pp is not simple it contains a loop cc, but we don’t always have c,p=|c|\langle c, p \rangle = |c|, and indeed we can have c,p=0.\langle c, p \rangle = 0.

There are various kinds of counterexamples: here’s one. Suppose p=abcb 1c 1p = a b c b^{-1} c^{-1} where b,cb, c are loos that start and end at the same point but share no edges, and aa is path sharing no edges with bb or cc. Then pp is not simple, and it contains a loop cc, but p,c=0\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 *:C 0C 1\partial^*: C_0 \to C_1. You could also characterize them by saying *γ=0\partial^* \gamma = 0 and γ0\partial\gamma \neq 0, where the first condition refers to *:C 1C 2\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?

Adam wrote:

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, *\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 SS such that SΓS - \Gamma is a union of open disks whose closures are embedded closed disks. Any path in Γ\Gamma gives a 1-chain cC 1(Γ,)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 SS 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 cC 1(Γ,)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 GG was connected for simplicity. Suppose that GG had an edge ee where, if it was removed, GG would have two connected components. Call them G 0G_0 and G 1G_1. Let’s create a zero chain α= vV(G)α v[v]\alpha = \sum_{v \in V(G)} \alpha_v [v] such that α v=0\alpha_{v} = 0 if vG 0v\in G_0 and α v=1\alpha_v = 1 if vG 1v\in G_1. Then *α=e\partial^* \alpha =e and, since ee is coexact, ee 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 GG, 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 ±1\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 1v_1, v 2v_2, v 3v_3 and v 4v_4. Write e ije_{ij} for the edge v iv jv_i \to v_j. Then the chain

12e 14+14(e 12+e 24+e 13+e 14)\tfrac{1}{2} e_{14} + \tfrac{1}{4}(e_{12}+e_{24}+e_{13}+e_{14}) has boundary v 1v 4v_1-v_4 and is orthogonal to every cycle.

So the question is to understand the finite group C 0/Ker( *:C 1C 2)C_0/\partial \mathrm{Ker}(\partial^{\ast}: C_1 \to C_2), which one can think of as the “integral failure of Hodge theory”, and see that uvu-v is not in it for any vertices uu and vv.

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:vwe : v \to w \, when ee is an edge going from the vertex vv to the vertex ww. We get a vector space of 0-chains C 0(Γ,)C_0(\Gamma,\mathbb{R}), which are formal linear combinations of vertices, and a vector space of 1-chains C 1(Γ,)C_1(\Gamma,\mathbb{R}), which are formal linear combinations of edges. We get a boundary operator

:C 1(Γ,)C 0(Γ,) \partial : C_1(\Gamma,\mathbb{Z}) \to C_0(\Gamma,\mathbb{Z})

sending each edge e:vwe: v \to w to the difference wvw - v. A 1-cycle is a 1-chain cc with c=0\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:vwe : v \to w and their formal ‘inverses’ e 1:wve^{-1}: w \to v, like this:

e 1 ±:v 0v 1, e_1^{\pm} : v_0 \to v_1, e 2 ±:v 1v 2, e_2^{\pm} : v_1 \to v_2 , \dots e n ±:v n1v n. e_n^{\pm} : v_{n-1} \to v_n .

The corresponding 1-chain is

c(γ)=±e 1±e 2±±e m. 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(γ)c(\gamma) with every cycle vanishes, must we have c(γ)=0c(\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 cc with c(γ),c0\langle c(\gamma), c \rangle \ne 0 whenever γ\gamma is path with c(γ)0c(\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