Chip-Firing on Metric Graphs: The Abel-Jacobi Map

Suppose {G} is a finite, connected, edge-weighted graph, i.e. there is an associated weight function {w: E(G) \rightarrow \mathbb{R}^{>0}}. One can make {G} into a metric space {\Gamma(G)} by identifying each edge {e\in E(G)} with a closed line segment {L_e} of length {w(e)}, setting

\displaystyle \Gamma = \bigcup_{e\in E(G)} L_e

and declaring {d(x,y)} to be the length of the shortest path between {x} and {y} when traveling along the edges of {G}. On the space {\mathcal{G}} of finite, edge-weighted graphs, there is the equivalence relation {G\sim G'} if {\Gamma(G)} and {\Gamma(G')} are isometric. A metric graph {\Gamma} is the unique (up to isometry) metric space associated with an equivalence class in {\mathcal{G}/\sim}, and any graph in the equivalence class is called a model for {\Gamma}.

We begin with {\mathcal{M}(\Gamma)}, the group (under pointwise addition) of continuous, piecewise linear functions {\Gamma \rightarrow \mathbb{R}} for which every linear piece has integer slope. This is a linearized analogue of the space of meromorphic functions on a Riemann surface, over which divisor theory is classically developed. We denote by {\text{Div}(\Gamma)} the free abelian group on {\Gamma}, i.e.

\displaystyle \text{Div}(\Gamma) := \left\{D =\sum_{p\in \Gamma} a_p (p) \, : \, a_p \in \mathbb{Z} \text{ for all } p \text{ and } a_p = 0 \text{ for almost all } p \right\}

In other words, {\text{Div}(\Gamma)} is the group of integer-valued functions on {\Gamma} having finite support. With this interpretation, we introduce the notation {D(p) := a_p} for a divisor {D \in \text{Div}(\Gamma)}.

There is a homomorphism {\text{deg} : \text{Div}(\gamma) \rightarrow \mathbb{Z}} given by {\sum a_p (p) \mapsto \sum a_p}, and {\text{deg}(D)} is called the degree of {D}. For any {d\in \mathbb{Z}}, we denote by {\text{Div}^{d} (\Gamma)} the set of divisors with degree {d}. Only when {d = 0} does {\text{Div}^{d} (\Gamma)} form a subgroup of {\text{Div}(\Gamma)}, and {\text{Div}^{0} (\Gamma)} is the kernel of {\text{deg}}.

With each {f\in \mathcal{M}(\Gamma)}, there is an associated divisor {\Delta(f)}, which records information on the “zeros” and “poles” of {f}. Namely, for each {p\in \Gamma}, we set {\text{ord}_p (f)} to be the sum of the slopes of {f} in all directions of the graph emanating from {p}. Then we define the principal divisor {\Delta(f)} as

\displaystyle \Delta(f) := \sum_{p\in \Gamma} \text{ord}_p (f) (p)

The principal divisors form a subgroup {\text{Prin}(\Gamma)}, and one observes {\deg(\Delta(f)) = 0} for every {f \in \text{Prin}(\Gamma)}, so that {\text{Prin}(\Gamma) \subseteq \text{Div}^{0} (\Gamma)}. This begs to form the quotient

\displaystyle \text{Pic}^{0} (\Gamma) := \text{Div}^{0} (\Gamma) / \text{Prin}(\Gamma)

which is called the Picard group of {\Gamma}. More generally, two divisors {D}, {D' \in \text{Div}^{d} (\Gamma)} are linearly equivalent, denoted {D\sim D'}, if {D - D' \in \text{Prin}(\Gamma)}, and one can form the sets {\text{Pic}^{d} (\Gamma) := \text{Div}^d (\Gamma) / \sim}.

There is a combinatorial/dynamical interpretation of linear equivalence. Given a divisor {D} on {\Gamma}, one can interpret {D(p)} as the number of dollars person {p} has (if {D(p) < 0}, then person {p} is in debt). For any star-shaped subset {X \subset \Gamma} and sufficiently small {\epsilon > 0}, there is a function {f_{X, \epsilon} \in \mathcal{M}(\Gamma)} taking value 0 on {X}, taking value {\epsilon} outside the {\epsilon}-neighborhood of {X}, and with slope 1 along each outgoing direction from {X}. Then {D \sim D + \Delta(f_{X,\epsilon})}, and this equivalence has the effect of each person on the boundary of {X} giving one dollar to the individual situated exactly distance {\epsilon} away. Every element of {\mathcal{M}(\Gamma)} may be written as a finite {\mathbb{Z}}-linear combination of {f_{X,\epsilon}}‘s, so two divisors are linearly equivalent precisely when connected by a sequence of these “chip-firing” moves.

In terms of the chip-firing game, {\text{Pic}^{0} (\Gamma)} is the space of inequivalent degree 0 wealth distributions on {\Gamma}. We would like to understand the structure of this space, both algebraically and geometrically. As it turns out, one can learn quite a bit about {\text{Pic}^{0} (\Gamma)} through the integer homology group {H_1 (\Gamma, \mathbb{Z})}.

Recall that {H_1 (\Gamma, \mathbb{Z})} is constructed as follows. Fix a model {G} for {\Gamma}, fix an orientation of {G}, fix a spanning tree {T} of {G}, and fix a base vertex {q\in V(G)}. Then, we denote by {A} the {\mathbb{R}}-vector space with basis {E(G) = \{e_1, \cdots, e_n\}}, and by {\text{P}} the {\mathbb{R}}-vector space with basis {V(G)}. The boundary map {\partial : E(G) \rightarrow P} given by {\partial(v\rightarrow w) = w-v} extends linearly to a map {A\rightarrow P} of vector spaces. One defines the real homology {H_1 (\Gamma, \mathbb{R})} to be the kernel of {\partial: A \rightarrow P}. Given the choices we have made, there is a canonical basis for {H_1 (\Gamma, \mathbb{R})}, consisting of simple cycles. For every {e\in E(G) \setminus E(T)}, there is a unique cycle beginning and ending at {q} that traverses no edges other than {e} and those in {T}. Recording each of these cycles as a sum of directed edges gives the aforementioned basis. Then {H_1 (\Gamma, \mathbb{Z})} is defined to be the free abelian group on this canonical basis, i.e. the associated integer lattice inside {H_1 (\Gamma, \mathbb{R})}.

Screen Shot 2015-06-22 at 10.24.32 PM

The Abel-Jacobi theorem states there is an isomorphism

\displaystyle \text{Pic}^{0}(\Gamma) \stackrel{\Phi}{\cong} H_1 (\Gamma, \mathbb{R}) / H_1 (\Gamma, \mathbb{Z})

We will not prove this fact, as it is rather difficult, but we will show how this isomorphism gives rise to interesting geometric features. One defines the Abel-Jacobi map {\varphi_q : \Gamma \rightarrow \text{Pic}^{0} (\Gamma)} via

\displaystyle p \mapsto [(p) - (q)]

By the isomorphism above, {\varphi_q} descends to a map {\tilde{\varphi}_{q}} from {\Gamma} into the {g}-dimensional torus

\displaystyle H_1 (\Gamma, \mathbb{R})/H_1 (\Gamma, \mathbb{Z}) \cong \mathbb{R}^g / \mathbb{Z}^g \cong (S^1)^{g}

where {g = |E(G)| - |V(G)| + 1} is the genus of {G}. This {\tilde{\varphi}_q} can be described in very geometric terms: it essentially draws a skeletonized version of {G} on the torus {(S^1)^g}.

Screen Shot 2015-06-22 at 10.21.13 PM

To specify the map {\tilde{\varphi}_q}, we will need to equip the ambient edge space {A} with an inner product given by

\displaystyle \langle e_i, e_j \rangle = \left\{\begin{array}{lr} 0 & : i\neq j\\ w(e_i) & : i=j \end{array} \right.

This allows us to talk about orthogonality of vectors in {A}, and in particular, define an orthogonal projection {\pi : A \rightarrow H_1 (\Gamma, \mathbb{R})}. A line segment in {H_1 (\Gamma, \mathbb{R})} can be specified by providing a vector and a base point onto which the tail of the vector should be translated. Accordingly, let {(v,p)} denote the line segment in {H_1 (\Gamma, \mathbb{R})} obtained by translating vector {v} to {p}. We describe the image of {\tilde{\varphi}_q} by constructing the map inductively. Assume in the basis {\{e_1, \cdots, e_n\}} the edges are ordered such that for every {2\le j \le n}, the edge {e_j} shares a vertex with some {e_i} having {i<j}. Furthermore, assume the tail of {e_1} is {q}. Begin by identifying {e_1} with the segment {(\pi(e_1), 0)} (so that {\tilde{\varphi}_q} is defined on {e_1}). Now, if {e_j} for {j\ge 2} shares a vertex {x} with {e_i}, where {i<j}, we identify {e_j} with either the segment {(\pi(e_j), \tilde{\varphi}_q (x))} or the segment {(\pi(e_j), \tilde{\varphi}_q (x) - \pi(e_j))}, depending on if {x} is the tail of {e_j} or the head of {e_j}, respectively. Once this process is complete, the entire image of {\tilde{\varphi}_q} is contained in a unique fundamental domain of the lattice {H_1(\Gamma, \mathbb{Z})}, hence {\tilde{\varphi}_q} actually gives a map {\Gamma \rightarrow H_1 (\Gamma, \mathbb{R})/ H_1 (\Gamma, \mathbb{Z})}.

Screen Shot 2015-06-22 at 10.25.11 PM

How much information does {\tilde{\varphi}_q} preserve? The only edges mapped into {H_1 (\Gamma, \mathbb{R})} non-injectively are those which orthogonally project to {0 \in H_1 (\Gamma, \mathbb{R})}, i.e. those edges inhabiting the orthogonal complement of {H_1 (\Gamma, \mathbb{R})}. There is a nice characterization of this space when {w(e_i) = 1} for all {1\le i \le n}. Recall that a cut of {G} is any disjoint partition {V(G) = P \cup Q}, and any cut determines a cut set, consisting of the edges connecting a vertex in {P} to a vertex in {Q}. For each cut set {\{e_{i_1}, \cdots, e_{i_k}\}}, there is an associated cut vector in {A} encoding that set, namely {\sum_{j=1}^{k} \omega(j) e_{i_j}}. where {\omega(j) = 1} if {e_{i_j}} is oriented to flow from {P} to {Q} and {\omega(j) = -1} if {e_{i_j}} is oriented to flow from {Q} to {P}. We claim the cut space

\displaystyle C:= \text{span}\left( \text{all cut vectors} \right)

is precisely the orthogonal complement of the cycle space {H_1 (\Gamma, \mathbb{R})}.

To prove this, we first note that any cut vector is orthogonal to any cycle vector. Suppose {y \in H_1 (\Gamma, \mathbb{R})} represents a simple cycle (a cycle that traverses no edge twice) and {u = \sum_{j=1}^{k} \omega(j) e_{i_j} } is a cut vector. Let {\nu(j) = 1} if {y} traverses {e_{i_j}} along its orientation, let {\nu(j)=-1} if {y} traverses {e_{i_j}} against its orientation, and let {\nu(j) = 0} if {y} does not traverse {e_{i_j}}. Then

\displaystyle \langle y, u \rangle = \sum_{j=1}^{k} \nu(j) \omega(j)

\displaystyle = [\text{number of times } y \text{ goes } P \rightarrow Q] - [\text{number of times } y \text{ goes } Q \rightarrow P] = 0

But simple cycles form a basis for {H_1 (\Gamma, \mathbb{R})}, so {C \subseteq H_1 (\Gamma, \mathbb{R})^{\perp}}. Since {H_1 (\Gamma, \mathbb{R})^{\perp}} has dimension {|E(G)| - g = |V(G)| - 1}, to complete the argument it will suffice to exhibit {|V(G)| - 1} linearly independent vectors in {C}. Fix an ordering {\{v_1, \cdots, v_m\}} of the vertices, and set {A_j = \{v_1, \cdots, v_j\}}. Then for each {1\le j \le m-1}, the partition {V(G) = A_j \cup (V(G) \setminus A_j)} is a cut, with a corresponding cut set {C_j \subset V(G)}. Since {C_{j+1}} always contains a vertex that {C_1}, {\cdots}, {C_j} all do not, the {|V(G)| - 1} cut vectors corresponding to these cuts are linearly independent.

Hence, {\pi (e_i) = 0} if and only if {e_i} is a bridge, an edge whose removal would disconnect the graph. This means the only information lost by {\tilde{\varphi}_q} is the existence of bridges, which are collapsed into a point when the graph is drawn on {H_1 (\Gamma, \mathbb{R})}; elsewhere on {\Gamma}, the map is injective. Because of the isomorphism between {\text{Pic}^0 (\Gamma)} and {H_1 (\Gamma, \mathbb{R})/ H_1 (\Gamma, \mathbb{Z})}, this geometric observation can be translated to an equivalent algebraic fact about {\text{Pic}^0 (\Gamma)}: if {(p) \sim (p')}, then either {p=p'} or there is some bridge {e \in E(G)} such that {p}, {p' \in e}.

(Acknowledgment: the nice diagrams above are due to Samir Khan, UChicago ’19)


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s