# Firing games and greedoid languages

In an earlier post, I described the dollar game played on a finite graph $G$, and mentioned (for the “borrowing binge variant”) that the total number of borrowing moves required to win the game is independent of which borrowing moves you do in which order. A similar phenomenon occurs for the pentagon game described in this post.

In this post, I’ll first present a simple general theorem due to Mikkel Thorup which implies both of these facts (and also applies to many other ‘chip firing games’ in the literature). Then, following Anders Björner, Laszlo Lovasz, and Peter Shor, I’ll explain how to place such results into the context of greedoid languages, which have interesting connections to matroids, Coxeter groups, and other much-studied mathematical objects.

# Colorings and embeddings of graphs

My previous post was about the mathematician John Conway, who died recently from COVID-19. This post is a tribute to my Georgia Tech School of Mathematics colleague Robin Thomas, who passed away on March 26th at the age of 57 following a long struggle with ALS. Robin was a good friend, an invaluable member of the Georgia Tech community, and a celebrated mathematician. After some brief personal remarks, I’ll discuss two of Robin’s most famous theorems (both joint with Robertson and Seymour) and describe the interplay between these results and two of the theorems I mentioned in my post about John Conway.

# Some Mathematical Gems from John Conway

John Horton Conway died on April 11, 2020, at the age of 82, from complications related to COVID-19. See this obituary from Princeton University for an overview of Conway’s life and contributions to mathematics. Many readers of this blog will already be familiar with the Game of Life, surreal numbers, the Doomsday algorithm, monstrous moonshine, Sprouts, and the 15 theorem, to name just a few of Conway’s contributions to mathematics. In any case, much has already been written about all of these topics and I cannot do justice to them in a short blog post like this. So instead, I’ll focus on describing a handful of Conway’s somewhat lesser-known mathematical gems.

# The Circuit-Cocircuit Reversal System and Torsor Structures on Spanning Trees

The Jacobian of a finite graph $G$ is a finite abelian group whose cardinality is equal to the number of spanning trees of $G$.  In this earlier post, I discussed a family of combinatorial bijections between elements of ${\rm Jac}(G)$ and the set ${\mathcal T}(G)$ of spanning trees of $G$.  I also discussed the fact that for plane graphs, these Bernardi bijections come from a natural simply transitive action of ${\rm Jac}(G)$ on ${\mathcal T}(G)$ (or, more precisely, a natural isomorphism class of such actions).

In the present post, I’d like to discuss a different family of simply transitive actions of ${\rm Jac}(G)$ on ${\mathcal T}(G)$ discovered by myself, Spencer Backman (a former student of mine), and Chi Ho Yuen (a current student of mine).  One virtue of our construction is that it generalizes in a natural way from graphs to regular matroids.  (We will mostly stick to the graphical case in this post, but will insert some comments about extensions to regular and/or oriented matroids.  A regular matroid can be thought of, rather imprecisely, as the smallest natural class of objects which contain graphs and admit a duality theory generalizing duality for planar graphs. Regular matroids are special cases of the more general concept of oriented matroids.)

One of the main new ideas in [BBY] (as we will henceforth refer to our paper) is to use the torsor ${\rm Pic}^{g-1}(G)$ as an intermediate object rather than ${\rm Pic}^{g}(G)$.  The latter is canonically isomorphic (as a ${\rm Jac}(G)$-torsor) to the set of break divisors on $G$; the former is isomorphic to the circuit-cocircuit reversal system, which we now introduce.

# The Geometry of Break Divisors

I’d like to continue this discussion of break divisors on graphs & tropical curves by describing an interesting connection to algebraic geometry.  In this post, I’ll explain a beautiful connection to the theory of compactified Jacobians discovered by Tif Shen, a recent Ph.D. student of Sam Payne at Yale. Continue reading

# 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

# 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

# Effective Chabauty

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 $X / {\mathbf Q}$ is an algebraic curve of genus at least 2, then the set $X({\mathbf Q})$ of rational points on $X$ is finite. At present, we do not know any effective algorithm (in theory or in practice) to compute the finite set $X({\mathbf Q})$. The techniques of Faltings and Vojta lead in principle to an upper bound for the number of rational points on $X$, 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 $X({\mathbf Q})$ provided that the Mordell-Weil rank of the Jacobian of $X$ is not too large.  (For a memorial tribute to Coleman, who passed away on March 24, 2014, see this blog post.)

# The Pentagon Problem

In this post I’ll talk about another favorite recreational math puzzle, the (in)famous “Pentagon Problem”.  First, though, I wanted to provide a solution to the Ghost Bugs problem from my last blog post.  The puzzle is the following:

You are given four lines in a plane in general position (no two parallel, no three intersecting in a common point). On each line a ghost bug crawls at some constant velocity (possibly different for each bug). Being ghosts, if two bugs happen to cross paths they just continue crawling through each other uninterrupted.  Suppose that five of the possible six meetings actually happen. Prove that the sixth does as well.

Here is the promised solution.  The idea (like in Einstein’s theory of general relativity) is to add an extra dimension corresponding to time.  We thus lift the problem out of the page and replace the four lines by the graph of the bugs’ positions as a function of time.  Since each bug travels at a constant speed, each of the four resulting graphs $g_i$ is a straight line.  By construction, two lines $g_i$ and $g_j$ intersect if and only if the corresponding bugs cross paths.

Suppose that every pair of bugs cross paths except possibly for bugs 3 and 4.  Then the lines $g_1, g_2, g_3$ each intersect one another (in distinct points) and therefore they lie in a common plane.  Since line $g_4$ intersects lines $g_1$ and $g_2$ in distinct points, it must lie in the same plane.  The line $g_4$ cannot be parallel to $g_3$, since their projections to the page (corresponding to forgetting the time dimension) intersect.  Thus $g_3$ and $g_4$ must intersect, which means that bugs 3 and 4 do indeed cross paths.

Cool, huh?  As I mentioned in my last post, I can still vividly remember how I felt in the AHA! moment when I discovered this solution more than 15 years ago.

# Riemann-Roch theory for graph orientations

In this post, I’d like to sketch some of the interesting results contained in my Ph.D. student Spencer Backman’s new paper “Riemann-Roch theory for graph orientations”.

First, a bit of background.  In a 2007 paper, Emeric Gioan introduced the cycle-cocycle reversal system on a (finite, connected, unoriented) graph G, which is a certain natural equivalence relation on the set of orientations of G.  Recall that an orientation of G is the choice of a direction for each edge.  A cycle flip on an orientation ${\mathcal O}$ consists of reversing all the edges in a directed cycle in ${\mathcal O}$.  Similarly, a cocycle flip consists of reversing all the edges in a directed cocycle in ${\mathcal O}$, where a directed cocycle (also called a directed cut) is the collection of all oriented edges connecting a subset of vertices of G to its complement.  The cycle-cocycle reversal system is the equivalence relation on the set of orientations of G generated by all cycle and cocycle flips.  In his paper, Gioan proves (via a deletion-contraction recursion) the surprising fact that the number of equivalence classes equals the number of spanning trees in G.  A bijective proof of this result was subsequently obtained by Bernardi. Continue reading

# Reduced divisors and Riemann-Roch for Graphs

In an earlier post, I described a graph-theoretic analogue of the Riemann-Roch theorem and some of its applications.  In this post, I’d like to discuss a proof of that theorem which is a bit more streamlined than the one which Norine and I gave in our original paper [BN].  Like our original proof, the one we’ll give here is based on the concept of reduced divisors. 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.