In an earlier post, I described a graph-theoretic analogue of the Riemann-Roch theorem and some of its applications.  In this post, I’d like to discuss a proof of that theorem which is a bit more streamlined than the one which Norine and I gave in our original paper [BN].  Like our original proof, the one we’ll give here is based on the concept of reduced divisors.

We begin by recalling the statement of the theorem (using the standard terminology from algebraic geometry, as applied to graphs).  Let be a graph, by which we mean a finite, connected, undirected graph.  Multiple edges between vertices are allowed, but we do not allow loop edges connecting a vertex to itself.  We let (resp. ) denote the set of vertices (resp. edges) of .  The genus of is the number .

A divisor on is a formal sum of vertices of with integer coefficients, i.e., an element of the free abelian group on .  The degree of is , and is called effective if for all .  A principal divisor is a divisor of the form for some function , where is the sum of over all edges adjacent to .   Two divisors and are called linearly equivalent if their difference is principal.

One can describe linear equivalence in terms of a game of solitaire (often called chip-firing or the dollar game) played on the vertices of .  Two divisors and are linearly equivalent if one can get from the dollar configuration specified by to the one specified by via a sequence of legal moves, where a move consists of choosing a vertex and either borrowing or lending a dollar along each edge adjacent to .  (The number of times that a given vertex borrows or lends money in getting from to is encoded in the function above.)

The rank of a divisor, denoted , is defined as the maximum integer such that is equivalent to an effective divisor for all effective divisors of degree .  (Thus if is not equivalent to an effective divisor, and is non-negative otherwise.) In terms of the dollar game, if one thinks of the goal as getting all vertices out of debt, then iff the game with starting configuration is winnable, and iff the game is still winnable after subtracting dollars in an arbitrary way from .

The canonical divisor on is the divisor , where is the degree (or valence) of .  The degree of is .

Theorem (Riemann-Roch for Graphs): For every divisor on , we have .

The proof which we will give relies on finding a particularly nice representative (depending on the choice of a vertex q) for each linear equivalence class of divisors.  We call these nice representatives q-reduced divisors.  (I chose the name by analogy with Gauss’s notion of reduced quadratic forms, which yield nice representatives for ideal classes in quadratic number fields.)  A divisor on is called q-reduced if:

(i) is out of debt for all vertices , and

(ii) for every non-empty set of vertices not containing q, firing all elements of simultaneously causes some element of to go into debt.

Lemma 1: Each linear equivalence class of divisors on contains a unique q-reduced divisor.

Proof: We show existence, referring the reader to the proof of Proposition 3.1 in [BN] for uniqueness.  (The uniqueness assertion is not actually needed for the proof of the Riemann-Roch formula.)

We first use chip-firing moves to obtain a divisor equivalent to where no vertex except q is in debt.  This can be done by arranging the vertices in some order, starting with q, so that every vertex except for q has a neighbor that precedes it in this order. We then take the vertices out of debt consecutively, starting with the last vertex, at each step having some neighbor which precedes the current vertex lend out enough money to take out of debt.

If is q-reduced, we are done.  Otherwise, there is a non-empty set (disjoint from q) of vertices which can fire simultaneously without going into debt.  Fire all the vertices in and repeat.  It is not hard to see that this process cannot go on forever, so eventually we terminate at a q-reduced divisor equivalent to . Q.E.D.

To determine whether or not a divisor is q-reduced using the definition requires exponential time.  However, there is in fact a linear time algorithm for this problem, known as Dhar’s burning algorithm.

Dhar’s algorithm: Suppose satisfies condition (i) above, and for let there be firefighters at the vertex .  Each firefighter can stop fires in one direction.  Light a fire at q; the fire spreads continuously across the graph, burning through a vertex if the number of burnt edges adjacent to exceeds the number of firefighters at .  Then is q-reduced if and only if the fire eventually burns through the whole graph.

The proof of correctness for Dhar’s algorithm is straightforward and left to the reader.

Given an orientation of (i.e., an assignment of a direction to each edge), we define the associated divisor by , where is the number of incoming edges at .  It is easy to see that for every orientation .  Also, if denotes the reverse orientation then , the canonical divisor on .

Lemma 2: If is acyclic (i.e., contains no directed cycle) then is not equivalent to an effective divisor.

Proof: (Compare with [BN, Lemma 3.2]) Let be an arbitrary divisor equivalent to , and let be a connected component of the set of vertices where the function takes its maximum value.  The restriction of is an acyclic orientation of , and therefore it has a source vertex .  It is easy to check that , so in particular is not effective.  Q.E.D.

Following the terminology of Mikhalkin and Zharkov, we call a divisor of the form , where is an acyclic orientation, a moderator.  We call the dual moderator.

We now come to the key lemma in the theory:

Lemma 3: Given a divisor , either is equivalent to an effective divisor or is equivalent to an effective divisor for some moderator .

Proof:  Let be the unique q-reduced divisor equivalent to .  Run Dhar’s burning algorithm on and keep track of the direction in which the fire spreads as it burns through the graph.  This gives an acyclic orientation with associated moderator .  By our description of Dhar’s algorithm, we necessarily have for all .  If then is effective.  Otherwise and thus . Q.E.D.

Lemma 3 implies a useful formula for (Lemma 2.7 in [BN]).  In order to state it, given a divisor we define to be the sum of the non-negative coefficients in .

Corollary 1: for every divisor , where the minimum is taken over all divisors equivalent to and all moderators .

Proof: Let .  If , then there exists an effective divisor of degree for which .  By Lemma 3, there exists a moderator and an effective divisor such that .  But then for some divisor , which implies that , a contradiction.  Thus .  Conversely, if we choose divisors and achieving the minimum in the definition of then there are effective divisors with such that .  But then , which by Lemma 2 is not equivalent to any effective divisor.  It follows that .  Q.E.D.

The Riemann-Roch theorem for graphs can be deduced directly from Corollary 1 using the fact that for every moderator .

Proof of Riemann-Roch for Graphs: Note that for every moderator , we have .  Therefore

where the first two minima are over and and the last is over and .  Q.E.D.

Concluding observations:

1. For other proofs of Riemann-Roch for graphs, see the papers by Amini-Manjunath, Manjunath-Sturmfels, and Cori-LeBorgne.  My student Spencer Backman has recently discovered a different proof which I will blog about soon. [Note added: see https://mattbakerblog.wordpress.com/2014/01/23/riemann-roch-theory-for-graph-orientations/%5D

2. The above arguments can be extended to metric graphs (Mikhalkin-Zharkov) and metrized complexes of curves (Amini-Baker).

3. Reduced divisors are closely related to the G-parking functions of Postnikov-Shapiro and to the critical configurations of Biggs; see [BN] for a discussion.  They are also related to configurations in the abelian sandpile model which are both stable and recurrent.  David Perkinson has written a Sandpile package in Sage which, among other things, can compute the rank function r(D).

4. The first step in the proof of Lemma 1 was to show that there is a divisor equivalent to such that for all .  An alternate proof of this fact is as follows: since the Jacobian group is finite, for each vertex there is a positive integer such that the divisor is principal.  The result follows easily by adding appropriate positive integer multiples of each to .

5. For an alternate approach to the existence and uniqueness of reduced divisors on graphs, see this unpublished paper.  A metric graph argument of this argument appears in the Appendix to this paper.

6. Lemma 2 implies that the two alternatives in Lemma 3 cannot both occur.  From this one deduces easily that a divisor is equivalent to an effective divisor if and only if the unique q-reduced divisor equivalent to is effective.

7. It would be a big breakthrough to find a cohomological proof of the Riemann-Roch Theorem for Graphs.  Another major open problem is to formulate a higher-dimensional generalization analogous to the Hirzebruch-Riemann-Roch theorem in algebraic geometry.