Riemann-Roch for Graphs and Applications

I plan to write several posts related to the Riemann-Roch Theorem for Graphs, which was published several years ago in this paper written jointly with Serguei Norine. In this post I want to explain the statement of the theorem, give some anecdotal background, and mention a few applications which have been discovered in recent years.

The Riemann-Roch Theorem

The (classical) Riemann-Roch Theorem is a very useful result about analytic functions on compact one-dimensional complex manifolds (also known as Riemann surfaces). Given a set of constraints on the orders of zeros and poles, the Riemann-Roch Theorem computes the dimension of the space of analytic functions satisfying those constraints. More precisely, if $D$ denotes the set of constraints and $r(D)$ is the dimension of the space of analytic functions satisfying those constraints, then the Riemann-Roch theorem asserts that

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

where $g$ is the genus (“number of holes”) of the Riemann surface $X$ , ${\rm deg}(D)$ is the total number of constraints, and $K$ is the “canonical divisor” on $X$ . See the Wikipedia page for much more information.

Before formulating the combinatorial analogue of this result which Norine and I discovered, I want to briefly reminisce about how this result came about. In the summer of 2006, my Georgia Tech REU (Research Experience for Undergraduates) student Dragos Ilas worked on a graph-theoretic conjecture which I had made some time earlier. Dragos spent eight weeks working on the problem and compiled a lot of experimental evidence toward my conjecture. He gave a talk about the problem one Friday toward the end of the summer in an REU Mini-Conference that I was organizing at Georgia Tech. Serguei Norine (then a postdoc working with my colleague Robin Thomas) was in the audience. On Monday morning, Serguei knocked on my office door and showed me an extremely clever proof of my conjecture. I told Serguei about my real goal, which was to prove a graph-theoretic analogue of the Riemann-Roch theorem. I outlined what I had in mind and within a week, we had exactly the kind of Riemann-Roch formula that I had hoped for… thanks in large part to Serguei’s amazing combinatorial mind!

Riemann-Roch for Graphs

To explain our result, consider the following game of solitaire played on a (finite connected) graph $G$ . The game begins with an initial configuration $D$ , which is an assignment of some integer number of dollars (which could be positive, negative, or zero) to each vertex of $G$ . A vertex with a negative number of dollars is said to be in debt.

There are two kinds of legal moves in the game. A lending move consists of selecting a vertex $v$ and then moving one dollar across each edge adjacent to $v$ in such a way that the money flows from $v$ to its neighbors. A borrowing move is similar, except that the money flows in the other direction. For example, here is an illustration of a borrowing move performed on the famous Petersen graph. The picture on the left shows the starting configuration, and the picture on the right shows the new configuration after the top vertex performs a borrowing move:

The goal of the game is to get all the vertices of $G$ out of debt by a sequence of legal moves.

I stumbled upon the idea that there ought to be a graph-theoretic avatar of the Riemann-Roch Theorem while investigating “p-adic Riemann surfaces” (for the experts: Berkovich curves). At the time I didn’t know precisely how to formulate the combinatorial Riemann-Roch theorem, but I knew that the following should be a special case (this was the REU problem mentioned above):

(♠) Let $g = \# \textrm{edges} - \# \textrm{vertices} + 1$ be the genus of $G$ and let $N$ denote the total number of dollars in the game at any time. If $N \geq g$ , then the game is always winnable

For example, in the Petersen graph game depicted above, we have $g= N = 6$ so the conjecture implies that the game depicted there should be winnable (which it is — see if you can find a winning set of moves!).

We need just a little more notation. Let $K$ be the canonical configuration $K(v) = (\# \textrm{edges adjacent to } v) - 2.$ For each configuration $D$ , define its degree deg(D) to be the total number of dollars present. Finally, we define the rank $r(D)$ to be $-1$ if the game starting with $D$ is not winnable, and otherwise to be the largest integer $k$ such that the game is still winnable after subtracting $k$ dollars from $D$ in an arbitrary way.

Theorem (Riemann-Roch for Graphs): For any configuration $D$ on any graph $G$ ,
$r(D) - r(K-D) = {\rm deg}(D) + 1 - g.$

It is easy to deduce (♠) above from this result. Riemann-Roch for Graphs also shows that there is a subtle duality present in the dollar game which is not readily apparent. For example, if $D$ is a configuration of degree $g-1$ , then the game with initial configuration $D$ is winnable if and only if the game with initial configuration $K-D$ is winnable.

When we originally proved the graph-theoretic Riemann-Roch theorem, I did not have specific applications in mind, although I had a hunch that it would some day prove useful. This hunch turned out to be correct! Here are three examples:

1. (Algebraic Geometry) I made the following conjecture based on computational evidence assembled by my Georgia Tech REU student Adam Tart:

Brill-Noether Conjecture for Graphs: Given positive integers $g$ , $r$ , and $d$ , every graph with genus $g$ has a configuration of degree $d$ and rank at least $r$ if and only if $(r+1)(g-d+r) \leq g$ .

In this paper, I proved a metric graph analogue of the “if” direction of this conjecture, and also showed that the “only if” part of this result implies the corresponding result in classical algebraic geometry, which is the (non-existence part of the) celebrated Brill-Noether theorem. Despite its name, the Brill-Noether theorem was first proved by Griffiths and Harris in 1980. (Brill and Noether gave a heuristic argument for why such a result for Riemann surfaces should be true in 1874.) The “only if” direction of my conjecture was subsequently proved in this paper by Cools, Draisma, Payne, and Robeva; they make crucial use of my Ph.D. student Ye Luo’s fundamental theorem on rank-determining sets (see this paper). The “if” direction remains open…

2. (Combinatorics) In this recent paper written with Yang An (a Chinese undergraduate from Xi’an who spent Fall 2012 visiting Georgia Tech as part of a visiting student program), Farbod Shokrieh (my former student, now a postdoc at Cornell), and Greg Kuperberg, we use many of the ideas behind Riemann-Roch for Graphs to give a volume proof (which, as Greg Kuperberg says, is even better than a bijective proof) of a famous result in combinatorics, Kirchhoff’s Matrix-Tree Theorem. Specifically, associated to a graph $G$ there is a $g$ -dimensional real torus $J(G)$ called the tropical Jacobian of $G$ , which is completely analogous to the Jacobian of a compact Riemann surface. We prove that there is a (canonical up to translation) polyhedral decomposition of $J(G)$ into $\kappa_G$ parallelepipeds each of volume $1/{\rm vol}(J(G))$ , where $\kappa_G$ is the number of spanning trees in $G$ . On the other hand, the volume ${\rm vol}(J(G))$ can be computed as the square root of the absolute value of the determinant of any cofactor of the Laplacian matrix of $G$ . Therefore this determinant is equal to the number of spanning trees in $G$ , which is Kirchhoff’s theorem. The polyhedral decomposition of $J(G)$ which we introduce contains a lot more interesting information that just the volumes of its pieces, so this should not be viewed as “just another proof” of Kirchhoff’s result. I will write another blog post at some point explaining the details of this decomposition and what it encodes.

3. (Number Theory) There is also a beautiful application of Riemann-Roch for Graphs to number theory, which arose from a suggestion I made to David Zureick-Brown and Eric Katz. Their theorem is as follows:

Theorem (Katz, Zureick-Brown): Let $X$ be an algebraic curve of genus $g \geq 2$ defined over the field ${\mathbf Q}$ of rational numbers. Let $p$ be a prime number bigger than $2g$ and suppose that the Mordell-Weil rank $r$ of the Jacobian of $X$ satisfies $r < g$ . Then the number of rational points on $X$ is at most $\# {\bar X}({\mathbf F}_p)+ 2r$ , where ${\bar X}$ is the “reduction of $X$ modulo $p$ ” with respect to some proper regular model.

For example, one can deduce from this theorem that the only integers $x$ for which $x(x-1)(x-2)(x-5)(x-6)$ is a perfect square are 0,1,2,3,5,6, and 10.
I will blog about the proof of the theorem of Katz and Zureick-Brown another time… In the meantime, their paper is here and its relation to Riemann-Roch for Graphs is also explained here.

There are other interesting applications of Riemann-Roch for graphs as well, and I’m optimistic that this point of view will continue to be fruitful for researchers in algebraic geometry, combinatorics, and number theory.

Concluding observations:

1. An interactive java applet for playing the dollar game on a graph, written by Adam Tart, can be found here.

2. It turns out that if the dollar game is winnable, then it can always be won using only borrowing moves. More precisely, any winnable game can be won by simply using the “borrowing binge strategy”: any time there are vertices in debt, pick one of them and do a borrowing move. Repeat until everyone is out of debt! Moreover, the total number of borrowing moves required to win the game when playing the “borrowing binge strategy” is independent of which borrowing moves you do in which order. See Section 5.5 of my paper with Norine and the references therein for proofs of these facts.

3. The tropical Jacobian is defined and studied in this paper by Mikhalkin and Zharkov. That paper, and independently this paper by Gathmann and Kerber, used the results and arguments which Norine and I employed in order to formulate and prove a Riemann-Roch theorem in tropical geometry.

4. Another recent application of Riemann-Roch for Graphs to algebraic geometry, explained in this paper by Omid Amini and myself, is a generalization of the Eisenbud-Harris theory of limit linear series to semistable curves which are not necessarily of compact type. I will blog about that paper another time…

This entry was posted in Curves and their Jacobians, Graphs, Tropical geometry and tagged Brill-Noether theory, Chip firing, Curves and their Jacobians, Graphs, Matrix-Tree Theorem, Personal anecdotes, Rational points on curves, Riemann-Roch for Graphs. Bookmark the permalink.

27 thoughts on “Riemann-Roch for Graphs and Applications”

Pingback: Reduced divisors and Riemann-Roch for Graphs | Matt Baker's Math Blog
Tyler Foster says:

February 2, 2014 at 3:41 pm

What is deg(D) here? Is it just the total number of chips on the graph?

Reply
- mbakermath says:
  
  February 3, 2014 at 2:00 pm
  
  Yes, deg(D) is the total number of chips on the graph. I will clarify this in the post, thanks!
  
  Reply
Tyler Foster says:

February 3, 2014 at 10:23 pm

Suppose you have a smooth curve X over a non-archimedean field K, and suppose this curve degenerates to a singular curve over the residue field k of K. Suppose this special fiber is an snc divisor whose every component is a copy of P^1. Let L be a line bundle on X. Do I understand correctly that chip firing on the dual graph of the special fiber corresponds to passing between possible degenerations of L to line bundles on the special fiber? If so, how does a single lending or borrowing move correspond to the passage from one degeneration of L to another?

Reply
mbakermath says:

February 10, 2014 at 2:39 pm

Hi Tyler — Sorry for the delayed response. In your setup, let’s fix a model ${\mathfrak X}$ for X over the valuation ring R of K, and for simplicity let’s assume that K is discretely valued and the model is regular. To get a divisor D on the dual graph G of the special fiber from L, you need to first extend L to a line bundle $\bar{L}$ on ${\mathfrak X}$ , and then you can set $D = \sum (\bar{L} \cdot X_v) (v)$ , where the sum is over all vertices v of G and $X_v$ is the component of the special fiber corresponding to v. Linearly equivalent divisors on G correspond to different extensions of L to a line bundle $\bar{L}$ on the surface ${\mathfrak X}$ . For example, if you replace $\bar{L}$ by $\bar{L} \otimes O_{\mathfrak X}(X_v)$ , the associated divisor D gets modified by a single lending move at v. Does this make sense?

Reply
Tyler Foster says:

February 10, 2014 at 11:55 pm

It does make sense. The part I was really confused about though was how an $\mathscr{O_{\frak{X}}}(X_{v})$-twist translates into a lending move. Yoav Len explained it to me: If $D_{v}$ denotes the primitive divisor supported on $X_{v}$, then one obtains the change in the chip number at a given vertex $u$ as the number $D_{v}\cdot D_{u}$. For all $u\ne v$, this intersection number $D_{v}\cdot D_{u}$ is obvious, and gives the number corresponding to a lending move. At $u=v$, one can move the special fiber $D$ to the generic fiber to see that $D_{v}\cdot D=0$. The full lending move follows.

Reply
mbakermath says:

February 11, 2014 at 12:09 am

Yes, exactly.

Reply
Math student says:

February 20, 2014 at 1:38 pm

Is there a problem with the Java Applet for the dollar game? It won’t launch for me.

Reply
- mbakermath says:
  
  February 21, 2014 at 5:44 pm
  
  Most likely the problem is being caused by your computer’s Java security settings. If you have a Mac, try this:
  
  1) Click the apple logo in the top left hand corner of the computer screen, then click “System Preferences”.
  
  2) Click on the Java logo. The Java Control Panel should open.
  
  3) In the Java Control Panel, click the “Security” tab.
  
  4) Click “Edit site list” and add the following address: http://people.math.gatech.edu/~mbaker/GraphGame/GraphGame.html
  Then click Okay.
  
  Please let me know if that helps.
  
  Reply
Pingback: The Pentagon Problem | Matt Baker's Math Blog
Pingback: Math blog roundup | Quomodocumque
Pingback: Effective Chabauty | Matt Baker's Math Blog
Pingback: The Combinatorics of Break Divisors | Matt Baker's Math Blog
DukeBG says:

September 9, 2018 at 12:49 pm

I created a js implementation along with the editor after being inspired by the recent numberphile video.
duke.a-comics.ru/dollar/

Reply
- Matt Baker says:
  
  September 9, 2018 at 3:18 pm
  
  Nice implementation of the dollar game!
  
  Reply
altenalson says:

September 10, 2018 at 8:50 am

Hello Matt,
After playing around with the game, I saw that you can always win with just the “give” move. Does my theory hold on ? You mention, that “it can always be won using only borrowing moves”, but what about the “give” move ?

Another question, is there a way, from any graph to compute the least amount of moves required to win ?

Thanks

Reply
- Matt Baker says:
  
  September 10, 2018 at 2:39 pm
  
  Correct, you can also always win with only lending moves. If you use a combination of borrowing and lending moves, I believe it’s an open problem to find describe an optimal strategy for the dollar game, or to find good bounds for the least number of moves required to win the game. But if you use only borrowing (or only lending) moves, more is known; see the references in my paper with Norine and in https://arxiv.org/abs/1107.1313
  (You might also enjoy taking a look at my expository paper https://people.math.gatech.edu/~mbaker/pdf/g4g9.pdf)
  
  Reply
  - altenalson says:
    
    September 10, 2018 at 3:49 pm
    
    Your expository is nice, but sadly don’t answer this. Do you talk about https://arxiv.org/pdf/math/0608360.pdf ?
    I’ll take a look, but honestly I’m not a math heavy person, is there a definitive answer ? Like others, I’m here because of the Numberphile episode. I was hoping to code a nice game around this concept and was wondering if I can compute a score.
    
    Thanks
Matt Baker says:

September 10, 2018 at 7:44 pm

Yes that’s the paper with Norine I was talking about. I think the short answer to your question is that no, there is not a simple way to compute a “score” for the game in advance. The simplest thing, if you want to know in advance what kind of target score to give, might be to run a simulation using only borrowing moves (or only lending moves) and use that as a benchmark.

Reply
- altenalson says:
  
  September 11, 2018 at 7:34 am
  
  Hum, that’s unfortunate … Anyway, thanks for your answers and further documentation. I might try the “simulation” solution, but that looks like a very complexe solution to a mundane problem.
  
  Reply
flash1234567890 says:

July 12, 2019 at 3:46 am

Looking at remark 5.5 of your paper with Norine, you cite Theorem 1 of “M. Thorup. Firing games. preprint. Available at
http://citeseer.ist.psu.edu/thorup96firing.html, 2 pages, 1996″ but it seems that either I am not able to access this or the preprint has been deleted. Is there some way I can get a copy of the preprint?

Reply
- Matt Baker says:
  
  July 15, 2019 at 10:30 am
  
  Here is a working link: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=EA953C89FB0AD6693E2F2A10BFAC6FE2?doi=10.1.1.17.1725&rep=rep1&type=pdf
  
  Reply
Pingback: The Dollar Game — Numberphile — Mvience
Pingback: Colorings and embeddings of graphs | Matt Baker's Math Blog
Alex Jin says:

October 7, 2021 at 3:27 pm

I am a bit confused on why your definition of a genus here differ from what I read from other sources. Take the graph K3,3 complete 3 bipartite graph as an example, the formula E-V+1 would yield genus 4. However, from what I find from other sources, K3,3 can be embedded on a sphere with one handle, having a genus 1.
I am not sure why there is a difference here. Perhaps here, the genus is defined differently?

Reply
- Matt Baker says:
  
  October 7, 2021 at 3:40 pm
  
  Right, there are different usages of the word “genus” in the literature as applied to graphs. The “classical” usage is what you say – the minimal genus of a surface in which the graph can be embedded. But Norine and I redefined genus to mean E-V+1, which is more classically called the cyclomatic number, Euler number, or first Betti number of the graph. We did this because otherwise the analogy with the classical Riemann-Roch theorem gets obscured. In my own writing I reserve “topological genus” for what graph theorists traditionally call the genus.
  
  Reply
Pingback: Firing games and greedoid languages | Matt Baker's Math Blog