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 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. Continue reading →

### Like this:

Like Loading...