# 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.