Every way to pair a polygon's edges

Take a hexagon and pair its six edges. There are fifteen ways to do it: the first edge can be paired with any of the other five, then the first unpaired edge with any of the remaining three, and the last two with each other — five times three times one. Now glue each pair head to tail, the way a torus is made from a square, so that the surface keeps two sides. Every one of the fifteen gluings gives a closed surface, and the classification says each is a sphere with some number of handles. Which ones?

Five of them make a sphere and ten make a torus, and none make anything with two handles. The hexagon cannot: a surface built from one hexagon has one face and three edges, and its vertex count is at least one, so its Euler characteristic is at least 1 − 3 + 1 = −1, and since an orientable characteristic is even, it is at least zero. One handle is the most six edges can make.

The earlier essays on this topic answered the question which surface does this gluing give? one word at a time. This one asks the question the other way round — of all the gluings of a polygon, how many give each surface? — and the answer turns out to be a table with a structure of its own, one that was worked out in full only in 1986, and for a reason that had nothing to do with polygons.

One number decides the surface #

For an orientable gluing the classification needs only one number, and the polygon hands it over directly. A polygon with 2n edges, glued in pairs, becomes a surface with one face and n edges. The only thing the gluing decides is how many vertices the 2n corners collapse to, V. The Euler characteristic is V − n + 1, and since it equals 2 − 2g for a surface of genus g,

$$g = \frac{n + 1 - V}{2}.$$

So fewer vertices means more handles, and the whole census is a census of vertex counts. The largest V can be is n + 1, which gives the sphere; the smallest is one or two, depending on the parity of n, which gives the most handles the polygon can carry — ⌊n/2⌋ of them.

The vertex count has a pleasantly mechanical description. Gluing edge i head to tail with its partner j identifies the corner at the start of i with the corner at the end of j. So the corners are permuted: corner i goes to the corner just after edge i’s partner, and following that rule from a corner until it returns traces out every corner that becomes the same vertex. The vertices are the cycles of a permutation — the product of the pairing and a rotation of the polygon by one step — which is exactly the kind of object a covering turned out to be, and the reason the census can be computed for a thousand edges in a thousand steps.

Chords that cross make handles #

The chord diagrams are more than a way of drawing the pairings. They see the genus.

In the first diagram no two chords cross. The word is abcc⁻¹b⁻¹a⁻¹, a nest of pairs each sitting inside the last, and the corners fall into four vertices, the most a hexagon can have. It is a sphere. In the second, the chords for a and b cross, and the word contains aba⁻¹b⁻¹, the torus’s own word, as a stretch. In the third, all three chords cross at once. Both give two vertices and a torus.

The rule is general: a pairing gives a sphere exactly when no two of its chords cross. One direction is easy to see. If no chords cross, some chord joins two adjacent edges — the innermost of any nest — and gluing those two edges, xx⁻¹, simply folds them shut, removing two edges and one corner and leaving a polygon two edges smaller with the same property. The folding continues until nothing is left but a sphere. The other direction is the fact that a crossing pair, $a \dots b \dots a^{-1} \dots b^{-1}$, can always be moved by the cut-and-reglue moves into a torus’s commutator, so a crossing always costs a handle.

The rule turns the sphere column of the census into a known sequence. Non-crossing pairings of 2n points on a circle are counted by the Catalan numbers 1, 2, 5, 14, 42, 132, …, the sequence that counts triangulations, bracketings and binary trees. The hexagon’s five spheres are the Catalan number for n = 3; the octagon’s will be 14.

Why the spheres split into smaller spheres #

The Catalan numbers have a recurrence of their own, and the chord picture explains it directly. Look at the chord leaving the first edge. It joins that edge to some partner, and because no chord may cross it, every other chord lies entirely on one side of it or entirely on the other. The edges between the first edge and its partner must be paired among themselves, and so must the edges beyond the partner. Each side is a smaller polygon with a non-crossing pairing of its own.

If the first edge’s partner leaves 2k edges on the near side, then 2(n − 1 − k) remain on the far side, and the number of non-crossing pairings is the product of the counts for the two sides. Summing over where the partner sits gives

$$C_n = \sum_{k=0}^{n-1} C_k\, C_{n-1-k},$$

the recurrence that defines the Catalan numbers and that a balanced string of brackets obeys for the same reason: an opening bracket’s partner splits the string into an inside and an outside. A non-crossing pairing of edges is a balanced bracketing, with each chord an opening and a closing bracket, so the two counts are one count.

Topologically the recurrence says something too. The chord from the first edge cuts the sphere along a circle into two discs, and each disc, with its own non-crossing pairing, is a sphere with a hole. So a sphere assembled from a polygon is two smaller spheres assembled from smaller polygons and sewn together along one circle — which is the reason the sphere count multiplies where every higher-genus count must be added up by the full Harer–Zagier rule.

The smallest polygon for each surface #

The census also answers the most basic question a surface can ask of a polygon: how few edges does it need? A surface of genus g built from one face and n edges has V = n + 1 − 2g vertices, and V is at least one, so n is at least 2g. The smallest polygon that can make a surface with g handles has 4g edges, and it does so only by gluing every corner to a single vertex.

For one handle that is the square and its one torus word. For two it is the octagon and its twenty-one single-vertex gluings, and for three it is the twelve-sided polygon with 1,485 of them. The count of the Euler characteristic that every corner pays for — vertices less edges plus faces — is what forces this: with only one face to spend, handles have to be paid for with vertices, and each handle costs two.

The octagon in full #

With eight edges there are 7 × 5 × 3 × 1 = 105 pairings, and for the first time a surface with two handles is possible.

Fourteen spheres, the Catalan number, as the chord rule promised. Seventy tori. And twenty-one surfaces with two handles — the gluings in which all eight corners collapse to a single vertex, so that V = 1 and g = (4 + 1 − 1)/2 = 2. The standard word for the double torus, aba⁻¹b⁻¹cdc⁻¹d⁻¹, is one of them, but most of the twenty-one look nothing like it; the reduction moves would drive each to that standard form, and the figure simply records where they start.

The twenty-one also show how much freedom a single vertex leaves. Rotating the octagon by one step turns any single-vertex pairing into another, and so does reflecting it, yet the twenty-one do not fall into orbits of eight: some pairings return to themselves after a quarter turn or a half turn, and those form smaller orbits. The pairing that glues every edge to the edge directly opposite is unchanged by every rotation, and the standard double-torus word is unchanged by a half turn. The census counts every labelled pairing separately, which is what makes its numbers add up to 105 and what makes the recurrence exact.

The picture shows how the proportions have shifted. For the hexagon, a third of the pairings made spheres. For the octagon it is fourteen in 105, under one in seven, and the largest group is the tori. The most-handled surface, which did not exist for six edges, already claims a fifth of all pairings for eight.

The shares as the polygon grows #

Counting the pairings one at a time gets expensive fast — there are 10,395 for twelve edges and 135,135 for fourteen — but it can still be done, and the shares tell a clear story.

The sphere’s share collapses: from all of them at two edges, through two in three, a third, fourteen in 105, forty-two in 945, to 429 in 135,135 at fourteen edges — about a third of one per cent. The tori follow it down a step later. And the weight of every bar moves to the right, so that for fourteen edges the two highest genera, two and three handles, hold more than four fifths of all pairings.

That drift is the first sign of the result the next essay takes up. Most pairings of a large polygon make a surface with nearly as many handles as the polygon allows. The spheres, which the chord rule makes easy to picture and easy to count, are a vanishing exception, and the typical gluing is a tangle of crossing chords whose corners fall into only a few vertices.

It is also a reminder of how small cases mislead. At four edges, two of the three pairings are spheres, and anyone generalising from the square would expect gluing to produce mostly spheres. The square is the one polygon for which that is true. Crossing chords become the rule as soon as there is room for them, because a random chord is far more likely to cross some other chord than to avoid all of them.

The Harer–Zagier numbers #

The full table has a name. Write $\varepsilon_g(n)$ for the number of pairings of a 2n-gon that give genus g.

John Harer and Don Zagier found in 1986 that the table obeys a three-term recurrence,

$$(n+1)\,\varepsilon_g(n) = 2(2n-1)\,\varepsilon_g(n-1) + (n-1)(2n-1)(2n-3)\,\varepsilon_{g-1}(n-2),$$

which builds each row from the two before it. The recurrence reaches as far as anyone wants — the sixteen-edge row, with over two million pairings, is computed from it in a few multiplications — and it reproduces the counts made one pairing at a time wherever they can be checked. Every entry comes out a whole number, which is not obvious from the formula, since it divides by n + 1.

The table has two edges with closed forms. The first column is the Catalan numbers, which is the chord rule again. The last entry of every even row is a single-vertex count, and it is always exactly (2n − 1)!!/(n + 1): one pairing in three for the square, one in five for the octagon, one in seven for twelve edges. The table shows 21 = 105/5 and 1,485 = 10,395/7. Why the proportion should be so simple is not visible from the recurrence at all; it comes from a different way of counting, in which the vertex count is tracked as the number of cycles of the permutation described above.

Harer and Zagier did not set out to count gluings. They needed the numbers to compute an Euler characteristic of a different kind: that of the space of all complex structures on a surface of genus g, the moduli space, which can be cut into cells indexed by exactly these one-faced gluings. The polygon census was the combinatorial core of that computation, and its answer turned out to involve the values of the Riemann zeta function at negative odd integers. The table is a small window onto that result, and it is complete: nothing about the counts is conjectural.

A closed formula for every row #

Beyond the recurrence, the rows have a generating identity that packages all genera at once. If each gluing is weighted by N raised to its number of vertices, then

$$\sum_{g} \varepsilon_g(n)\, N^{\,n+1-2g} = (2n-1)!! \sum_{k \ge 1} 2^{k-1} \binom{n}{k-1} \binom{N}{k}.$$

At N = 1 each side counts every pairing once and both are (2n − 1)!!. At N = 2 and n = 2 the left side is 2 × 8 + 1 × 2 = 18, and the right is 3 × (2 + 4) = 18. The identity is what makes the one-vertex column simple, and it is also how the numbers first arose in practice: the left side is the average of the trace of the 2n-th power of a large random Hermitian matrix, where every term of the expansion is a pairing of 2n factors and every pairing contributes N to the power of its vertex count. That coincidence — that gluing polygons into surfaces and multiplying random matrices are the same count — is why the subject of these numbers is sometimes called map enumeration, and why physicists met them before topologists did.

None of this changes the classification. Each gluing still gives the surface its vertex count names, and the census only records how often each name comes up. But it answers a question the essay on bordered surfaces left open — which gluings give which surfaces, and how many — completely for the closed orientable case.

What the census leaves out #

The other half of the gluings. Every pairing here is glued head to tail. Allowing either orientation for each pair multiplies the count by $2^n$ and brings in the one-sided surfaces; the census of those, by the number of cross-caps, obeys its own recurrence and is not drawn.

Which gluings give the same surface in the same way. Two pairings with the same genus give surfaces that are topologically identical, but the pairings themselves differ, and the ways they differ — by rotating the polygon, by reflecting it — are not quotiented out. The census counts labelled pairings, which is what the recurrence counts too.

Bordered surfaces. Leaving some edges unpaired, as the essay on boundaries did, gives a table with three indices instead of two. Its recurrences exist and are harder, and the counts for boundary circles are not drawn here.

Why most gluings have handles #

The census closes one question and opens a sharper one. As the polygon grows, the table’s weight moves to the high genera, and the fraction of pairings giving a sphere falls faster than any power. What does a typical gluing of a large polygon look like — how many vertices does it leave, and how close to the maximum is its genus?

The answer is in the cycle description. The vertex count is the number of cycles of a product of two permutations, and for a random pairing that product behaves remarkably like a random permutation, which has very few cycles — about the logarithm of its length. So a random gluing of a thousand edges has only seven or eight vertices, and a genus within a few of the largest possible. The spheres that the chord rule counts so neatly are among the least typical surfaces a polygon can make.

A table in place of a list #

The classification of surfaces is a list: every closed orientable surface is a sphere with g handles, and one number says which. Counting the gluings of a polygon turns that list into a table, with a row for each polygon and a column for each genus, and the table is not arbitrary. Its first column is the Catalan numbers because a sphere is a gluing with no crossing chords. Its last entries are one pairing in n + 1. And every row follows from the two before it by a recurrence that arrived from the geometry of moduli space rather than from polygons.

Fifteen hexagon gluings, five spheres and ten tori; 105 octagon gluings, 14, 70 and 21. The numbers are small enough to draw every case, and the drawings show the one fact the table is built on: crossing chords are handles, and as the polygon grows there is no avoiding them.