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 consists of reversing all the edges in a directed cycle in . Similarly, a cocycle flip consists of reversing all the edges in a directed cocycle in , 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 from the set of equivalence classes of orientations of G to , the set of degree divisors on G modulo linear equivalence (see this blog post for the definition of divisors and linear equivalence). The map takes to the linear equivalence class of the divisor defined by , where denotes the number of edges pointing toward . 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 and are linearly equivalent then and are equivalent in the cycle-cocycle reversal system, and thus is injective. It is well-known that the cardinality of is the number of spanning trees of G for every integer ; 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 is a bijection. Alternatively, one can see this without Gioan’s theorem (thereby obtaining a new proof of his result) by showing directly that is surjective; this is done for example in Theorem 4.7 from [ABKS], which says that every divisor of degree is equivalent to a divisor of the form for some orientation .
Spencer notes in his paper that the bijection is in fact an isomorphism of -torsors. The action of on equivalence classes of orientations is defined as follows. Every element of can be written as (the linear equivalence class of) a sum of divisors of the form , so it suffices to explain how acts on . For this, we use Gioan’s theorem that every orientation 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 is q-connected, in which case the action of on 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 via a generalization of the cycle-cocycle reversal system. One defines the divisor 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 is unoriented and an unoriented edge adjacent to is oriented towards .
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 and are equivalent in this system if and only if their associated divisors and are linearly equivalent. Moreover, one has the following fundamental dichotomy:
Theorem 1: If is a divisor of degree at most on G, then exactly one of the following two possibilities holds: (a) is linearly equivalent to for some sourceless partial orientation ; or (b) is linearly equivalent to a divisor dominated by for some acyclic partial orientation .
(Here 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, is sourceless iff 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 or , 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 (see this post for the definition of the rank of a divisor):
Theorem 2: If is a partial orientation, then 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 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 and where is obtained from by reversing a directed path. Then is one less than the distance in from 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 , either is equivalent to an effective divisor or is equivalent to an effective divisor for some acyclic orientation . If has degree at most , 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 , it remains to show that is equivalent to an effective divisor. It suffices to prove this statement when , in which case has degree and is therefore equivalent to for some q-connected orientation . By definition we have for and , which proves what we want.
1. According to Theorem 4.10 of [ABKS], every divisor of degree is linearly equivalent to a unique divisor of the form where 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 (the algorithm in [ABKS] takes exponential time). Using Lemma 3.3 of [ABKS], which asserts that the map 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 on G.
2. According to Theorem 4.5 of [ABKS], a divisor of degree is orientable (i.e., has the form for some orientation ) if and only if for every non-empty subset of vertices of G. (Here denotes the degree of restricted to plus the topological Euler characteristic (number of vertices minus the number of edges) of the induced subgraph .) 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 to be the set of all vertices of G in the definition of , we obtain , 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.