The Combinatorics of Break Divisors

I recently gave three lectures at Yale University for the Hahn Lectures in Mathematics.  The unifying theme of my talks was the notion of break divisor, a fascinating combinatorial concept related to the Riemann-Roch theorem for graphs.  Some applications of break divisors to algebraic geometry will be discussed in a follow-up post.

Break divisors on graphs

Let G be a connected finite graph of genus g = g(G), where g := |E(G)| - |V(G)| + 1.  Our central object of study will be the notion of a break divisor on G.  Recall that a divisor D on a graph G is an assignment of an integer D(v) to each vertex v of G.   The divisor D is called effective if D(v) \geq 0 for all v; in this case, we often visualize D by placing D(v) “chips” at v.  And the degree of D is the sum of D(v) over all vertices v, i.e., the total number of chips.  By analogy with algebraic geometry, we write divisors on G as formal sums D = \sum_{v \in V(G)} D(v) (v), i.e., as elements of the free abelian group on V(G).

A break divisor on G is an effective divisor D of degree g such that for every connected subgraph H of G, the degree of D restricted to H is at least g(H).  In other words, there are g(G) total chips and each connected subgraph H contains at least genus-of-H of these chips.  One surprising fact, proved in this paper (referred to henceforth as [ABKS]), is that the number of break divisors on G is equal to the number of spanning trees of G. Continue reading

p-adic Numbers and Dissections of Squares into Triangles

My thesis advisor Robert Coleman passed away two years ago today (see this remembrance on my blog).  One of the things I learned from Robert is that p-adic numbers have many unexpected applications (see, for example, this blog post).  Today I want to share one of my favorite surprising applications of p-adic numbers, to a simple problem in Euclidean geometry. Continue reading

Matroids over Hyperfields, Part II

In Part I of this post, we defined hyperrings and hyperfields, gave some key examples, and introduced matroids over (doubly distributive) hyperfields in terms of Grassman-Plücker functions.  If E=\{ 1,\ldots,m \} is a finite set and K is a field, we saw that a K-matroid on E is the same thing as a linear subspace of K^m, and if {\mathbb K} is the Krasner hyperfield then a {\mathbb K}-matroid on E is the same thing as a matroid in the usual sense.  Matroids over the hyperfield {\mathbb S} of signs are the same thing as oriented matroids, and matroids over the tropical hyperfield {\mathbb T} are the same thing as valuated matroids.  In this post we will give some “cryptomorphic” axiomatizations of matroids over hyperfields, discuss duality theory, and then discuss the category of hyperrings in a bit more detail. Continue reading

Matroids over Hyperfields, Part I

In this post and its sequel, I’d like to explain a new perspective on matroid theory which was introduced in this recent preprint which I wrote with Nathan Bowler.  The main observation is that by working with algebraic structures called hyperfields, in which addition is allowed to be multi-valued, linear subspaces, matroids, valuated matroids, and oriented matroids become special cases of a single general concept.  In the process of explaining this observation, I also hope to advertise how natural hyperfields are, for example in the context of tropical geometry.


The notion of an algebraic structure in which addition is allowed to be multi-valued goes back to Frédéric Marty, who introduced hypergroups in 1934.  Later on, in the mid-1950’s, Marc Krasner developed the theory of hyperrings and hyperfields in the context of approximating non-Archimedean fields, and in the 1990’s Murray Marshall explored connections to the theory of real spectra and spaces of orderings.  For the most part, however, the theory of hyperstructures was largely ignored by the mathematical community at large until Connes and Consani started advocating its potential utility in connection with F_1-geometry and the Riemann hypothesis.  There now seems to be a reappraisal of sorts going on within the math community of the “bias” against multi-valued operations.  Continue reading

A Celebration of Independence

Yesterday marked the second anniversary of my blog, and today is the 239th birthday of the U.S. In celebration of Independence Day, I want to explain what matroids are. Matroids were invented by Hassler Whitney (and independently by Takeo Nakasawa) to abstract the notion of linear independence from vector spaces to a much more general setting that includes acyclicity in graphs. Other pioneering early work on matroids was done by Garrett Birkhoff and Saunders MacLane. Matroid theory is a rich subject about which we will only scratch the surface here. In particular, there are many different (“cryptomorphic“) ways to present the matroid axioms which all turn out to be (non-obviously) equivalent to one another. We will focus on just a couple of ways of looking at matroids, emphasizing their connections to tropical geometry. Continue reading

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

The Jacobian of the skeleton and the skeleton of the Jacobian

My new Georgia Tech colleague Joe Rabinoff and I recently posted this paper to the arXiv, entitled The skeleton of the Jacobian, the Jacobian of the skeleton, and lifting meromorphic functions from tropical to algebraic curves.  In this post I will attempt to give some context and background for that paper.

Suppose X is an algebraic variety over a complete non-Archimedean field K.  For simplicity of exposition, I will assume throughout that K is algebraically closed and that the value group \Lambda = {\rm val} (K^\times) is nontrivial.  The set of points X(K) possesses a natural (Hausdorff) analytic topology, but X(K) is totally disconnected and not even locally compact in this topology.  This is bad for all sorts of reasons.  Over the years there have been many attempts at “fixing” this problem, beginning with the Tate-Grothendieck theory of rigid analytic spaces.  One of the most successful and elegant solutions to the problem is Berkovich’s theory of non-Archimedean analytic spaces.  One can associate to X, in a natural and functorial way, an analytic space X^{\rm an} which contains X(K) as a dense subspace but has much nicer topological properties.  For example, X^{\rm an} is a locally compact Hausdorff space which is locally contractible, and is arcwise connected if X is connected.  As in the theory of complex analytic spaces, X^{\rm an} is compact if and only if X^{\rm an} is proper.  For much more information about Berkovich analytic spaces, see for example these course notes of mine.

One of the nice features of Berkovich’s theory (established in full generality only very recently, by Hrushovski and Loeser) is that the space X^{\rm an} always admits a deformation retraction onto a finite polyhedral complex \Sigma.  In general, there is no canonical choice for \Sigma.  However, in certain special cases there is, e.g. when X is a curve of positive genus or X is an abelian variety.  (More generally, the existence of canonical skeleta is closely tied in with the Minimal Model Program in birational algebraic geometry, see for example this recent paper of Mustata and Nicaise.)  For the rest of this post, I will focus on the special cases of curves and abelian varieties. Continue reading