Riemann-Roch theory for graph orientations

In this post, I’d like to sketch some of the interesting results contained in my Ph.D. student Spencer Backman’s new paper “Riemann-Roch theory for graph orientations”.

First, a bit of background. In a 2007 paper, Emeric Gioan introduced the cycle-cocycle reversal system on a (finite, connected, unoriented) graph G, which is a certain natural equivalence relation on the set of orientations of G. Recall that an orientation of G is the choice of a direction for each edge. A cycle flip on an orientation ${\mathcal O}$ consists of reversing all the edges in a directed cycle in ${\mathcal O}$ . Similarly, a cocycle flip consists of reversing all the edges in a directed cocycle in ${\mathcal O}$ , where a directed cocycle (also called a directed cut) is the collection of all oriented edges connecting a subset of vertices of G to its complement. The cycle-cocycle reversal system is the equivalence relation on the set of orientations of G generated by all cycle and cocycle flips. In his paper, Gioan proves (via a deletion-contraction recursion) the surprising fact that the number of equivalence classes equals the number of spanning trees in G. A bijective proof of this result was subsequently obtained by Bernardi.

One can profitably view Gioan’s theorem through the lens of Riemann-Roch theory for graphs. There is a natural map $\psi$ from the set of equivalence classes of orientations of G to ${\rm Pic}^{g-1}(G)$ , the set of degree $g-1$ divisors on G modulo linear equivalence (see this blog post for the definition of divisors and linear equivalence). The map $\psi$ takes $[{\mathcal O}]$ to the linear equivalence class of the divisor $D_{\mathcal O}$ defined by $D_{\mathcal O} = \sum ({\rm indeg}_{\mathcal O}(v) - 1)(v)$ , where ${\rm indeg}_{\mathcal O}(v)$ denotes the number of edges pointing toward $v$ . This map turns out to be a bijection. One way to see this is to first prove (as in Section 3 of Spencer’s paper) that if $D_{\mathcal O}$ and $D_{{\mathcal O}'}$ are linearly equivalent then $\mathcal O$ and ${\mathcal O}'$ are equivalent in the cycle-cocycle reversal system, and thus $\psi$ is injective. It is well-known that the cardinality of ${\rm Pic}^d(G)$ is the number of spanning trees of G for every integer $d$ ; this follows for example from Kirchhoff’s Matrix-Tree Theorem and some simple linear algebra (see for example this paper). Therefore Gioan’s theorem implies that $\psi$ is a bijection. Alternatively, one can see this without Gioan’s theorem (thereby obtaining a new proof of his result) by showing directly that $\psi$ is surjective; this is done for example in Theorem 4.7 from [ABKS], which says that every divisor of degree $g-1$ is equivalent to a divisor of the form $D_{\mathcal O}$ for some orientation ${\mathcal O}$ .

Spencer notes in his paper that the bijection $\psi$ is in fact an isomorphism of ${\rm Pic}^0(G)$ -torsors. The action of ${\rm Pic}^0(G)$ on equivalence classes of orientations is defined as follows. Every element of ${\rm Pic}^0(G)$ can be written as (the linear equivalence class of) a sum of divisors of the form $(p) - (q)$ , so it suffices to explain how $[(p)-(q)]$ acts on $[{\mathcal O}]$ . For this, we use Gioan’s theorem that every orientation ${\mathcal O}$ is equivalent to a q-connected orientation, meaning an orientation which contains a directed path from q to every other vertex. So we may assume that $[{\mathcal O}]$ is q-connected, in which case the action of $[(p)-(q)]$ on $[{\mathcal O}]$ is given by reversing all the edges in a directed path from q to p.

The majority of Spencer’s paper is devoted to a systematic generalization of Gioan’s theory to partial orientations, in which some edges are allowed to remain unoriented. This allows him to study divisors of degree less than $g-1$ via a generalization of the cycle-cocycle reversal system. One defines the divisor $D_{\mathcal O}$ associated to a partial orientation as above, but to get the correct equivalence relation one needs to introduce an additional kind of move called an edge pivot, whereby an edge oriented towards $v$ is unoriented and an unoriented edge adjacent to $v$ is oriented towards $v$ .

A partial orientation with (a) an edge pivot, (b) a cocycle reversal, and (c) a cycle reversal.

It is easy to see that edge pivots and cycle reversals both leave the divisor associated to a partial orientation unchanged. The generalized cycle-cocycle reversal system is the equivalence relation on partial orientations generated by cycle flips, cocycle flips, and edge pivots. Spencer proves that two partial orientations ${\mathcal O}$ and ${\mathcal O}'$ are equivalent in this system if and only if their associated divisors $D_{\mathcal O}$ and $D_{{\mathcal O}'}$ are linearly equivalent. Moreover, one has the following fundamental dichotomy:

Theorem 1: If $D$ is a divisor of degree at most $g-1$ on G, then exactly one of the following two possibilities holds: (a) $D$ is linearly equivalent to $D_{\mathcal O}$ for some sourceless partial orientation ${\mathcal O}$ ; or (b) $D$ is linearly equivalent to a divisor dominated by $D_{{\mathcal O}'}$ for some acyclic partial orientation ${\mathcal O}'$ .

(Here $g$ is the genus of G, i.e., the number of edges minus the number of vertices plus one, and a partial orientation is called sourceless if every vertex has at least one incoming directed edge and acyclic if it has no directed cycles. By definition, ${\mathcal O}$ is sourceless iff $D_{\mathcal O}$ is effective.) The fact that (a) and (b) cannot both occur is closely related to the well-known fact that every acyclic orientation of a graph has a source.

The proof of Theorem 1 is constructive; it gives a polynomial-time algorithm to determine which of (a) and (b) occurs and construct either ${\mathcal O}$ or ${\mathcal O}'$ , accordingly. As a corollary of Theorem 1, Spencer gets a new proof of Theorem 4.7 from [ABKS] which was mentioned above.

Spencer also obtains an interesting formula for $r(D_{\mathcal O})$ (see this post for the definition of the rank $r(D)$ of a divisor):

Theorem 2: If $\mathcal O$ is a partial orientation, then $r(D_{\mathcal O})$ is one less than the minimum number of directed paths which need to be reversed in the generalized cycle-cocycle reversal system to produce an acyclic partial orientation.

In other words, define a new graph $\hat{G}$ whose vertices are equivalence classes of partial orientations of G, with an edge between two equivalence classes if and only if they can be represented by partial orientations ${\mathcal O}$ and ${\mathcal O}'$ where ${\mathcal O}'$ is obtained from ${\mathcal O}$ by reversing a directed path. Then $r(D_{\mathcal O})$ is one less than the distance in $\hat{G}$ from $[D_{\mathcal O}]$ to the acyclic locus. (Spencer actually proves an a priori stronger result where equivalence of partial orientations is defined without cycle flips; he calls this the generalized cocycle reversal system.)

Spencer uses Theorems 1 and 2 to give a new proof of the Riemann-Roch theorem for graphs which does not make use of reduced divisors or Dhar’s algorithm. Here is a variant of the proof given in Spencer’s paper, which only requires Theorem 1. By the arguments given in this blog post, it suffices to prove that given a divisor $D$ , either $D$ is equivalent to an effective divisor or $D_{\mathcal O} - D$ is equivalent to an effective divisor for some acyclic orientation $\mathcal O$ . If $D$ has degree at most $g-1$ , this follows from Theorem 1 together with the easy fact that every acyclic partial orientation can be extended (greedily) to a full acyclic orientation. If ${\rm deg}(D) \geq g$ , it remains to show that $D$ is equivalent to an effective divisor. It suffices to prove this statement when ${\rm deg}(D) = g$ , in which case $D-(q)$ has degree $g-1$ and is therefore equivalent to $D_{\mathcal O}$ for some q-connected orientation $\mathcal O$ . By definition we have $D_{\mathcal O}(v) \geq 0$ for $v \neq q$ and $D_{\mathcal O}(q) \geq -1$ , which proves what we want.

Concluding observations:

1. According to Theorem 4.10 of [ABKS], every divisor of degree $g-1$ is linearly equivalent to a unique divisor of the form $D_{\mathcal O}$ where ${\mathcal O}$ is a q-connected orientation (called a q-orientable divisor in [ABKS]). The constructions in Spencer’s paper give a polynomial-time algorithm to compute the unique q-orientable divisor equivalent to $D$ (the algorithm in [ABKS] takes exponential time). Using Lemma 3.3 of [ABKS], which asserts that the map $D \mapsto D - (q)$ gives a bijection between the break divisors of Mikhalkin-Zharkov and q-orientable divisors, it follows that there is a polynomial-time algorithm to compute the unique break divisor equivalent to a given divisor of degree $g$ on G.

2. According to Theorem 4.5 of [ABKS], a divisor of degree $g-1$ is orientable (i.e., has the form $D_{\mathcal O}$ for some orientation ${\mathcal O}$ ) if and only if $\chi(S,D) \geq 0$ for every non-empty subset $S$ of vertices of G. (Here $\chi(S,D)$ denotes the degree of $D$ restricted to $S$ plus the topological Euler characteristic (number of vertices minus the number of edges) of the induced subgraph $G[S]$ .) Although we did not know it when we originally wrote [ABKS], this result is just a reformulation of an old theorem of Hakimi, rediscovered independently later on by Felsner. Building on an observation of Felsner, Spencer proves the remarkable fact that Theorem 4.5 of [ABKS] is equivalent to the celebrated Max-Flow Min-Cut theorem in graph theory. The proof of this equivalence gives a second polynomial-time algorithm for computing the unique q-orientable divisor associated to a given divisor. Spencer writes in his paper: “It might be natural to view [Hakimi’s] theorem historically as an extension to arbitrary graphs of Landau’s characterization of score vectors for tournaments… although it seems that Hakimi was unaware of Landau’s result which was presented in a paper on animal behavior a decade earlier.”

3. If we take $S$ to be the set of all vertices of G in the definition of $\chi(S,D)$ , we obtain $\chi(G,D) = {\rm deg}(D) + 1 - g$ , which is the right-hand side of the Riemann-Roch formula. This is suggestive of a deeper connection between the Riemann-Roch theorem for graphs and the Max-Flow Min-Cut theorem yet to be unearthed…

4. Spencer’s paper uses Theorem 2 to give an elegant new proof of my student Ye Luo’s topological characterization of rank-determining subsets of metric graphs (see this paper).

5. Spencer is currently writing up a generalization of the above results to metric graphs.

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Riemann-Roch theory for graph orientations

2 thoughts on “Riemann-Roch theory for graph orientations”

Leave a Reply Cancel reply

Share this:

Like this:

Related

2 thoughts on “Riemann-Roch theory for graph orientations”

Leave a Reply Cancel reply