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 be a connected finite graph of genus , where . Our central object of study will be the notion of a break divisor on . Recall that a divisor on a graph is an assignment of an integer to each vertex of . The divisor is called effective if for all ; in this case, we often visualize by placing “chips” at . And the degree of is the sum of over all vertices , i.e., the total number of chips. By analogy with algebraic geometry, we write divisors on as formal sums , i.e., as elements of the free abelian group on .
A break divisor on is an effective divisor of degree such that for every connected subgraph of , the degree of restricted to is at least . In other words, there are total chips and each connected subgraph contains at least genus-of- of these chips. One surprising fact, proved in this paper (referred to henceforth as [ABKS]), is that the number of break divisors on is equal to the number of spanning trees of .
For example, if is the complete graph on vertices, then and an effective divisor on is a break divisor if and only if after relabeling the so that we have for all , with equality when . The total number of such divisors is (non-obviously!) equal to the Cayley number . For example, when the break divisors correspond to all permutations of the sequences and .
To see why the number of break divisors on is equal to the number of spanning trees of , we recall the notion of linear equivalence of divisors. Two divisors and are called linearly equivalent, denoted , if for some function , where . Equivalently, if and only if one can get from to by a sequence of borrowing and lending moves. Divisors of the form are called principal and have degree zero. The set of linear equivalence classes of divisors of degree is denoted . The group , which is also called the Jacobian group, sandpile group, or critical group of , acts simply and transitively on for each , i.e., is a –torsor. It is a fundamental fact (and a consequence of Riemann-Roch) that every divisor of degree at least is linearly equivalent to an effective divisor. The following refinement when is proved in [ABKS]:
Theorem 1 (An-Baker-Kuperberg-Shokrieh): Every degree divisor on is linearly equivalent to a unique break divisor. Therefore the set of break divisors on is canonically in bijection with .
In particular, since and have the same cardinality and the size of the latter is the number of spanning trees in (by Kirchhoff’s Matrix-Tree Theorem), it follows that the number of break divisors on is equal to the number of spanning trees of as claimed above. The above theorem can be rephrased as saying that the natural map from effective divisors of degree on to has a canonical section given by sending a divisor class to the unique break divisor in that class. (It is worth mentioning that the analogous assertion in algebraic geometry is false.)
Equivalent characterizations of break divisors
There are several equivalent ways to characterize break divisors on . One such characterization is in terms of the divisors associated to certain orientations of , which we now define. Let be an orientation of . We say that is -connected if there is a directed path from to for every vertex . The divisor associated to an orientation is , where denotes the number of incoming (with respect to ) edges at . The following is proved in [ABKS]:
Theorem 2: The following are equivalent for an effective divisor of degree on :
(1) is a break divisor.
(2) There exists a spanning tree and an enumeration of the edges in the complement of such that and is one of the two endpoints of for all .
(3) For every (or equivalently, for some ), for some -connected orientation of .
One can also define break divisors for metric graphs / tropical curves, and these have similar properties to break divisors on graphs. (In fact, the name “break divisor” comes from a paper of Mikhalkin-Zharkov where they were first introduced, in the context of tropical curves.). We will say more about this later…
Ellenberg’s question and the Bernardi process
Motivated by the equality of cardinalities between and the set of spanning trees of , together with the observation that the former has a distinguished identity element while the latter does not, Jordan Ellenberg asked in this Math Overflow post whether is naturally a torsor for . He actually asked the question in a more precise way, and a surprising answer to Ellenberg’s question was given in this beautiful paper by Chan, Church, and Grochow. My former student Yao Wang and I gave a different (but similar-sounding) answer to Ellenberg’s question in this paper. I will briefly summarize our results, which provide a highly nontrivial connection between Ellenberg’s question and break divisors.
A ribbon structure on a graph is a cyclic ordering of the edges around each vertex . A plane graph (i.e., a graph embedded in the Euclidean plane) has a natural ribbon structure given by orienting the edges around each vertex counterclockwise (say). Conversely, any ribbon structure determines a local embedding of into the plane, and globally it gives an embedding into a (canonically defined) compact oriented surface-without-boundary . A graph together with a ribbon structure is called a ribbon graph, and a ribbon graph is planar if the corresponding embedding surface is a sphere.
Given a ribbon graph , there is an algorithm due to Bernardi (although he didn’t phrase it in this way) which assigns to each spanning tree a corresponding break divisor . The assignment depends on first choosing a reference vertex and an edge incident to . Informally, the Bernardi process works as follows: starting at in the direction of , we take a stroll in which we walk along edges which belong to and we cut through edges which don’t belong to . Each time we either walk along some or cut through some , we figure out which edge to consider next using the cyclic ordering at the current vertex . In this way, we make a complete tour around , cutting through each edge twice and walking along each edge twice, once in each direction:
The first time we cut through each edge , we drop a chip at the corresponding vertex By the time we’ve finished our tour of , we will have dropped exactly chips on ; we call the resulting divisor . By condition (2) in Theorem 2 above, is a break divisor on .
Theorem 3 (Bernardi, Baker-Wang): The map defines a bijection from to .
Wang and I give a proof of Theorem 3 which is quite different from Bernardi’s. We show that one can construct an inverse to via the following algorithmic procedure. Given a break divisor on , and starting at in the direction of , we again begin strolling around the graph, building up a spanning tree as we go. We cut through an edge if removing that edge from the graph and subtracting a chip from at the current vertex gives a break divisor on the resulting (connected) graph ; in this case we replace by and by and continue. Otherwise, we walk along and add it to the spanning tree we’re building.
Since is canonically in bijection with , which is canonically a torsor for , the choice of provides us with a simply transitive action of the group on the set of spanning trees. Moreover, it is proved in [Baker-Wang] that, up to isomorphism of -torsors, this action is independent of the starting edge . Thus for each vertex there is a well-defined (up to isomorphism) simply transitive action of on .
Theorem 4 (Baker-Wang): The action is independent of if and only if the ribbon graph is planar.
Theorem 4 can be rephrased somewhat loosely as saying that the set of spanning trees of a graph is naturally a torsor for the Jacobian group of if and only if is planar. This provides a rather striking answer to Ellenberg’s question.
When the ribbon graph is planar, the canonical torsor structure on defined above comes from a natural bijection between and which can be described without mentioning the Bernardi process. This observation is due to my student Chi Ho Yuen (and is discussed in more detail in this paper, about which we will say more below). The bijection is as follows: given a spanning tree and an edge , there is an associated fundamental cycle, defined as the unique cycle contained in . Orient counterclockwise and consider the induced orientation on ; drop a chip at the tail end of this orientation. Doing this for each gives a break divisor , and the map is a bijection.
Break divisors on tropical curves and the ABKS decomposition
A metric graph, or tropical curve (we will use the terms interchangeably in this post), of genus is obtained from a finite graph of genus by assigning a positive real number to each edge and identifying with a line segment of length . Divisors on are allowed to be supported anywhere along , including points in the relative interior of (but must be supported at only finitely many points).
A principal divisor on a tropical curve is a divisor of the form for some tropical rational function , i.e., a continuous piecewise-linear function with everywhere integer slope. (The function is allowed to change slope at points in the interior of edges, but it can only change slope finitely many times.). By definition, we have , where is minus the sum of the outgoing slopes of in each direction emanating from .
We can define as in the discrete case, and each is again a torsor for the Jacobian group , but now is no longer a finite group but a real torus of dimension . We can also define break divisors on as in the discrete case: a break divisor on is an effective divisor of degree on such that the restriction of to every closed connected subgraph of has degree at least the genus of . It turns out once again (see [ABKS]) that there is a unique break divisor in every linear equivalence class in .
Moreover, a suitable analogue of Theorem 2 holds for tropical curves. For example, one has that is a break divisor on if and only if there exists a spanning tree of and an enumeration of such that and belongs to the closure of in for all . This fact allows us to define a canonical polyhedral decomposition of the real torus as follows. Let be the set of all divisors of the form as above, with in the closure of the connected component of , so that each is a -dimensional parallelepiped. Let be the image of in under the map sending a divisor to its linear equivalence class.
Theorem 5 (An-Baker-Kuperberg-Shokrieh): is the union of over all spanning trees of . Each is a polyhedral subset of , and the relative interiors of the various are disjoint.
For example, when is the metric graph corresponding to the following genus 2 graph (with all ):
the corresponding ABKS decomposition of is as follows:
There is a natural metric on with respect to which the volume of each cell is the product of the for , and the volume of itself is naturally related to the determinant of the Laplacian matrix of . One recovers in this way a canonical “volume-theoretic” proof of the (dual) weighted version of Kirchhoff’s Matrix-Tree Theorem (see [ABKS] for details).
When all edge lengths in are equal to 1, in which case we call the tropical curve the regular realization of , the vertices (zero-dimensional cells) of the ABKS decomposition of (which are precisely the lattice points in ) are naturally in bijection with the break divisors of , while the faces (top-dimensional cells) are in bijection with spanning trees of . One way to define a bijection between break divisors and spanning trees is to shift each cell in the ABKS decomposition by a small amount in the same direction ; after such a shift, each cell will contain exactly one lattice point, which corresponds to a break divisor . The resulting map gives what we call a geometric bijection between and .
In this paper, Chi Ho Yuen proves that for planar ribbon graphs, the natural action of on defined by the Bernardi process arises from a geometric bijection between and . This provides a connection (for planar graphs) between the Bernardi process and tropical geometry. Yuen proves conversely that non-planar graphs give non-geometric bijections, at least after subdividing each edge into two edges (which does not change the corresponding metric graph once one rescales the metric).
(1) In a future post I will describe another family of simply transitive actions (which are “geometric” in a slightly different sense) of on which, instead of fixing a ribbon structure on , rely on choosing an orientation for each simple cycle and simple cut in . This family of torsors, defined and studied in this paper, has the advantage of generalizing to regular matroids.
(2) In another future post I will describe some applications of break divisors to algebraic geometry. Specifically, break divisors can be used to understand Simpson compactified Jacobians in degree (recent work of Jifeng Shen), and they can also be used to give a simple geometric interpretation of the Zhang measure on a tropical curve.
(3) Mikhalkin and Zharkov define break divisors on a tropical curve in this paper as follows: an effective divisor of degree is a break divisor if and only if for sufficiently small , there are distinct tangent directions at such that removing the valence 2 points gives a connected and simply connected open subgraph of . Thus break divisors can be used to “break” all nontrivial cycles of . The Mikhalkin-Zharkov definition is easily seen to be equivalent to the definition in part (3) of Theorem 2 (adapted to tropical curves). Mikhalkin and Zharkov prove that every degree divisor on is equivalent to a unique such break divisor by a very different argument from the one in [ABKS] (they use tropical intersection theory).
(4) The simply transitive action of on considered by Chan, Church, and Grochow is defined using rotor-routing. As proved in [Baker-Wang], the rotor-routing torsor for a planar ribbon graph is isomorphic to the one defined using the Bernardi process. Thus for a plane graph (together with a fixed orientation of the plane), there seems to be a single canonical torsor structure on the set of spanning trees. (The theory described in Concluding Remark #1 gives yet another description of this same torsor.)
(5) If we fix a vertex , the set of -reduced divisors, defined in this post, is also a collection of “nice” representatives for elements of . While -reduced divisors are indispensable for Riemann-Roch theory, the advantage of break divisors is that they are completely canonical. One can give families of explicit combinatorial bijections between spanning trees and elements of using -reduced divisors instead of break divisors; see for example the Cori-LeBorgne algorithm described in this paper. Such bijections are not “geometric” in nature, however.
Pingback: The Geometry of Break Divisors | Matt Baker's Math Blog
Pingback: The circuit-cocircuit reversal system | Matt Baker's Math Blog