Skip to Main Content

On the Gonality of Metric Graphs

Jan Draisma
Alejandro Vargas

Communicated by Notices Associate Editor Steven Sam

Article cover

The last decades have seen an extremely fruitful interplay between Riemann surfaces and graphs with a metric. A deformation process called tropicalisation transforms the former into the latter. Under this process, additional structure on the Riemann surfaces yields additional structure on the metric graphs. For instance, meromorphic functions on Riemann surfaces yield piecewise linear functions on metric graphs. In this manner, theorems in algebraic geometry have deep combinatorial consequences; and conversely, combinatorial arguments can be used to prove theorems in algebraic geometry.

This interplay has inspired the development of a stand-alone theory of metric graphs that has strong parallels to the theory of Riemann surfaces. Milestones are a Riemann-Roch formula, an Abel-Jacobi theorem, a theory of harmonic morphisms, and a Riemann-Hurwitz formula for metric graphs BN07GK08MZ08BN09, which closely resemble their classical counterparts for Riemann surfaces.

The purpose of this article is to discuss another beautiful parallel: that of maps where the geometry of the target space is as simple as possible. We summarise the story for Riemann surfaces in Section 1, and for metric graphs in Section 2. In both settings, the number of preimages of any point of the target space, counted with multiplicities, is a constant called the degree of the map. The minimal degree of such a map is called the gonality of the source space. This is a rough measure of the complexity of the space.

The gonality of a Riemann surface is bounded from above by a function of a topological invariant of the Riemann surface: its genus. In groundbreaking work Baker Bak08 and Caporaso Cap14 showed that under tropicalisation, the gonality either remains constant or decreases. This leads to a similar topological upper bound for the gonality of a metric graph. In Section 3 we outline how such a tropicalisation process works, and how it interacts with the gonality.

The upper bound on the gonality of metric graphs is a purely combinatorial statement whose proof, up to now, depended on algebraic geometry. We have recently completed a purely combinatorial construction of maps witnessing the gonality bound DV21Var20. The technical details of our construction are somewhat daunting—and indeed, we hope that this exposition might incite interest that leads to a simplification!—but the key ideas are very simple, and we discuss these in Section 4.

While the notion of gonality for metric graphs was inspired by algebraic geometry, it is related to the purely combinatorial graph notion of treewidth and to spectral graph theory; we briefly review these connections in Section 2.

1. Gonality of Riemann Surfaces

Recall that a Riemann surface is a connected complex manifold of complex dimension one, hence real dimension two. We restrict our attention to compact Riemann surfaces. As a topological space, such a surface is uniquely determined by its genus, which counts the holes in the surface.

In this setting, the space with the simplest geometry is the unique Riemann surface of genus 0: the Riemann sphere . Any compact Riemann surface admits a branched cover to , i.e., a holomorphic map that, near any , can be expressed as for some choice of local coordinates. The integer is independent of the choice of local coordinates and is called the ramification index of at . If , then is called ramified at . The set of points where is ramified is finite.

For a classical example, consider the elliptic curve , the quotient of by a lattice in . The Weierstrass -function defined as

turns out to be holomorphic around all and has a pole of order at all . Furthermore, it is doubly periodic with periods and , and hence factors through a meromorphic function of degree with a double pole at . This function extends to a holomorphic map with four index-two ramification points: the points .

The gonality of a compact Riemann surface is the lowest degree of a surjective holomorphic map from onto . A Riemann surface has gonality 1 if and only if it is isomorphic to , and the gonality of any elliptic curve is . The fundamental relation between gonality and genus is the following.

Theorem 1.

The gonality of a compact Riemann surface of genus is at most , with equality if is sufficiently general. Moreover, if is even and is sufficiently general, then the number of holomorphic maps to of degree from to , counted modulo automorphisms of , equals the th Catalan number .

Compact genus- Riemann surfaces are parameterised by a complex algebraic variety of dimension , called the moduli space of genus- Riemann surfaces, and the predicate “sufficiently general” in Theorem 1 means “for all in an open dense subset of the moduli space.” In fact, a genus- Riemann surface can have gonality much smaller than . For example, for every there exist gonality- Riemann surfaces of genus . These so-called hyperelliptic curves can be obtained by compactifying the solution set in of an equation , with a squarefree polynomial of degree or . By Theorem 1, hyperelliptic curves are quite atypical in the moduli space.

The Catalan numbers appear throughout mathematics. We will use the fact that is the number of Dyck paths: sequences , , …, in with , , (“up” and “down” steps, respectively), such that lies strictly above the -axis for all .

Theorem 1 is part of Brill-Noether theory, an area of algebraic geometry that has its roots in the late 19th century and is still very active today. The existence of branched covers of the given degree was already established by Riemann, and this was later generalised by Kempf Kem71 and Kleiman-Laksov KL72. The Catalan count was established, in the more general setting of Brill-Noether theory, by Griffiths-Harris GH80. Moreover, by EH87, when is even, there exists an irreducible variety mapping onto the moduli space of compact genus- Riemann surfaces whose fibre over a sufficiently general Riemann surface consists of points corresponding to the holomorphic maps of that surface onto . Our construction sketched in Section 4 yields a metric-graph analogue of this variety.

2. Gonality of Metric Graphs

Now we introduce metric graphs and their maps. Let be a finite, connected, undirected graph; multiple edges and loops are allowed, and we require that has at least one edge. For every choose a length . Construct a topological space by taking a real interval for each and glueing these together in the manner prescribed by . Equipped with the shortest-path metric, this topological space is what we call a metric graph . We call the pair a model for . Distinct models may yield isometric metric graphs.

Every point in has a neighbourhood isometric to a star of line segments glued along a common center, where the isometry maps to the center of the star. The number is called the valency of , and the line segments are called the directions from .

Figure 1.

The map is harmonic near . The numbers indicate slopes and we have .

A harmonic map from to another metric graph is a continuous map that, outside a finite number of points in , is linear with nonzero integral slopes with respect to the metrics on and , and which satisfies the following balancing condition: for each and each direction from , the sum of the slopes of along all directions from that map onto is independent of —i.e., replacing by a different direction from yields the same sum of slopes, which we denote . See Figure 1 for an illustration of the balancing condition and see Figures 2 and 3 for examples of harmonic maps.

We will see in Section 3 that harmonic maps between metric graphs arise as limits of holomorphic maps between Riemann surfaces. For now, a more direct motivation for the definition is as follows: for each real-valued function defined in an open neighbourhood of that satisfies the mean-value property, i.e., whose average over the points at distance from equals for any sufficiently small , the pullback also satisfies the mean-value property.

Figure 2.

Top: a metric graph of genus called the double lollipop. Bottom: a picture suggesting a tropical morphism of degree from that graph to a line segment. The edge and vertex colours match, the slope is on the red edge and the green edge, and the slope is on the blue edge; to illustrate this, that edge is depicted fatter in the picture below. These slopes ensure balancing at the light-blue and red vertices. The black numbers label edges of the tree below (a path with three edges), the white numbers label edges of the metric graph above.

Figure 3.

A metric graph of genus on the top, and a tropical morphism of degree from a modification to a tree on the bottom. The edge and vertex colours match, the slope is everywhere, and the dangling edges in the modification are depicted in transparent yellow. The black numbers label edges of the tree below, the white numbers label edges of the metric graph above.

By an iterative application of the balancing condition, one finds that is surjective and that, moreover, the number

is the same for all . This number is called the degree of . The idea that balancing implies surjectivity with fibres of equal total multiplicity will reappear in a higher-dimensional setting in Section 4.

To tighten the analogy with holomorphic maps even further, one introduces the Riemann-Hurwitz inequality, which requires that at each the harmonic map satisfies the condition

The origin of this inequality is that the left-hand side minus the right-hand side plus one is the tropical analogue of the ramification index of at , which should, of course, be positive. Note that at all but finitely many points , both sides are equal to zero, and hence has ramification index there. A harmonic map that satisfies the Riemann-Hurwitz inequality at every point is called a tropical morphism. The map in Figure 2 is a tropical morphism—e.g., in the red vertex the inequality reads —and so is the map in Figure 3.

Like compact Riemann surfaces, the metric graph has a genus, defined as the first Betti number of , which equals in any model of with . The simplest metric graphs are those of genus . They are the metric trees and play the role of . We now introduce an equivalence relation under which all metric trees turn out to be equivalent, so that we may think of them as different representatives of the tropical analogue of .

Pick a point in and attach a new line segment to at ; the segment has no other points glued to , and we therefore call it a dangling segment in the new metric graph . A graph that can be obtained from by a sequence of operations consisting of attaching and/or removing dangling segments is called a tropical modification of . Tropical modification is a ubiquitous operation in tropical geometry, where two different tropicalisations of the same algebraic variety often differ only by a tropical modification.

Every metric graph has a tropical modification that admits a tropical morphism to a metric tree. Indeed, to construct a tropical morphism to a line segment pick any and pin to a pinboard with a thumbtack at , letting the rest of hang down along a vertical line segment under the force of gravity. This yields the map that sends each to its distance from ; it has slope everywhere. By adding suitable dangling edges, this map can be made to satisfy the balancing condition, as well as the Riemann-Hurwitz inequality; see Figure 4.

Figure 4.

A degree- tropical morphism from a modification of the double lollipop graph to a line segment. The dangling segments are dashed.

The tropical morphism to a tree thus constructed typically does not have the minimal possible degree, but at least ensures that the minimal degree exists. We therefore may define the gonality of as

where ranges over all tropical modifications of , ranges over all metric trees, and ranges over all tropical morphisms from to .

The gonality of is equal to if and only if is a metric tree, and is equal to if and only if a tropical modification of admits an isometric involution such that is a metric tree; the moduli space of such tropical hyperelliptic curves is studied in Cha13.

Over the last years, the gonality of metric graphs has been the subject of research in combinatorics and computer science: the gonality of is bounded from below by the treewidth of for any model of vDdBG20, and also—like for Riemann surfaces YY80—by an expression involving its volume and the smallest positive eigenvalue of the Laplace operator of AK16. Moreover, like treewidth, gonality is NP-complete Gij15BvdWvdZ19.

Figure 3 shows that the genus- graph on the top has gonality at most . This is predicted by the following analogue of Theorem 1.

Theorem 2.

The gonality of a metric graph of genus is at most , with equality if is sufficiently general. Moreover, if is even and is sufficiently general, then the number of tropical morphisms of degree , where is a tropical modification of and is a metric tree, equals , when counted up to simultaneous tropical modification of and , as well as with certain multiplicities.

Genus- metric graphs , up to modifications, are parameterised by a space of real dimension , the moduli space of genus- metric graphs, and “sufficiently general” means “for all in some open dense subset of that space.”

For , that moduli space is glued from polyhedral cones of dimension , one for each genus- graph in which all vertices have valency at least ; see Cap12, where a genus- metric graph is called a pure tropical curve. As we move a vector through the cone , the metric graph with model moves through the moduli space.

The existence in Theorem 2 of a tropical morphism of degree to a tree from some modification of is due to Caporaso Cap14, following work by Baker on the existence of special divisors on metric graphs Bak08. They deduce this from Theorem 1 via a degeneration process, a variant of which we review in the next section. The fact that a sufficiently general genus- metric graph has gonality equal to follows from their work combined with work by Cools-Draisma, who, following ideas from Grigory Mikhalkin, do a careful parameter count in CD18. In Section 4, we sketch our new contribution to this area: a purely combinatorial proof of Theorem 2, which comes with the bonus of the Catalan count.

3. Tropicalisation

In this section, we sketch how Theorem 1 implies part of Theorem 2; more precisely, how the existence of holomorphic maps of degree for compact Riemann surfaces of genus implies the existence of a tropical morphism from a tropical modification of any genus- metric graph to some tree . Instead of following the more algebro-geometric approaches in Bak08Cap14, we discuss the hyperbolic-geometric approach taken in Lan20. Among other things, the latter paper gives a new viewpoint on Mikhalkin’s groundbreaking work on phase-tropical curves Mik06.

First, at the combinatorial level, there is a straightforward reduction to the case of even and to metric graphs that only have points of valency or ; we assume this throughout the remainder of this paper.

The metric graph can be realised as a tropical limit of a family of compact Riemann surfaces that we will construct now; we refer to Lan20 for details on this notion of convergence. The Riemann surfaces in the family are built up from pairs of pants as in Figure 5, obtained by glueing two copies of the unique right-angled hyperbolic hexagon with three alternating sides of lengths along the remaining three sides. Such a pair of pants has a canonical complex structure.

Figure 5.

The pair of pants glued from two geodesic hyperbolic hexagons.

Let be the model of in which each has valency , and let be a positive real number for each ; the relation between and will be explained below. Then we construct a compact Riemann surface as follows. For each , incident to , , , take a copy of , and glue these pairs of pants together along their boundary cycles in the manner prescribed by : if , then and are glued along their boundary cycle of circumference ; if so that is a loop, then we glue two legs of . There is one (real) degree of freedom in each of these glueings, namely, the angle under which the cycles are glued. These twists and the cycle lengths are the Fenchel-Nielsen coordinates on Teichmüller space. For our purposes, however, we ignore the twists.

The resulting structure inherits the structure of a complex manifold from the hexagons, and is hence a compact Riemann surface. We call the image of the boundary cycle corresponding to .

Now we choose via the formula

Then, as we let tend to , the tend to zero and the Riemann surface tropically converges to the metric graph in the sense of Lan20, Definition 1.1. This convergence is related to, but different from, convergence in the Gromov-Hausdorff sense; see Lan20, Remark 3.12.

Next, let be a holomorphic map of degree ; these exist by Theorem 1. We sketch how, in the limit for , these yield a tropical morphism from to a tree. For this take . Then the boundary cycles have disjoint images . A priori, each is only an immersed circle in . But it can be shown that after a suitable deformation of the , their images are disjoint, closed circles on the sphere ; we assume this from now on. Note that each may be covered multiple times by . Make a graph whose vertices are the connected components of and two are connected by an edge if they have a common in their boundary. The fact that has genus implies that is a tree.

For each , is a disjoint union of circles in ; one of these is , and the other circles are disjoint from all boundary cycles. Cut up along all of these (old and new) circles and construct from the connected components of the cut-up , like we constructed from the cut-up . Then is obtained from by subdividing edges and attaching dangling trees. Each edge corresponds to a circle in mapping to some circle ; let be the topological degree of the restriction .

The formula for in 1 guarantees that tropically converges to a tropical morphism from a modification of , with underlying graph , to the metric tree for a suitable edge length vector Lan20. The tropical morphism is linear on the open line segment in corresponding to an edge in , with slope equal to . In particular, the balancing condition and the Riemann-Hurwitz condition are immediate here.

On the other hand, if a point in corresponds to a vertex of and hence to a connected component of , then the balancing condition and the Riemann-Hurwitz inequality at follow from the fact that the restriction is a branched cover between Riemann surfaces with boundary.

This concludes our discussion of the relation between Theorems 1 and Theorem 2.

4. Proof Sketch of Theorem 2

In this section, we sketch our new, purely combinatorial proof of Theorem 2. As in the previous section, we assume that is even and that all points in have valency or .

Full-dimensional families of morphisms

Consider a triple of a trivalent genus- metric graph , a metric tree , and a tropical morphism , where is a tropical modification of . Let be the model of for which each has valency . We will say that points of lie above their images under in . The first key idea in our proof is to look at such triples that move in a family of the right dimension, namely, —recall from Section 2 that this is the dimension of the moduli space of genus- metric graphs, and equal to .

“Moving in a -dimensional family” is to be understood as follows. Call ordinary if has valency in and a sufficiently small open interval around in has the property that is a disjoint union of open intervals, each mapped bijectively onto with some integer slope; and call special otherwise. The special points are those above which the combinatorics of changes. If we delete from all special points , then our first requirement is that decomposes into open intervals. We write for the set of these intervals; is the edge set of a tree , a model of , and we let be the edge length vector for the metric graph .

Now each edge in passes above one or more of the edges in , possibly multiple times and with different slopes. Consequently, each edge length in is a nonnegative rational linear combination of the edge lengths in . We record the coefficients of these combinations in an -matrix , so that . Our second requirement is that is a nonsingular matrix. If both requirements are fulfilled, then we say that the triple moves in a family of the right dimension .

For instance, in Figures 2 and 3, the matrix equals

respectively, relative to the labellings of the edges in (in white) and (in black) indicated there, and both of these matrices are nonsingular -matrices.

Balancing

As we vary in the cone , its image moves through an open cone in , which maps to an open subset of the moduli space of genus- graphs. For instance, in Figure 3, one facet of that cone is given by the condition

This expresses that, for this combinatorial type of tropical morphisms, the orange edge with the white label , which is mapped onto the edges of the tree with the black labels and , has length less than the sum of the lengths of the yellow edge (white label , mapped onto black and ) and the green edge (white label , mapped onto black and ).

The second key ingredient in our proof is a careful analysis of what happens when a single entry of becomes zero. Call the resulting vector and set , and let be the corresponding tropical morphism. See Figure 6.

Figure 6.

The edge labelled in the tree in Figure 3 has been contracted to obtain .

Figure 7.

and with as limit upon contracting the edge labelled .

If the nonzero entries of are sufficiently general, then there are two possibilities: either has only positive entries, or precisely one entry is zero. In the former case, the metric graph still has the same (trivalent) combinatorial structure as —this is what happens in Figure 6—while in the latter case, has precisely one vertex of valency .

In either case, we construct all combinatorial types of tropical morphisms , …, , with equal to , that have as a limit when shrinking one edge of the underlying tree with edges. This can be done since all the axioms for a tropical morphism can be checked locally, so we need only to study local changes in the combinatorics of near the vertex corresponding to the shrunk edge. The matrices are all equal to except in the column corresponding to the edge of the tree that needs to be shrunk to arrive at .

Ideally, from among the , we would like to keep only those that move in a family of the right dimension. However, in the first case, where is still trivalent, this cannot be done via local combinatorial arguments: the nonsingularity of the matrix depends on the global structure of the morphism . However, it turns out that this is irrelevant for our approach: using local combinatorial arguments and the fact that the matrices all agree outside one column, we show that there exist positive rational numbers , …, such that the balancing equation

holds; a that does not move in a family of the right dimension contributes zero to this equation. Since is nonzero, the balancing equation implies that there exists at least one for which moves in a family of the right dimension, and indeed one for which and have opposite signs.

In our running example, equals and are seen in Figure 7. Furthermore, we have

and the balancing equation reads

In this example, the matrices and turn out to be the same, and indeed the tropical morphisms and have the same combinatorics; but they differ when we keep track of the (colours of the) edges of —blue and purple are swapped—and therefore need to be counted both.

A similar analysis can be done in the second case, where has a four-valent vertex. In that case, around there are precisely three combinatorial types of metric graphs, corresponding to the three different groupings of the four edges into two pairs. Here we find positive rational numbers such that is independent of .

Finally, in both cases, it turns out that the numbers can be chosen to depend on the morphism only (not on the limit that we are considering), and such that the are certain integers. We call their absolute value the multiplicity of the morphism . Then our result shows that the sum of the multiplicities of the morphisms near is constant (independent of ).

In our running example, these multiplicities are for , where 2 holds; and for both and , where the opposite of 2 holds—so we see that the open cone in parameterised by is adjacent to, and “balances out,” the two (identical) cones parameterised by , .

Just like the balancing condition for a harmonic morphism between metric graphs ensures that the morphism is surjective and has fibres of the same total multiplicity, our higher-dimensional balancing condition implies that each genus- metric graph admits the same number of degree- tropical morphisms to a tree, when counted with multiplicities. Note that the multiplicities are nonzero only for tropical morphisms that move in a family of the right dimension, so “accidental” tropical morphisms, for instance those from a hyperelliptic graph to a tree, will not be counted here.

The two remaining ingredients in our proof of Theorem 2 are: first, that the space of such morphisms is connected, and second, that the correct count is the Catalan number . The connectedness follows from two facts: first, that the space of metric graphs of genus is connected through codimension 1 (indeed, this is true even when restricting to graphs with higher connectivity Cap12); and second, an analysis of a special class of graphs discussed in the next paragraph.

Caterpillars of loops

Consider a “caterpillar of loops”: a metric graph whose underlying graph is obtained by taking a path , , , …, , of edges and attaching loops to and ; and lollipops (bridges leading to a loop) to the remaining . See Figure 8.

Figure 8.

Top: a caterpillar of genus . Bottom: one of its tropical morphisms to a metric tree.

Given a tropical morphism from a tropical modification of to a metric tree, it turns out that is linear on each edge ; let denote its slope. Then we show that the sequence , , is a Dyck path. Conversely, given a Dyck path, there is a unique tropical morphism from a modification of to a metric tree whose slopes along the edges are the second coordinates of the points in the Dyck path.

For instance, in Figure 8, if we let be the red vertex and be the orange vertex, then the slopes along , , , , are , , , , , so the Dyck path is , , , , , , .

The multiplicities of all these tropical morphisms turn out to be . So admits precisely tropical morphisms from modifications to trees. Furthermore, all Dyck paths are connected to each other via moves that change an occurrence of up-down into down-up or vice versa. We show that these moves can be realised via the type of moves on tropical morphisms discussed in the previous subsection. Together with the balancing formula 3, this implies that the space of morphisms from (modifications of) genus- metric graphs to metric trees that move in a family of dimension <