Reduced divisors and Riemann-Roch for Graphs

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 G 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 V(G) (resp. E(G)) denote the set of vertices (resp. edges) of G.  The genus of G is the number g = |E(G)| - |V(G)| + 1.

A divisor on G is a formal sum D = \sum a_v (v) of vertices of G with integer coefficients, i.e., an element of the free abelian group on V(G).  The degree of D is \sum a_v, and D is called effective if a_v \geq 0 for all v.  A principal divisor is a divisor of the form {\rm div(f)} for some function f : V(G) \to {\mathbf Z}, where {\rm div(f)} is the sum of f(w)-f(v) over all edges e=vw adjacent to v.   Two divisors D and D' 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 G.  Two divisors D and D' are linearly equivalent if one can get from the dollar configuration specified by D to the one specified by D' via a sequence of legal moves, where a move consists of choosing a vertex v and either borrowing or lending a dollar along each edge adjacent to v.  (The number of times that a given vertex borrows or lends money in getting from D to D' is encoded in the function f above.)

The rank of a divisor, denoted r(D), is defined as the maximum integer k such that D-E is equivalent to an effective divisor for all effective divisors E of degree k.  (Thus r(D)=-1 if D 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 r(D) \geq 0 iff the game with starting configuration D is winnable, and r(D) \geq k iff the game is still winnable after subtracting k dollars in an arbitrary way from D.

The canonical divisor on G is the divisor K = \sum ({\rm deg}(v) - 2)(v), where {\rm deg}(v) is the degree (or valence) of v.  The degree of K is 2g-2.

Theorem (Riemann-Roch for Graphs): For every divisor D on G, we have r(D) - r(K-D) = {\rm deg}(D) + 1 - g.

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 D on G is called q-reduced if:

(i) v is out of debt for all vertices v \neq q, and

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

Lemma 1: Each linear equivalence class of divisors on G 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 D' equivalent to D 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 w which precedes the current vertex v lend out enough money to take v out of debt.

If D' is q-reduced, we are done.  Otherwise, there is a non-empty set A (disjoint from q) of vertices which can fire simultaneously without going into debt.  Fire all the vertices in A 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 D. 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 D satisfies condition (i) above, and for v \neq q let there be D(v) firefighters at the vertex v.  Each firefighter can stop fires in one direction.  Light a fire at q; the fire spreads continuously across the graph, burning through a vertex v if the number of burnt edges adjacent to v exceeds the number of firefighters at v.  Then D 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 O of G (i.e., an assignment of a direction to each edge), we define the associated divisor D_O by D_O = \sum ({\rm indeg}_O(v) - 1)(v), where {\rm indeg}_O(v) is the number of incoming edges at v.  It is easy to see that {\rm deg}(D_O) = g-1 for every orientation O.  Also, if \bar{O} denotes the reverse orientation then D_O + D_{\bar O} = K, the canonical divisor on G.

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

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

Following the terminology of Mikhalkin and Zharkov, we call a divisor \nu of the form \nu = D_O, where O is an acyclic orientation, a moderator.  We call \bar\nu = D_{\bar O} the dual moderator.

We now come to the key lemma in the theory:

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

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

Lemma 3 implies a useful formula for r(D) (Lemma 2.7 in [BN]).  In order to state it, given a divisor D we define {\rm deg}^+(D) to be the sum of the non-negative coefficients in D.

Corollary 1: r(D) = {\rm min} \; {\rm deg}^+ (D' - \nu) - 1 for every divisor D, where the minimum is taken over all divisors D' equivalent to D and all moderators \nu.

Proof: Let r'(D) = {\rm min} \; {\rm deg}^+ (D' - \nu) - 1.  If r(D) < r'(D), then there exists an effective divisor E of degree r'(D) for which r(D-E) = -1.  By Lemma 3, there exists a moderator \nu and an effective divisor E' such that \nu - D + E \sim E'.  But then D' - \nu = E - E' for some divisor D' \sim D, which implies that {\rm deg}^+ (D' - \nu) \leq {\rm deg}(E) = r'(D), a contradiction.  Thus r(D) \geq r'(D).  Conversely, if we choose divisors D' \sim D and \nu achieving the minimum in the definition of r'(D) then there are effective divisors E,E' with \deg(E) = r'(D) + 1 such that D' - \nu = E - E'.  But then D - E \sim \nu - E', which by Lemma 2 is not equivalent to any effective divisor.  It follows that r(D) \leq r'(D).  Q.E.D.

The Riemann-Roch theorem for graphs can be deduced directly from Corollary 1 using the fact that \nu + \bar\nu = K for every moderator \nu.

Proof of Riemann-Roch for Graphs: Note that for every moderator \nu, we have {\rm deg}^+(D-\nu) = {\rm deg}(D) - g + 1 + {\rm deg}^+(\nu - D).  Therefore

r(D)+ 1 = {\rm min} \; {\rm deg}^+ (D' - \nu)

= {\rm deg}(D) - g + 1 + {\rm min} \; {\rm deg}^+(K - D'- (K - \nu))

= {\rm deg}(D) - g + 1 + {\rm min} \; {\rm deg}^+(K - D' - \nu')

= {\rm deg}(D) - g + 1 + r(K - D),

where the first two minima are over D' \sim D and \nu and the last is over D' \sim D and \nu'.  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 http://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 D' equivalent to D such that D'(v) \geq 0 for all v \neq q.  An alternate proof of this fact is as follows: since the Jacobian group {\rm Jac}(G) = {\rm Div}^0(G) / {\rm Prin}(G) is finite, for each vertex v there is a positive integer m_v such that the divisor D_v = m_v (v) - m_v (q) is principal.  The result follows easily by adding appropriate positive integer multiples of each D_v to D.

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 D is equivalent to an effective divisor if and only if the unique q-reduced divisor equivalent to D 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.

3 thoughts on “Reduced divisors and Riemann-Roch for Graphs

  1. Pingback: Riemann-Roch theory for graph orientations | Matt Baker's Math Blog

  2. Pingback: The Pentagon Problem | Matt Baker's Math Blog

  3. Hi,

    Can we show that the non-equivalent configurations of the same degree partition div(G)? But without going into g-parking functions and reduced divisors?
    I want to show how the converse of “Two configurations that are equivalent have same degree” is false!

    Any help is greatly appreciated

    Reply

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