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 denotes the set of constraints and is the dimension of the space of analytic functions satisfying those constraints, then the Riemann-Roch theorem asserts that

where is the *genus* (“number of holes”) of the Riemann surface , is the total number of constraints, and is the “canonical divisor” on . 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 . The game begins with an initial configuration , which is an assignment of some integer number of dollars (which could be positive, negative, or zero) to each vertex of . 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 and then moving one dollar across each edge adjacent to in such a way that the money flows from 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 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 be the *genus* of and let denote the total number of dollars in the game at any time. If , then the game is always winnable

For example, in the Petersen graph game depicted above, we have 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 be the *canonical configuration* For each configuration , define its *degree* deg(D) to be the total number of dollars present. Finally, we define the *rank * to be if the game starting with is not winnable, and otherwise to be the largest integer such that the game is still winnable after subtracting dollars from in an arbitrary way.

**Theorem** (Riemann-Roch for Graphs): For any configuration on any graph ,

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 is a configuration of degree , then the game with initial configuration is winnable if and only if the game with initial configuration 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 , , and , every graph with genus has a configuration of degree and rank at least if and only if .

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 there is a -dimensional real torus called the *tropical Jacobian* of , 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 into parallelepipeds each of volume , where is the number of spanning trees in . On the other hand, the volume can be computed as the square root of the absolute value of the determinant of *any cofactor of the Laplacian matrix* of . Therefore this determinant is equal to the number of spanning trees in , which is Kirchhoff’s theorem. The polyhedral decomposition of 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 be an algebraic curve of genus defined over the field of rational numbers. Let be a prime number bigger than and suppose that the Mordell-Weil rank of the Jacobian of satisfies . Then the number of rational points on is at most , where is the “reduction of modulo ” with respect to some proper regular model.

For example, one can deduce from this theorem that the only integers for which 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…

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

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

Yes, deg(D) is the total number of chips on the graph. I will clarify this in the post, thanks!

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?

Hi Tyler — Sorry for the delayed response. In your setup, let’s fix a model 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 on , and then you can set , where the sum is over all vertices v of G and 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 on the surface . For example, if you replace by , the associated divisor D gets modified by a single lending move at v. Does this make sense?

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.

Yes, exactly.

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

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.

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

I created a js implementation along with the editor after being inspired by the recent numberphile video.

duke.a-comics.ru/dollar/

Nice implementation of the dollar game!

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

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)

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

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.

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.

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?

Here is a working link: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=EA953C89FB0AD6693E2F2A10BFAC6FE2?doi=10.1.1.17.1725&rep=rep1&type=pdf

Pingback: The Dollar Game — Numberphile — Mvience

Pingback: Colorings and embeddings of graphs | Matt Baker's Math Blog

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?

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.

Pingback: Firing games and greedoid languages | Matt Baker's Math Blog