One of the deepest and most important results in number theory is the Mordell Conjecture, proved by Faltings (and independently by Vojta shortly thereafter). It asserts that if is an algebraic curve of genus at least 2, then the set of rational points on is finite. At present, we do not know any effective algorithm (in theory or in practice) to compute the finite set . The techniques of Faltings and Vojta lead in principle to an upper bound for the number of rational points on , but the bound obtained is far from sharp and is difficult to write down explicitly. In his influential paper Effective Chabauty, Robert Coleman combined his theory of p-adic integration with an old idea of Chabauty and showed that it led to a simple explicit upper bound for the size of provided that the Mordell-Weil rank of the Jacobian of is not too large. (For a memorial tribute to Coleman, who passed away on March 24, 2014, see this blog post.)
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! Continue reading