Monthly Archives: October 2013

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! Continue reading →