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$ .

For example, if $G=K_n$ is the complete graph on $n$ vertices, then $g=\binom{n-1}{2}$ and an effective divisor $D = \sum_{i=1}^n a_i (v_i)$ on $K_n$ is a break divisor if and only if after relabeling the $v_i$ so that $0 \leq a_1 \leq a_2 \leq \cdots \leq a_n$ we have $a_1 + \cdots + a_k \geq \binom{k-1}{2}$ for all $k=1,\ldots,n$ , with equality when $k=n$ . The total number of such divisors is (non-obviously!) equal to the Cayley number $n^{n-2}$ . For example, when $n=4$ the break divisors correspond to all permutations of the sequences $(0,1,1,1)$ and $(0,0,1,2)$ .

To see why the number of break divisors on $G$ is equal to the number of spanning trees of $G$ , we recall the notion of linear equivalence of divisors. Two divisors $D$ and $D'$ are called linearly equivalent, denoted $D \sim D'$ , if $D - D' = {\rm div}(f)$ for some function $f : V(G) \to {\mathbb Z}$ , where ${\rm div}(f) = \sum_{v \in V(G)} \sum_{e = vw \in E(G)} \left( f(v) - f(w) \right) (v)$ . Equivalently, $D \sim D'$ if and only if one can get from $D$ to $D'$ by a sequence of borrowing and lending moves. Divisors of the form ${\rm div}(f)$ are called principal and have degree zero. The set of linear equivalence classes of divisors of degree $d$ is denoted ${\rm Pic}^d(G)$ . The group ${\rm Pic}^0(G)$ , which is also called the Jacobian group, sandpile group, or critical group of $G$ , acts simply and transitively on ${\rm Pic}^d(G)$ for each $d$ , i.e., ${\rm Pic}^d(G)$ is a ${\rm Pic}^0(G)$ –torsor. It is a fundamental fact (and a consequence of Riemann-Roch) that every divisor of degree at least $g$ is linearly equivalent to an effective divisor. The following refinement when $d=g$ is proved in [ABKS]:

Theorem 1 (An-Baker-Kuperberg-Shokrieh): Every degree $g$ divisor on $G$ is linearly equivalent to a unique break divisor. Therefore the set ${\mathcal B}(G)$ of break divisors on $G$ is canonically in bijection with ${\rm Pic}^g(G)$ .

In particular, since ${\rm Pic}^g(G)$ and ${\rm Pic}^0(G)$ have the same cardinality and the size of the latter is the number of spanning trees in $G$ (by Kirchhoff’s Matrix-Tree Theorem), it follows that the number of break divisors on $G$ is equal to the number of spanning trees of $G$ as claimed above. The above theorem can be rephrased as saying that the natural map from effective divisors of degree $g$ on $G$ to ${\rm Pic}^g(G)$ 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 $G$ . One such characterization is in terms of the divisors associated to certain orientations of $G$ , which we now define. Let ${\mathcal O}$ be an orientation of $G$ . We say that ${\mathcal O}$ is $q$ -connected if there is a directed path from $q$ to $v$ for every vertex $v \neq q$ . The divisor associated to an orientation is ${\rm div}({\mathcal O}) := \sum_{v \in V(G)} \left( {\rm indeg}_{\mathcal O}(v) - 1 \right) (v)$ , where ${\rm indeg}_{\mathcal O}(v)$ denotes the number of incoming (with respect to ${\mathcal O}$ ) edges at $v$ . The following is proved in [ABKS]:

Theorem 2: The following are equivalent for an effective divisor $D$ of degree $g$ on $G$ :

(1) $D$ is a break divisor.

(2) There exists a spanning tree $T$ and an enumeration of the edges $e_1,\ldots,e_g$ in the complement of $T$ such that $D = (v_1) + \cdots + (v_g)$ and $v_i$ is one of the two endpoints of $e_i$ for all $i$ .

(3) For every $q \in V(G)$ (or equivalently, for some $q \in V(G)$ ), $D - (q) = {\rm div}({\mathcal O})$ for some $q$ -connected orientation ${\mathcal O}$ of $G$ .

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 ${\rm Pic}^0(G)$ and the set ${\mathcal T}(G)$ of spanning trees of $G$ , 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 ${\mathcal T}(G)$ is naturally a torsor for ${\rm Pic}^0(G)$ . 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 $G$ is a cyclic ordering of the edges around each vertex $v \in V(G)$ . 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 $G$ into the plane, and globally it gives an embedding into a (canonically defined) compact oriented surface-without-boundary $S$ . A graph together with a ribbon structure is called a ribbon graph, and a ribbon graph is planar if the corresponding embedding surface $S$ is a sphere.

Given a ribbon graph $G$ , there is an algorithm due to Bernardi (although he didn’t phrase it in this way) which assigns to each spanning tree $T$ a corresponding break divisor $D_T$ . The assignment $T \mapsto D_T$ depends on first choosing a reference vertex $v$ and an edge $e$ incident to $v$ . Informally, the Bernardi process works as follows: starting at $v$ in the direction of $e$ , we take a stroll in which we walk along edges which belong to $T$ and we cut through edges which don’t belong to $T$ . Each time we either walk along some $f \in T$ or cut through some $f \not\in T$ , we figure out which edge to consider next using the cyclic ordering at the current vertex $w$ . In this way, we make a complete tour around $T$ , cutting through each edge $f\not\in T$ twice and walking along each edge $f \in T$ twice, once in each direction:

The first time we cut through each edge $f \not\in T$ , we drop a chip at the corresponding vertex $w.$ By the time we’ve finished our tour of $T$ , we will have dropped exactly $g$ chips on $G$ ; we call the resulting divisor $D_T$ . By condition (2) in Theorem 2 above, $D_T$ is a break divisor on $G$ .

Theorem 3 (Bernardi, Baker-Wang): The map $T \mapsto D_T$ defines a bijection $\beta_{v,e}$ from ${\mathcal T}(G)$ to ${\mathcal B}(G)$ .

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 $\beta_{v,e}$ via the following algorithmic procedure. Given a break divisor $D$ on $G$ , and starting at $v$ in the direction of $e$ , we again begin strolling around the graph, building up a spanning tree $T_D$ as we go. We cut through an edge $e'$ if removing that edge from the graph and subtracting a chip from $D$ at the current vertex gives a break divisor $D'$ on the resulting (connected) graph $G'$ ; in this case we replace $G$ by $G'$ and $D$ by $D'$ and continue. Otherwise, we walk along $e'$ and add it to the spanning tree we’re building.

Since ${\mathcal B}(G)$ is canonically in bijection with ${\rm Pic}^g(G)$ , which is canonically a torsor for ${\rm Pic}^0(G)$ , the choice of $(v,e)$ provides us with a simply transitive action of the group ${\rm Pic}^0(G)$ on the set ${\mathcal T}(G)$ of spanning trees. Moreover, it is proved in [Baker-Wang] that, up to isomorphism of ${\rm Pic}^0(G)$ -torsors, this action is independent of the starting edge $e$ . Thus for each vertex $v \in V(G)$ there is a well-defined (up to isomorphism) simply transitive action $\beta_v$ of ${\rm Pic}^0(G)$ on ${\mathcal T}(G)$ .

Theorem 4 (Baker-Wang): The action $\beta_v$ is independent of $v \in V(G)$ if and only if the ribbon graph $G$ is planar.

Theorem 4 can be rephrased somewhat loosely as saying that the set of spanning trees of a graph $G$ is naturally a torsor for the Jacobian group of $G$ if and only if $G$ is planar. This provides a rather striking answer to Ellenberg’s question.

When the ribbon graph $G$ is planar, the canonical torsor structure on ${\mathcal T}(G)$ defined above comes from a natural bijection between ${\mathcal T}(G)$ and ${\mathcal B}(G)$ 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 $T$ and an edge $e \not\in T$ , there is an associated fundamental cycle, defined as the unique cycle $C_{T,e}$ contained in $T \cup \{ e \}$ . Orient $C_{T,e}$ counterclockwise and consider the induced orientation on $e$ ; drop a chip at the tail end of this orientation. Doing this for each $e \not\in T$ gives a break divisor $D_T$ , and the map $T \mapsto D_T$ 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), $\Gamma$ of genus $g$ is obtained from a finite graph $G$ of genus $g$ by assigning a positive real number $\ell(e)$ to each edge $e \in G$ and identifying $e$ with a line segment of length $\ell(e)$ . Divisors on $\Gamma$ are allowed to be supported anywhere along $e$ , including points in the relative interior of $e$ (but must be supported at only finitely many points).

A principal divisor on a tropical curve $\Gamma$ is a divisor of the form ${\rm div}(f)$ for some tropical rational function $f$ , i.e., a continuous piecewise-linear function $f : \Gamma \to {\mathbb R}$ with everywhere integer slope. (The function $f$ 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 ${\rm div}(f) = \sum_{p \in \Gamma} {\rm ord}_p(f) (p)$ , where ${\rm ord}_p(f)$ is minus the sum of the outgoing slopes of $f$ in each direction emanating from $p$ .

We can define ${\rm Pic}^d(\Gamma)$ as in the discrete case, and each ${\rm Pic}^d(\Gamma)$ is again a torsor for the Jacobian group ${\rm Pic}^0(\Gamma)$ , but now ${\rm Pic}^0(\Gamma)$ is no longer a finite group but a real torus of dimension $g$ . We can also define break divisors on $\Gamma$ as in the discrete case: a break divisor on $\Gamma$ is an effective divisor $D$ of degree $g$ on $\Gamma$ such that the restriction of $D$ to every closed connected subgraph $\Gamma'$ of $\Gamma$ has degree at least the genus of $\Gamma'$ . It turns out once again (see [ABKS]) that there is a unique break divisor in every linear equivalence class in ${\rm Pic}^g(\Gamma)$ .

Moreover, a suitable analogue of Theorem 2 holds for tropical curves. For example, one has that $D$ is a break divisor on $\Gamma$ if and only if there exists a spanning tree $T$ of $G$ and an enumeration $e^\circ_1,\ldots,e^\circ_g$ of $\Gamma \backslash T$ such that $D = (p_1) + \cdots + (p_g)$ and $p_i$ belongs to the closure $e_i$ of $e^\circ_i$ in $\Gamma$ for all $i$ . This fact allows us to define a canonical polyhedral decomposition of the real torus ${\rm Pic}^g(\Gamma)$ as follows. Let $B_T$ be the set of all divisors of the form $(p_1) + \cdots + (p_g)$ as above, with $p_i$ in the closure of the $i^{\rm th}$ connected component of $\Gamma \backslash T$ , so that each $B_T$ is a $g$ -dimensional parallelepiped. Let $C_T$ be the image of $B_T$ in ${\rm Pic}^g(\Gamma)$ under the map sending a divisor $D$ to its linear equivalence class.

Theorem 5 (An-Baker-Kuperberg-Shokrieh): ${\rm Pic}^g(\Gamma)$ is the union of $C_T$ over all spanning trees $T$ of $G$ . Each $C_T$ is a polyhedral subset of ${\rm Pic}^g(\Gamma)$ , and the relative interiors of the various $C_T$ are disjoint.

For example, when $\Gamma$ is the metric graph corresponding to the following genus 2 graph $G$ (with all $\ell(e) = 1$ ):

the corresponding ABKS decomposition of ${\rm Pic}^2(\Gamma)$ is as follows:

There is a natural metric on ${\rm Pic}^g(\Gamma)$ with respect to which the volume of each cell $C_T$ is the product of the $\ell(e)$ for $e \not\in T$ , and the volume of ${\rm Pic}^g(\Gamma)$ itself is naturally related to the determinant of the Laplacian matrix of $G$ . 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).

Geometric bijections

When all edge lengths $\ell(e)$ in $\Gamma$ are equal to 1, in which case we call the tropical curve $\Gamma$ the regular realization of $G$ , the vertices (zero-dimensional cells) of the ABKS decomposition of ${\rm Pic}^g(\Gamma)$ (which are precisely the lattice points in ${\rm Pic}^g(\Gamma)$ ) are naturally in bijection with the break divisors of $G$ , while the faces (top-dimensional cells) are in bijection with spanning trees of $G$ . 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 ${\vec{v}}$ ; after such a shift, each cell $C_T$ will contain exactly one lattice point, which corresponds to a break divisor $D'_T$ . The resulting map $C_T \mapsto D'_T$ gives what we call a geometric bijection between ${\mathcal T}(G)$ and ${\mathcal B}(G)$ .

In this paper, Chi Ho Yuen proves that for planar ribbon graphs, the natural action of ${\rm Pic}^0(G)$ on ${\mathcal T}(G)$ defined by the Bernardi process arises from a geometric bijection between ${\mathcal T}(G)$ and ${\mathcal B}(G)$ . 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).

Concluding remarks

(1) In a future post I will describe another family of simply transitive actions (which are “geometric” in a slightly different sense) of ${\rm Pic}^0(G)$ on ${\mathcal T}(G)$ which, instead of fixing a ribbon structure on $G$ , rely on choosing an orientation for each simple cycle and simple cut in $G$ . 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 $g$ (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 $\Gamma$ in this paper as follows: an effective divisor $D=(p_1)+\cdots + (p_g)$ of degree $g$ is a break divisor if and only if for sufficiently small $\epsilon > 0$ , there are distinct tangent directions $\vec{v}_i$ at $p_i$ such that removing the $g$ valence 2 points $p_i + \epsilon \vec{v}_i$ gives a connected and simply connected open subgraph of $\Gamma$ . Thus break divisors can be used to “break” all nontrivial cycles of $\Gamma$ . 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 $g$ divisor on $\Gamma$ 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 ${\rm Pic}^0(G)$ on ${\mathcal T}(G)$ 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 $G$ is isomorphic to the one defined using the Bernardi process. Thus for a plane graph $G$ (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 $q \in V(G)$ , the set of $q$ -reduced divisors, defined in this post, is also a collection of “nice” representatives for elements of ${\rm Pic}^d(G)$ . While $q$ -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 ${\rm Pic}^0(G)$ using $q$ -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.

2 thoughts on “The Combinatorics of Break Divisors”

Pingback: The Geometry of Break Divisors | Matt Baker's Math Blog
Pingback: The circuit-cocircuit reversal system | Matt Baker's Math Blog

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

The Combinatorics of Break Divisors

2 thoughts on “The Combinatorics of Break Divisors”

Leave a Reply Cancel reply

Share this:

Like this:

Related

2 thoughts on “The Combinatorics of Break Divisors”

Leave a Reply Cancel reply