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.

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.

One thought on “Riemann-Roch theory for graph orientations

  1. Pingback: Reduced divisors and Riemann-Roch for Graphs | Matt Baker's Math Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s