A space whose points are graphs

A moduli space is a geometric space whose points are in bijection with the isomorphism classes of some kind of mathematical object. Think of it as a menu of your objects: picking a point of the space picks out one of them. Moduli spaces have a few key properties. Moving continuously in the space deforms the object continuously, and the boundary of the space tends to hold degenerate versions of the object. We start with two warm-up examples before turning to graphs.

Segments in ℝ²

A segment in the plane is a set [p, q] = {(1 − t)p + tq : 0 ≤ t ≤ 1} for two distinct points p and q. Call two segments the same if some rotation followed by a translation carries one onto the other. What does the space of all segments look like?

Translate so that p sits at the origin, then rotate so that q lies on the positive x-axis. Every segment is then the same as the segment from (0, 0) to (ℓ, 0), where ℓ = |q − p| > 0. Rotations and translations preserve length, so different values of ℓ really are different segments. The length is the only parameter:

What happens as ℓ approaches 0? The two endpoints collide and the segment collapses to a single point. That point is no longer a segment, but it is the natural limit of segments: a degenerate segment. It sits at the boundary point 0 of the ray, and adding it closes up (0, ∞) to [0, ∞).

Every segment also has a symmetry that swaps its two endpoints: the half-turn about its midpoint. That symmetry does not change ℓ, so it leaves no trace in the picture. The same thing will happen with loops in Part 4.

Why this example? Segments are the building block for the rest of the lecture. An edge of a metric graph is a segment, determined up to isometry by its length, and length zero is exactly where the edge degenerates. A graph with k edges will contribute a copy of (0, ∞)^k, one coordinate per edge.

Lines through the origin

A line through the origin in ℝ² is determined by its angle θ with the x-axis, taken in [0, π). As θ approaches π the line comes back to the x-axis, so the two ends of the interval are glued together and the space of lines is a circle. The map θ ↦ 2θ makes this precise: it identifies the space of lines with the unit circle. Each line is a very simple object, but the space of all of them has a hole.

The definition of a graph as a vertex set with a set of two-element subsets has trouble with three things we need: loops, several edges between the same two vertices, and edges that hang off a vertex and go nowhere. Half-edges handle all three at once.

A loop is an edge whose two halves have the same root. Parallel edges are several edges whose halves have the same pair of roots. Neither needs a special case.

We add two decorations.

1. Marked legs. A bijection m from the set L of legs to {1, 2, …, n}. Legs are the graph version of marked points, and we draw each leg with its number at the end.
2. Vertex weights. A function w : V → {0, 1, 2, …}. We draw a weight as a number inside the vertex and leave weight-0 vertices as plain dots.

The set r⁻¹(v) is the set of half-edges rooted at v, so |r⁻¹(v)| counts them. A loop at v contributes two half-edges and a leg contributes one. For a graph with no loops or legs, |r⁻¹(v)| is the usual degree of v.

The number |E| − |V| + 1 counts the independent cycles of G: it is the number of edges outside a spanning tree. The weights count genus that is hidden at a vertex. Contraction, at the end of this part, explains where hidden genus comes from.

Reading the table: a weight-0 vertex needs at least 3 half-edges, a weight-1 vertex needs at least 1, and a vertex of weight 2 or more is always fine. So a stable graph has no unweighted vertex with 1 or 2 half-edges. Those are the leaves and the vertices in the middle of an edge, which carry no information.

In the loop-and-leg graph above, swapping the half-edges a and b and fixing everything else is an automorphism. So |Aut(G)| = 2, even though no vertex and no edge moves. The old definition of a graph cannot see this symmetry, which is one reason half-edges are the right language.

A useful way to picture the proof: 2g − 2 + n is a budget of squares, and every vertex must pay for at least one. The figure below draws the budget for one graph.

Edge contraction

Legs have no length. Think of them as infinitely long, or as markers.

Step 1: one graph at a time

Fix G. The possible length functions form the open orthant ℝ^E(G)_>0, with one coordinate per edge. Two length functions give isomorphic metric graphs when an automorphism of G permutes the edges and carries one to the other. So the metric graphs with underlying graph G are parametrized by

Here is the graph with two parallel edges and legs 1 and 2 on different vertices. It has type (1, 2), and its automorphism swaps the two edges. So (ℓ₁, ℓ₂) and (ℓ₂, ℓ₁) give the same metric graph, and the quadrant of lengths folds in half along its diagonal.

Step 2: let lengths go to zero

Now close up the orthant to ℝ^E(G)_≥0. A point with ℓ(e) = 0 should be the graph where e has shrunk away, which is the contraction G/e from Part 2. So the face {ℓ(e) = 0} of the orthant of G is glued to the orthant of G/e. In the figure, each axis is a copy of the ray of the graph with one loop and both legs on its vertex, and the corner is the single vertex of weight 1.

• As a set, the points of M_g,n are exactly the isomorphism classes of metric stable graphs of type (g, n). The graph with no edges, one vertex of weight g carrying all n legs, is a single cone point where every orthant meets.
• Each piece is a cone, and the pieces are indexed by graphs. A graph with k edges gives a k-dimensional piece, and contraction says which piece is a face of which. The graphs ordered by contraction form the poset drawn in the explorer.
• By the edge bound in Part 2, the largest pieces have dimension 3g − 3 + n. They come from graphs with all weights 0 and all vertices trivalent.
• Symmetry folds the space: a graph whose automorphisms permute its edges gives a folded cone.

Making it small enough to draw

Scaling all edge lengths by the same positive number gives a similar metric graph. So M_g,n is a cone over the subspace of graphs with total length 1:

The button “Rescale to total length 1” in the figure above slides the point onto this slice. In Δ_g,n a graph with k edges contributes a (k − 1)-simplex, folded by its automorphisms, and the cone point disappears. So Δ_g,n has dimension 3g − 4 + n and is glued together from simplices. All the pictures below draw Δ_g,n, except for the smallest ones, where the whole cone fits.

A question to take into Part 4: for genus 0 and five legs, how many maximal pieces are there, and how do they glue?

In genus 0 every weight is 0 and every graph is a tree (|E| − |V| + 1 = 0). So a stable graph of type (0, n) is a tree whose leaves are the n labelled legs and whose vertices all have valence at least 3. Biologists call these phylogenetic trees, and M_0,n is the space of phylogenetic trees on n labelled species. Every leg is labelled, so these trees have no nontrivial automorphisms and nothing gets folded.

M_0,3: a point

The bound allows at most 3 · 0 − 3 + 3 = 0 edges. The only stable graph is one vertex with legs 1, 2, 3, so M_0,3 is a single point.

M_0,4: three rays

Now at most one edge is allowed. With no edges there is one vertex carrying legs 1, 2, 3, 4: the cone point. With one edge there are two trivalent vertices, and the legs split two and two. There are three ways to do that: 12|34, 13|24 and 14|23. Each gives a ray ℝ_≥0 of edge lengths, and contracting the edge sends each ray's endpoint to the cone point. So M_0,4 is three rays glued at a point, and Δ_0,4 is three points. Is M_0,4 a graph? Yes: a star K_1,3 with infinitely long edges.

M_0,5: the Petersen graph

Now dim M_0,5 = 2, so Δ_0,5 is 1-dimensional. It is a graph. Let's find its vertices and edges.

Vertices of Δ_0,5 are trees with one edge. One edge splits the legs into two sides, and each side needs at least 2 legs so that both vertices are at least trivalent. So the split is a 2-subset against a 3-subset of {1, …, 5}. Label the tree by its 2-subset {i, j}. There are C(5, 2) = 10 of them.

Edges of Δ_0,5 are trees with two edges. A trivalent tree with 5 legs has 3 internal vertices and 2 edges: a pair of legs at each end and one leg in the middle. This is a caterpillar. Contracting either edge gives a one-edge tree. If the ends hold the pairs {i, j} and {k, l}, the two contractions are the trees labelled {i, j} and {k, l}. To count them: 5 choices for the middle leg, then 3 ways to split the other four into two pairs, for 15 trees.

So Δ_0,5 has a vertex for each 2-subset of {1, …, 5}, and {i, j} is adjacent to {k, l} exactly when the two subsets are disjoint. That is the Kneser graph K(5, 2), which is the Petersen graph. Before looking at the answer, try to label it yourself.

Each edge of Δ_0,5 is a family of caterpillars. Walking along the edge from {i, j} to {k, l} shrinks one internal edge while the other grows. Drag the point to watch it happen.

Some checks.

• Each vertex {i, j} has C(3, 2) = 3 disjoint partners, so the graph is 3-regular with 10 · 3 / 2 = 15 edges.
• So M_0,5 is the cone over the Petersen graph: 15 two-dimensional quadrants, glued in threes along 10 rays.
• The cycle rank of the Petersen graph is 15 − 10 + 1 = 6 = 3!. In general Δ_0,n is homotopy equivalent to a wedge of (n − 2)! spheres of dimension n − 4. For n = 5 that is 6 circles.

Examples with genus

M_1,1: a ray. At most one edge is allowed. The graphs are a vertex of weight 1 with the leg, and a weight-0 vertex with a loop and the leg (it has 2 + 1 = 3 half-edges). Contracting the loop gives the first graph. The second graph has Aut = ℤ/2, which flips the loop's two half-edges, but the flip does not change the loop's length. So M_1,1 is a ray and Δ_1,1 is a point. This is the segment's endpoint swap from Part 1. The automorphism is invisible in the space, but it is still there, and it matters in algebraic geometry.

M_1,2: a segment. At most two edges are allowed, so Δ_1,2 is 1-dimensional. There are two graphs with two edges.

• A: two weight-0 vertices joined by two parallel edges, with leg 1 on one vertex and leg 2 on the other. Aut(A) = ℤ/2 swaps the two edges, so its piece of Δ_1,2 is the segment {ℓ₁ + ℓ₂ = 1} folded in half at ℓ₁ = ℓ₂ = ½. This is the slice of the folded quadrant from Part 3.
• B: a vertex with a loop, joined by a bridge to a vertex carrying legs 1 and 2. Its automorphism flips the loop and fixes both lengths, so its piece is a full segment.

There are two graphs with one edge, the vertices of Δ_1,2.

• C: one weight-0 vertex with a loop and legs 1 and 2. It is A with either edge contracted, and B with the bridge contracted.
• D: a weight-1 vertex joined by an edge to a vertex carrying legs 1 and 2. It is B with the loop contracted.

So Δ_1,2 is a segment. The piece of B runs from D to C, and the folded piece of A continues from C to the point where ℓ₁ = ℓ₂, which is not glued to anything.

Activity: genus 2, no legs

List all stable graphs of type (2, 0) and organize them by contraction. There are 7. The bounds from Part 2 say each has at most 2 vertices and at most 3 edges. Try it before revealing the rows.

So Δ₂ has two triangles, one for the theta graph and one for the dumbbell, each folded by its automorphisms. The theta graph's automorphisms permute its three edges in all six ways, so only a sixth of its triangle survives. The dumbbell's automorphisms swap its two loops, so half of its triangle survives. The two pieces are glued along the segment of figure-eights, also called roses.

This part is a story with pictures, not proofs. The combinatorics above is a shadow of something much bigger.

The moduli space of curves. Algebraic geometers study the moduli space of curves ℳ_g,n. Its points are Riemann surfaces of genus g (a sphere with g handles) with n marked points. It has complex dimension 3g − 3 + n, the same number as our bound on the number of edges. That is not a coincidence.

Degenerations and dual graphs. ℳ_g,n is not compact. A surface can degenerate when a loop drawn on it pinches down to a point. The limit is a nodal curve: several surfaces glued together at points. Every nodal curve has a dual graph.

Two things line up exactly.

• A nodal curve is stable, meaning it has only finitely many automorphisms, exactly when its dual graph is stable in our sense. The inequality 2w(v) − 2 + |r⁻¹(v)| > 0 says that each component, with its nodes and marked points removed, has negative Euler characteristic.
• Contracting an edge corresponds to smoothing a node. So the way our cones glue is the way the boundary strata of the compactified moduli space fit together. A graph with k edges corresponds to a stratum of codimension k.

What the edge lengths mean. Roughly, the length of an edge measures how fast the corresponding neck pinches in a family of surfaces. A longer edge means a thinner neck.

The precise statement. The space Δ_g,n is the boundary complex of the Deligne–Mumford compactification of ℳ_g,n (Abramovich, Caporaso and Payne). As a result, its homology computes the top-weight cohomology of ℳ_g,n. Chan, Galatius and Payne used this to show that the rational cohomology of ℳ_g in degree 4g − 6 is nonzero for g = 3, 5 and every g ≥ 7, and that its dimension grows at least exponentially in g. Counting holes in a space of graphs told us something new about the space of all surfaces.

Back to M_0,5. The compactified moduli space of 5 points on the sphere is a complex surface. Its boundary consists of 10 curves, one for each 2-subset of {1, …, 5}, and two of them meet exactly when their 2-subsets are disjoint. The Petersen graph is the picture of how they meet.

Everything from this semester shows up in current research on the geometry of surfaces: trees, cycles, contraction, automorphisms, and the Petersen graph.

Optional problems for anyone who wants more.

1. Write the graph with one vertex, two loops and one leg in half-edge notation (V, H, r, ι). Compute |Aut(G)|.

   Answer

   |Aut(G)| = 8. Each loop can be flipped, and the two loops can be swapped: 2 · 2 · 2.

2. Show that edge contraction preserves genus and stability.

   Hint

   See the two key facts at the end of Part 2: track |E| − |V| + 1, the weights, and the budget 2w − 2 + |r⁻¹(v)| of the vertices involved.

3. How many stable graphs of type (0, 6) have 3 edges?

   Answer

   105, the number of trivalent trees with 6 labelled leaves, which is (2 · 6 − 5)!! = 7 · 5 · 3.

4. Show that Δ_0,5 has no 3-cycles and no 4-cycles, so its girth is 5.

5. Verify the list of 7 stable graphs of type (2, 0), and compute |Aut| for the theta graph.

   Answer

   12. The symmetric group S₃ permutes the three edges, and ℤ/2 swaps the two vertices.

6. Challenge: show that the number of trivalent trees with n labelled leaves is (2n − 5)!!.

Further reading

The research literature has its own name for the graphs in these notes, and you will see it in the titles of these papers.

• Melody Chan, lecture notes on curves and their moduli spaces. The most readable introduction.
• Billera, Holmes and Vogtmann, Geometry of the space of phylogenetic trees. The genus-0 story, motivated by biology.
• Abramovich, Caporaso and Payne, on the moduli space of curves and its boundary complex. The precise link to algebraic geometry.
• Chan, Galatius and Payne, on graph complexes and the top-weight cohomology of ℳ_g. The cohomology application from Part 5.