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.
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…