PDFLINK |
On the Gonality of Metric Graphs
Communicated by Notices Associate Editor Steven Sam

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 . defined as -function
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. .
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 , Catalan number th .
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 for all -axis .
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 ,.
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 replacing —i.e., 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.
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.


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 so is the map in Figure —and3.
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.
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.
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.
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
Next, let
For each
The formula for
On the other hand, if a point
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
Full-dimensional families of morphisms
Consider a triple
“Moving in a
Now each edge in
For instance, in Figures 2 and 3, the matrix
respectively, relative to the labellings of the edges in
Balancing
As we vary
This expresses that, for this combinatorial type of tropical morphisms, the orange edge with the white label
The second key ingredient in our proof is a careful analysis of what happens when a single entry of
The edge labelled



If the nonzero entries of
In either case, we construct all combinatorial types of tropical morphisms
Ideally, from among the
holds; a
In our running example,
and the balancing equation reads
In this example, the matrices
A similar analysis can be done in the second case, where
Finally, in both cases, it turns out that the numbers
In our running example, these multiplicities are
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-
The two remaining ingredients in our proof of Theorem 2 are: first, that the space of such morphisms
Caterpillars of loops
Consider a “caterpillar of
Top: a caterpillar of genus


Given a tropical morphism
For instance, in Figure 8, if we let
The multiplicities of all these tropical morphisms turn out to be