22
$\begingroup$

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:

enter image description here

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 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$?

I believe someone should have settled this by now, since it sounds easy, and the space of 1-chains orthogonal to all 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:

but I suspect there's a lot more known about this subject!

[Note: I have edited my original question to simplify the hypotheses, and also called elements of $Z_1(\Gamma,\mathbb{R})$ 1-cycles, to distinguish them from cycles in the sense of graph theory.]

$\endgroup$
  • $\begingroup$ What do you mean by "embedded"? $\endgroup$ – darij grinberg May 13 '16 at 6:36
  • 1
    $\begingroup$ Also, I don't get the second boldfaced question. If your digraph is a directed $2m $-cycle, and $c (\gamma) $ is the alternating sum of the arcs of this cycle (i.e., sum of all even arcs minus sum of all odd arcs), then isn't $c (\gamma)=0$? Or do you mean $\partial(c (\gamma)) =0$? $\endgroup$ – darij grinberg May 13 '16 at 6:41
  • $\begingroup$ I think that the alternating sum you mentioned isn't a path, since the vertices don't line up as specified by Baez's definition, @darijgrinberg. Say $m=2$ and the cycle has edges $abcd$. You're proposing $ab^{-1}cd^{-1}$ but (writing $s$ and $t$ for source and target), $s(b^{-1}) = t(b) \neq t(a)$. (And I promise I'm not stalking you, the other notification is just a coincidence. ;)) $\endgroup$ – Omar Antolín-Camarena May 13 '16 at 20:09
  • $\begingroup$ @OmarAntolín-Camarena: Ah! I misunderstood the definition of a path indeed. $\endgroup$ – darij grinberg May 13 '16 at 20:28
6
$\begingroup$

$\def\ZZ{\mathbb{Z}}$The answer to the boldfaced question is yes. Let $\Gamma$ be a connected graph with no cut edges. We will show that, if $\gamma \in C_1(\Gamma, \ZZ)$ with $\partial \gamma$ of the form $[u] - [v]$ and $\langle \gamma, \delta \rangle =0$ for all $\delta \in \mathrm{Ker}(\partial: C_1 \to C_0)$, then $\gamma=0$. We write $x \sim y$ to express that vertices $x$ and $y$ of $\Gamma$ are neighbors.

Proof: If $u=v$ then we have $\langle \gamma, \gamma \rangle =0$ so $\gamma=0$, as previously noted. So we may assume $u \neq v$.

For any vertex $w \in \Gamma$, let $D(w) = \sum_{x \sim w} [w \to x] \in C_1(\Gamma, \ZZ)$. The $D(w)$ form an integer spanning set for the cut space. (If $H$ is any subset of the vertices, then the vector associated to $H$ is $\sum_{w \in H} D(w)$.) So $\gamma = \sum_w n_w D(w)$ for some integers $n_w$. We thus have $$\partial \gamma = \sum_w n_w \left(d_w [w] - \sum_{x \sim w} [x] \right) = [u] - [v]$$ where $d_w$ is the degree of $w$.

For every vertex $w$ other than $u$ and $v$, we deduce $$d_w n_w = \sum_{x \sim w} n_x. \quad (\ast)$$ In other words, $n_w$ is the average of $n$ on the neighbors of $w$. (Conceptually, $n$ is "harmonic" away from $u$ and $v$.) Similarly, $$d_u n_u = \sum_{x \sim u} n_x+1 \quad (\dagger)$$ and $$d_v n_v = \sum_{x \sim v} n_x-1 \quad (\ddagger)$$

Let $M$ be the largest values of $n_w$ at any vertex $w$ of $\Gamma$ and let $U$ be the set of vertices where $n_w = M$. It follows from equation $(\ddagger)$ that $v \notin U$, so $U$ is not all of $\Gamma$.

For any vertex $w$ of $U$ other than $u$, the harmonic property $(\ast)$ forces all neighbors of $w$ to also be in $U$. So, if $u \not\in U$, then $U$ is a proper connected component of $\Gamma$, a contradiction.

We now know that $u \in U$, and only $u$ can border vertices of $\Gamma$ outside of $U$. And equation $(\dagger)$ forces $u$ to have a single neighbor $u'$ not in $U$, with $n_{u'}=n_u-1$.

But then $u \to u'$ is a cut edge separating off the component $U$, a contradiction. $\square$

$\endgroup$
  • $\begingroup$ Dumb question: you say " For any vertex $w$ of $U$ other than $u$, the harmonic property $(\ast)$ forces..." But you're only asserting $(\ast)$ for vertices other than than $u$ and $v$. What about $v$? (I have not attempted to actually think about this yet.) $\endgroup$ – John Baez May 9 '16 at 20:45
  • $\begingroup$ Yes, the inequality points the right way at $v$. I should edit to make this clearer but I'll just write it here: for $w \neq u$, $v$, the value $n_w$ is the average of its neighbors so, if $n_w$ is the maximum $M$ then $n_x=M$ for all $x \sim w$. At $v$, the value $n_v$ is less than the average of the neighbors, so $n_v$ simply can't be maximal. $\endgroup$ – David E Speyer May 9 '16 at 21:19
  • $\begingroup$ I think a bit of fine print is needed to explain why $u \in U$. If $M$ is achieved at some vertex $m$, $U$ will "spread" to all vertices for which there is a path from $m$ that doesn't pass through $u$ or $v$. It might be that every path from $m$ to $u$ passes through $v$ (this need not contradict the no-bridge condition). But then $v$ will have a neighbour in $U$, and $(\ast)$ will force $v \in U$, contradicting $(\ddagger)$ which forces $v \notin U$. $\endgroup$ – Greg Egan May 10 '16 at 1:06
  • $\begingroup$ If $u \not \in U$, then there are no edges from $U$ to the rest of $\Gamma$, violating that $\Gamma$ is connected. But I agree that I should improve the writing. $\endgroup$ – David E Speyer May 10 '16 at 1:43
  • $\begingroup$ If $\Gamma - \{v\}$ is not connected, I don't think it follows from $\Gamma$ itself being connected that $u \in U$, since (at first glance) $U$ could be confined to the component of $\Gamma - \{v\}$ that does not contain $u$. That can easily be shown to lead to a contradiction about $v$, but I think that small extra argument is necessary. $\endgroup$ – Greg Egan May 10 '16 at 4:17
5
$\begingroup$

EDIT Take te multiset of all edges of $\gamma$; if it contains a pair of inverse edges, remove it, and repeat this while possible. If the resulting multiset is empty, then $c(\gamma)=0$, otherwise we will find a cycle with nonzero product with $\gamma$.

Now each edge appears in only one direction, the in-degree and out-degree of each vertex with respect to this multiset are equal, except for $v_0$ and $v_n$ (if they are distinct). If this multiset contains a subset which forms a cycle $C$, then $\langle \gamma, C\rangle=|C|>0$. Otherwise, let us move along the edges from $v_0$, not passing any edge twice. We either come twice to some vertex (thus finding a cycle), or finish at $v_n$. In the latter case, we have passed all the edges (otherwise the remaining ones form a cycle again).END OF EDIT

Thus we may assume that $\gamma$ is simple, so $\gamma$ has the form $v_0\to v_1\to\dots\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 $\gamma$. 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\dots\to v_n$, provides a cycle having a positive product with $\gamma$.

$\endgroup$
  • 1
    $\begingroup$ I like the idea of this proof, but I don't see how to make it rigorous. If a path $p$ is not simple it contains a cycle $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 cycles 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 cycle $c$, but $\langle p, c \rangle = 0$. $\endgroup$ – John Baez May 8 '16 at 21:09
  • $\begingroup$ Just follow the path (starting from the first vertex) until you come to some vertex for the second time. The segment of the path between two visits is a <i>simple</i> cycle for which the claim holds. $\endgroup$ – Ilya Bogdanov May 10 '16 at 10:35
  • 1
    $\begingroup$ Applying Ilya's prescription to John's example would identify $b$ as the simple cycle of choice. But $\langle p,b \rangle=0$. $\endgroup$ – Greg Egan May 10 '16 at 11:19
  • $\begingroup$ .I see your point. I've tried to rewrite this part; is it better now? $\endgroup$ – Ilya Bogdanov May 12 '16 at 15:56
  • $\begingroup$ You say "Take the multiset of all edges of γ; if it contains a pair of inverse edges, remove it, and repeat this while possible". Suppose I have a path like $e_1 e_2 e_3 e_4 e_2^{-1}$ where $e_1: v_1 \to v_2$, $e_2: v_2 \to v_3$, $e_3: v_3 \to v_4$, $e_4: v_4 \to v_3$. There is a pair of inverse edges in this path, but if I try to remove them, I get $e_1 e_3 e_4$ which is not a well-defined path, since $e_3$ doesn't start where $e_1$ ends. $\endgroup$ – John Baez May 14 '16 at 18:14
5
$\begingroup$

This answer is an attempt to slightly rephrase Ilya's argument; I would have written it as a comment, but there's not enough room.

Given a path $\gamma$ with endpoints $v_0$ and $v_n$, we have a 1-chain $c(\gamma)$, which is an integer-linear combination of edges of the graph. Let $E_{c(\gamma)}$ be the set of edges with non-zero coefficients in $c(\gamma)$; this need not include every edge that appears in the path, since some might cancel to zero in the 1-chain. If we think of these edges as decorated with the integer coefficients they inherit from the 1-chain $c(\gamma)$, we can associate a 1-chain with any subset of $E_{c(\gamma)}$.

It's possible that $E_{c(\gamma)}$ as a subgraph of $\Gamma$ contains several connected components that share no vertices with each other, but since the boundary of $c(\gamma)$ is only non-zero on $v_0$ and $v_n$, and it's impossible for a 1-chain to have a single-point boundary, these components would need to include exactly one whose 1-chain's boundary was non-zero on $v_0$ and $v_n$, and all the rest would have to give 1-cycles. Since they're all disjoint, any one of the 1-cycles $\chi$ would satisfy $\langle c(\gamma), \chi \rangle = \langle \chi, \chi \rangle \gt 0$.

Assuming now that $E_{c(\gamma)}$ is connected as a subgraph, we can build up a 1-chain $\sigma$ with a positive inner product with $c(\gamma)$ as follows. Starting at $v_0$, pick an edge $\epsilon_1$ incident on $v_0$, and put $\pm \epsilon_1$ in $\sigma$, with the sign chosen to be the same as the coefficient of $\epsilon_1$ in $c(\gamma)$. Then advance to the other vertex of $\epsilon_1$, and choose an edge $\epsilon_2$ such that $\epsilon_2 \ne \epsilon_1$, and $\pm \epsilon_2$ with the same sign as the coefficient of $\epsilon_2$ in $c(\gamma)$ gives a boundary for $\pm \epsilon_1 \pm \epsilon_2$ that is zero at the current vertex. This must be possible (assuming we haven't ended up at an endpoint of the path), since the boundary of $c(\gamma)$ is zero at the current vertex, so the signs of the edge coefficients in $c(\gamma)$ can't all give boundaries of the same sign here.

We continue this process until we reach either $v_n$, the endpoint of the path, or a vertex we've visited before. If we reach a vertex we've visited before, we can drop any earlier edges from $\sigma$ and obtain a 1-cycle with a positive inner product with $c(\gamma)$.

If we reach $v_n$, there are two possibilities. If $\sigma = c(\gamma)$ then $\sigma$ describes a simple path $\gamma'$ from $v_0$ to $v_n$ with the same 1-chain as our original path, and we can proceed to use that simple path in place of $\gamma$. If $\sigma \ne c(\gamma)$, it nonethless has the same boundary. Since $\sigma$ is supported on a subset of the same edges as $c(\gamma)$, and its coefficients are of the same sign but never greater in magnitude (and must be less on at least one edge), $\langle c(\gamma), \sigma \rangle$ will be strictly less than $\langle c(\gamma), c(\gamma) \rangle$. So we'll have a non-trivial 1-cycle $\ell = c(\gamma) - \sigma$, and:

$$\langle c(\gamma), \ell \rangle = \langle c(\gamma), c(\gamma) \rangle - \langle c(\gamma), \sigma \rangle \gt 0$$

Finally, suppose we have a simple path $\gamma': v_0 \to v_1 \to \dots \to v_n$ with the same 1-chain as $\gamma$. (The following refinement of Ilya's argument is something that John described to me in correspondence.) Since the edge $e_n: v_{n-1} \to v_n$ cannot be a bridge, there must be a path joining $v_n$ to $v_0$ that does not include that $e_n$. If we follow that path only as far as the first of the $v_i$ it reaches, we will have a path $\rho: v_n \to v_i$ which uses no edges of the simple path $\gamma'$. We can then append the portion of $\gamma'$ that goes from $v_i$ to $v_n$, call it $\gamma'_i$, to obtain a 1-cycle $c(\rho) + c(\gamma'_i)$ that must have a positive inner product with $c(\gamma)$:

$$\langle c(\gamma), c(\rho) + c(\gamma'_i) \rangle = \langle c(\gamma'_i), c(\gamma'_i) \rangle \gt 0$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.