RECURSIONS, FORMULAS, AND GRAPH-THEORETIC

INTERPRETATIONS OF RAMIFIED COVERINGS OF THE SPHERE BY SURFACES OF GENUS 0 AND 1

RAVI VAKIL

Abstract. We derive a closed-form expression for all genus 1 Hurwitz numbers, and give a simple new graph-theoretic interpretation of Hurwitz numbers in genus 0 and 1. (Hurwitz numbers essentially count irreducible genus g covers of the sphere, with arbitrary specified branching over one point, simple branching over other specified points, and no other branching. The problem is equivalent to counting transitive factorisations of permutations into transpositions.) These results prove a conjecture of Goulden and Jackson, and extend results of Hurwitz and many others.

1. Introduction

The problem of enumerating factorisations of a permutation α ∈ S_{d} into transpositions is one of long-standing interest in combinatorics, functional analysis, knot theory, geometry, and physics. It is essentially equivalent to counting covers of the Riemann sphere ℙ_{ℂ}^{1} with branching over ∞ given by α, fixed simple branching at other specified points of the sphere, and no other branching, and it suffices to count irreducible covers of genus g, for all g. Hurwitz gave a simple formula when g = 0 (for any α, [H]); his result was largely forgotten until recently. (Strehl has extended Hurwitz’s idea to a complete proof, [S].)

Let l(α) be the number of cycles in α. Dénes gave a formula for the case g = 0 and l(α) = 1 ([D]), and Arnol’d extended this to g = 0, l(α) = 2 ([A]). The physicists Crescimanno and Taylor solved the case when g = 0 and α is the identity ([CT]). Goulden and Jackson dealt with the genus 0 case in its entirety, independently recovering Hurwitz’s result ([GJ1]). Other proofs have since been given (e.g. [GL]).

In positive genus, B. Shapiro, M. Shapiro, and Vainshtein have given a striking formula ([SSV]) when l(α) = 1 (and g is anything), involving the co-efficients of the generating function

(\frac{sinh x/2}{x/2})^{d−1} .

They also give formulas for g = 1 and l(α) = 2. Graber and Pandharipande have proved recursions for g = 0 and 1 when α is the identity (g = 0 due to Pandharipande, g = 1 to Graber and Pandharipande, [GP]) using divisor theory on the moduli space of stable maps. Goulden, Jackson, and Vainshtein ([GJV]) have derived formulas when g + l(α) ≤ 6, when g = 1, l(α) = 6, and when g = 1 and α is the identity (the latter using the recursion of Graber and Pandharipande). They also conjectured a general formula when g = 1. Recently, Ekedahl, Lando, M. Shapiro, and Vainshtein announced ([S]) that they have computed formulas for all Hurwitz numbers as intersections of natural classes on \overline{M}_{g,n}, the moduli space of n-pointed genus g curves (see 4.3).

In this article, we use the space of stable maps to give a closed form expression for all genus 0 and 1 Hurwitz numbers, generalizing the genus 1 results described above, and proving the conjecture of Goulden, Jackson, and Vainshtein (Corollary 1.5). En route, we interpret the genus 0 and 1 numbers as counting graphs with simple properties (Theorem 1.4). This idea appears to be new (even in genus 0) and suggests promising avenues for exploration in higher genus.

Date: November 29, 1998.

1.1. Outline. We use the theory of stable maps to ℙ^{1}. If g = 0 or 1, on the component of the moduli stack generically parametrizing degree d covers by smooth curves, the divisor corresponding to maps ramified above a certain fixed point is linearly equivalent to a divisor supported on the locus of maps from singular curves (the “boundary”). By restricting this equivalence to appropriate one-parameter families, we obtain recursions satisfied by Hurwitz numbers (Theorem 2.7), and the recursions determine the Hurwitz numbers (given the fact that there is one degree 1 cover of ℙ^{1}). These recursions (and initial condition) are also satisfied by the solution to a certain graph-counting problem. Finally, it is straightforward to get a closed-form solution to the graph-counting problem.

In Section 2, we derive the recursions, using results of [V1]. Readers unfamiliar with the language of algebraic geometry may prefer to skip the section, reading only Theorem 2.7. In Section 3, we relate the Hurwitz numbers to the graph-counting problem, and derived closedform formulas. In Section 4, we translate the recursions into differential equations, and speculate on connections to others’ work and to higher genus.

1.2. Conventions. If an edge of a graph has both endpoints attached to the same vertex, we say it is a loop. If a connected graph has V vertices and E edges, call 1 − V + E the genus of the graph. (Thus trees are genus 0 graphs, and connected graphs with a single cycle have genus 1.) When we count objects (e.g. covers of ℙ^{1}, or graphs with marked edges), if the automorphism group of the object is G, then the object is counted with multiplicity \frac{1}{|G|}. For example, the number of connected genus 1 graphs on two labelled vertices with no loops is \frac{1}{2}.

A labelled partition of d is a partition in which the terms are considered distinguished. For example, there are \binom{7}{3} ways of splitting the labelled partition α = [1^{7}] into two labelled partitions β = [1^{3}] and γ = [1^{4}]. We use set notation for labelled partitions (e.g. in this example, α = β ∐ γ, γ = α \ β). If α is a labelled partition of d, let l(a) be the number of terms in α, and let α_{1}, α_{2}, …, α_{l(α)} be the terms in the partition (so d = α_{1} + ⋯ + α_{l(α)}). A set of transpositions in S_{d} is transitive if it generates S_{d}. If g is an integer, set r_{α}^{g} := d + l(α) + 2g − 2. Let c_{α}^{g} be the number of factorizations of a fixed permutation σ ∈ C_{d}, with cycle structure given by α, into a transitive product of r_{α}^{g} transpositions.

Let G_{α}^{g} be the number of smooth degree d covers of ℙ_{ℂ}^{1} with ramification above ∞ given by α, simple branching at r_{α}^{g} other fixed points, and no other branching, where the ramification points above ∞ are labelled. Then by the Riemann-Hurwitz formula, the covering curve has genus g. By a simple argument, G_{α}^{g} = c_{α}^{g}/ ∏_{i} α_{i}. We call the numbers G_{α}^{g} Hurwitz numbers.

Another number of previous interest is a variation of these: if h_{α} is the size of the conjugacy class of α in S_{d}, then C_{α}^{g}h_{α}/d! is the number of smooth degree d covers of ℙ^{1} with ramification above ∞ given by α, simple branching at r_{α}^{g} other fixed points, and no other branching (and no marking of points above ∞). In [GJV], this number is denote μ_{l(α)}^{g}(α). These numbers are often called Hurwitz numbers as well.

Consider d labelled vertices, partitioned into subsets of size given by a labelled partition α; call these subsets clumps. A clump of size i will be referred to as an i-clump. Let T_{α}^{g} be the number of connected genus g graphs on these vertices, with no loops, with a set of ∑_{i}(α_{i} − 1) = d − l(α) of its edges that form trees on each of the clumps; we call these d − l(α) edges the edges in the clumps. (Thus T_{α}^{0} counts trees whose restriction to each of the clumps is Figure 1. Counting T_{α}^{1} = 4 when α is the partition 3 = 1 + 2 (the last two both count with multiplicity 1/2)

also a tree.) For example, if α is the partition 3 = 1 + 2, T_{α}^{1} = 4. This is illustrated in Figure 1, with the clumps indicated by ovals, and the edge in clumps indicated by drawing the edge entirely inside the corresponding oval.

1.3. Statement of results.

1.4. Theorem. —

G_{α}^{0} = \frac{r_{α}^{0}!T_{α}^{0}}{d ∏(α_{i} − 1)!}, G_{α}^{1} = \frac{r_{α}^{1}!T_{α}^{1}}{12 ∏(α_{i} − 1)!}.

The proof is given in Section 3.1.

It is not hard to find formulas for T_{α}^{0}, T_{α}^{1} (Proposition 3.2), so the above theorem gives formulas for G_{α}^{g} (and hence c_{α}^{g} = G_{α}^{g} ∏_{i} α_{i}) for g = 0, 1:

1.5. Corollary. —

G_{α}^{0} = \frac{r_{α}^{0}!d^{l(α)−3} ∏ α_{i}^{α_{i}−1}}{∏(α_{i} − 1)!} , G_{α}^{1} = \frac{r_{α}^{1}!d^{l(α)−2} ∏ α_{i}^{α_{i}−1}}{24 ∏(α_{i} − 1)!} (d^{2} − d − ∑_{j≥2} d^{2−j}(j − 2)!e_{j}),

where e_{j} is the jth symmetric polynomial in the α_{i}.

The formula for G_{α}^{0} is the same as that of Hurwitz, and the formula for G_{α}^{1} is the conjecture of Goulden, Jackson, and Vainshtein.

1.6. Remark. The author has recently learned that Goulden and Jackson have also just proved the above formula for G_{α}^{1}, by purely combinatorial means ([GJ2]). The method seems unrelated.

1.7. Acknowledgements. The author is grateful for discussions with A. J. de Jong, I. Goulden, M. Shapiro, and A. Vainshtein. This project was sparked by conversations with T. Graber and R. Pandharipande. The deformation theory in Sections 2.2, 2.3 and 2.5 was worked out jointly with de Jong.

2. Geometry

Fix a labelled partition α of a positive integer d. We work over the complex numbers, and rely heavily on Sections 2–4 of [V1]. All curves are assumed to be complete.

2.1. Background: Stable maps to ℙ^{1}. Recall that the moduli stack of stable maps \overline{M}_{g,n}(ℙ^{1}, d) is a fine moduli space for degree d stable maps from genus g curves with n labelled points to ℙ^{1}. When g = 0, it is a smooth stack. For definitions and basic results, see [FP]. Let \overline{M}_{g,n}(ℙ^{1}, d)^{+} be the (stack-theoretic) closure in \overline{M}_{g,n}(ℙ^{1}, d) of points corresponding to maps from smooth curves, or equivalently (from Section 2.3) the closure of points corresponding to maps with no contracted component (i.e. where no irreducible component of the source curve is mapped to a point).

The points of \overline{M}_{g,n}(ℙ^{1}, d)^{+} corresponding to maps from singular curves is a union of Weil divisors. Such points are called boundary points. Let Δ_{0} be the locus in \overline{M}_{g,n}(ℙ^{1}, d) that is the closure of the locus of maps of irreducible curves with one node. If 0 ≤ i ≤ g and 0 < j < d, let Δ_{i,j} be the locus in \overline{M}_{g,n}(ℙ^{1}, d) that is the closure of maps from a reducible curve C_{1} ∪ C_{2} where C_{1} is smooth of genus i and mapping with degree j, C_{2} is smooth of genus g − i and mapping with degree d − j, and C_{1} and C_{2} meet at a node.

By [V1] Section 3 there is a naturally defined divisor β on \overline{M}_{g}(ℙ^{1}, d)^{+} (in the operational Chow ring) such that the locus of maps branching above a fixed general point in ℙ^{1} lies in class β[\overline{M}_{g}(ℙ^{1}, d)^{+}]. If g = 0 or 1, β is linearly equivalent to a sum of boundary divisors (with multiplicities). If g = 0, the divisor Δ_{0,j} appears with multiplicity \frac{j(d−j)}{d} (Pandharipande’s relation, [P] Lemma 2.3.1, [V1] equation 5). If g = 1, the divisor Δ_{0} appears with multiplicity \frac{d}{12}, and the divisor Δ_{0,j} appears with multiplicity j ([V1] Claim 4.4 and equation 6).

2.2. Background: Deformations of a germ of a map.

(The results of the next two sections are not surprising in the analytic category.)

We recall results about “germs” of maps from nodal curves to smooth curves. Define τ : ℂ[[z]] → ℂ[[x, y]], τ(z) = x^{p} + y^{q}. Let C be the category of Artin local rings (A, 𝔪) over ℂ with A/𝔪 ≅ ℂ. Define the functor F : C → Sets as follows:

F (A) = {(δ : A[[z]] → B, α)} up to isomorphism, where B is an Artin local ring flat over A, α is an isomorphism B ⊗_{A} (A/𝔪) → ℂ[[x, y]]/(x, y), and the diagram

A[[z]]  →^{δ}  B
↓  ↓
ℂ[[z]] →^{τ} ℂ[[x, y]]/(x, y) ←^{α} B ⊗ ℂ

commutes (where the vertical arrows are restriction modulo 𝔪). Isomorphism in this category requires the commutativity of the obvious diagrams.

It is left to the reader to verify Schlessinger’s conditions ([Sch]). This functor has a hull, which can be taken to be

R = ℂ[[t, a, b_{1}, …, b_{p−1}, c_{1}, …, c_{q−1}]],

with h_{R} → F given by the “universal curve”

z = x^{p} + y^{q} + a + b_{1}x + ⋯ + b_{p−1}x^{p−1} + c_{1}y + ⋯ + c_{q−1}y^{q−1}, (1)

xy = t. (2)

Geometrically, this hull can be loosely thought of as parametrizing deformations of the germ of a map from a node to a pointed smooth curve (with formal co-ordinate z and point z = 0), where the node maps to the point z = 0, and the branches of the node ramify with order p and q. The source curve is given by (2), and the map to the pointed curve with parameter z and point z = 0 is given by (1). The locus where the curve remains singular is t = 0, which is clearly smooth (and irreducible).

Similarly, deformations of a ramification of order p over a pointed curve z = x^{p} are given by z = x^{p} + b_{p−1}x^{p−1} + ⋯ + b_{0}. This is well-known, and details (and the precise formulation) are left to the reader.

2.3. Background: Deformations of maps to ℙ^{1}.

Suppose ρ : C → ℙ^{1} is a degree d map from a nodal curve of arithmetic genus g, such that no component of C is contracted. Call formal (or analytic) neighborhoods of connected components A of Sing(ρ) ⊂ C special loci of ρ; denote such a special locus by (A, ρ). Special loci are (formal) neighborhoods of ramification points of C or nodes of C. The map ρ is stable, so the functor parametrizing deformations of the stable map ρ is pro-representable by the formal neighbourhood X of the corresponding point in the moduli stack of stable maps. The deformations are unobstructed of dimension 2d + 2g − 2. Sketch of proof: the deformation theory of ρ is controlled by Ext^{i}(ρ^{∗}Ω_{ℙ^{1}} → Ω_{C}, O_{C}). In this case the complex (ρ^{∗}Ω_{ℙ^{1}} → Ω_{C}) is quasi-isomorphic to (0 → Q) where Q is the cokernel of ρ^{∗}Ω_{ℙ^{1}} → Ω_{C}, supported on the (zero-dimensional) special loci of ρ. Hence the obstruction space Ext^{2}(ρ^{∗}Ω_{ℙ^{1}} → Ω_{C}, O_{C}) = Ext^{2}(Q, O_{C}) is 0, and Ext^{2}(ρ^{∗}Ω_{ℙ^{1}} → Ω_{C}, O_{C}) = Ext^{0}(Q, O_{C}) is 0 as well. Then an easy calculation using the long exact Ext(·, O_{C})-sequence for 0 → (0 → Ω_{C}) → (ρ^{∗}Ω_{ℙ^{1}} → Ω_{C}) → (ρ^{∗}Ω_{ℙ^{1}} → 0) → 0 gives Ext^{1}(ρ^{∗}Ω_{ℙ^{1}} → Ω_{C}, O) = 2d + 2g − 2. Thus Δ_{0} and Δ_{i,j} lie in \overline{M}_{g,n}(ℙ^{1}, d)^{+}, and (by a quick dimension count) are Weil divisors there.

Denote the formal schemes correspnding to the hulls of the special loci by X_{1}, …, X_{n} (whose local structure was given in Section 2.2). Then the natural map X → X_{1} × ⋯ × X_{n} is an isomorphism. A proof of this fact will appear in [V2]; essentially it is because the sheaf Q defined in the previous paragraph is a skyscraper sheaf on the special loci, and the restriction of Q to a particular locus controls the deformation theory of that locus. (More generally, it will be shown that if ρ : C → ℙ^{1} is any stable map, perhaps with contracted comopnents, the deformation space of ρ factors into a product of “deformation spaces of the special loci”.)

2.4. The stack \overline{H}_{α}^{g}. Let H_{α}^{g} be the locus in \overline{M}_{g}(ℙ^{1}, d) corresponding to smooth covers of ℙ^{1} with ramification over ∞ given by α, and with simple branching over r_{α}^{g} − 1 fixed general points of ℙ^{1}. By the Riemann-Hurwitz formula, only one ramification point is unaccounted for. Thus H_{α}^{g} is a one-parameter family with one “roaming” simple ramification point. Let \overline{H}_{α}^{g} be the (stack-theoretic) closure of H_{α}^{g} in \overline{M}_{g}(ℙ^{1}, d)^{+}. Then \overline{H}_{α}^{g} is a proper one-dimensional stack.

The family \overline{H}_{α}^{g} includes points of the boundary of one of two types. They correspond to when the “roaming” ramification hits a fixed ramification not over ∞, or when it hits one of the ramifications above ∞. In both cases the source curve is either an irreducible (1-nodal) curve of geometric genus g−1 (i.e. where \overline{H}_{α}^{g} meets Δ_{0}), or two smooth curves of genera adding to g, joined at a node (i.e. where \overline{H}_{α}^{g} meets some Δ_{i,j}).

2.5. Multiplicity calculation. We can use deformation theory to compute the multiplicity with which \overline{H}_{α}^{g} meets the boundary divisor Δ_{0} or Δ_{i,j} at a boundary point. Let \overline{H} be the locus in the hull described by (1) and (2) where the pre-image of z = 0 remains a single point (with multiplicity p + q), and the source curve is smoothed. Suppose I is the ideal of

R := ℂ[[t, a, b_{1}, …, b_{p−1}, c_{1}, …, c_{q−1}]]

defining \overline{H}. Multiplying (1) by x^{q} and using xy = t yields

zx^{q} ≡ x^{p+q} + b_{p−1}x^{p+q−1} + ⋯ + b_{1}x^{q+1} + ax^{q} + t^{1}c_{1}x^{q−1} + ⋯ + t^{q−1}c_{q−1}x + t^{q} (mod I). (3)

For convenience, let b = \frac{b_{p−1}}{p+q}, c = \frac{c_{q−1}}{p+q}, D = gcd(p, q). When z = 0, the right side of (3) must be a perfect (p + q)th power, i.e. (x + b)^{p+q}, so

b_{p−j} ≡ \binom{p + q}{j}b^{j}, a ≡ \binom{p + q}{p}b^{p}, t^{j}c_{j} ≡ \binom{p + q}{p + j}b^{p+j}, t^{q} ≡ b^{p+q} (mod I), (4)

and by symmetry

c_{q−j} ≡ \binom{p + q}{j}c^{j}, a ≡ \binom{p + q}{q}c^{q}, t^{j}b_{j} ≡ \binom{p + q}{q + j}c^{q+j}, t^{p} ≡ c^{p+q} (mod I). (5)

Note that tc_{1} = \binom{p+q}{p+1}b^{p+1} and c_{1} = \binom{p+q}{q−1}c^{q−1}, so tc^{q−1} = b^{p+1}.

Thus R/I is generated by b, c, and t with relations

b^{p} = c^{q}, t^{q} = b^{p+q}, t^{p} = c^{p+q}, tc^{q−1} = b^{p+1}

(and possibly more). If D > 1, b^{p} − c^{q} = 0 factors into ∏_{i=1}^{D}(b^{p/D} − ζ^{i}c^{q/D}) = 0, where ζ is a primitive Dth root of 1. Thus Spec ℂ[b, c, t]/(b^{p} − c^{q}, t^{q} − b^{p+q}, t^{p} − c^{p+q}, b^{p+1} − tc^{q−1}) has D irreducible components, with normalization parametrized by s, with b = ζ^{i}s^{q/D}, c = s^{p/D}, t = ζ^{i}s^{(p+q)/D}. (From the last formula, each branch meets t = 0 with multiplicity (p + q)/D.) Conversely, each such branch lies in the deformations described by (1) and (2), where the source curve is smoothed and the pre-image of z = 0 remains a single point, as these branches satisfy (4) and (5).

Hence the hull of this germ of a map, keeping ramification of order p + q above z = 0, has D branches, each of which intersect the boundary divisor t = 0 with multiplicity (p + q)/D. Thus the intersection of \overline{H}_{α}^{g} with the boundary at this point is p + q.

2.6. Recursions in genus 0 and 1.

Define \overline{I}_{α}^{g} as the closure of the locus in \overline{M}_{g,l(α)}(ℙ^{1}, d) corresponding to smooth covers of ℙ^{1} with ramification over ∞ given by α, with simple branching over r_{α}^{g} − 1 fixed general points of ℙ^{1}, and with the points over ∞ labelled. In short, \overline{I}_{α}^{g} can be thought of as parametrizing the same maps as \overline{H}_{α}^{g}, except the points over ∞ are labelled. There is a natural “forgetful” morphism \overline{I}_{α}^{g} → \overline{H}_{α}^{g}, generically of degree ∏ z_{α}(i)!, where z_{α}(i) is the number of times i appears in α. The linear equivalences for β in genus 0 and 1 relate the number of points on \overline{H}_{α}^{g} where the roaming ramification maps to a fixed general point of ℙ^{1} to the number of various boundary points (with various multiplicities). Each such point has ∏ z_{α}(i)! pre-images in \overline{I}_{α}^{g}. Thus instead of counting points of \overline{H}_{α}^{g} in the relation, we instead count points of \overline{I}_{α}^{g}. (In effect, we are pulling back the relation for β on \overline{H}_{α}^{g} to \overline{I}_{α}^{g}.) This will be more convenient computationally as, for example, deg β[\overline{I}_{α}^{g}] = G_{α}^{g}.

2.7. Theorem. — If α is a labelled partition of a positive integer d, then

(6) G_{α}^{0} = (r_{α}^{0} − 1) ∑ ; α=β ∐ γ \frac{i^{2}j^{2}}{d} G_{β}^{0}G_{γ}^{0}\binom{r_{α}^{0} − 2}{r_{β}^{0}} + ∑ \frac{α_{k}}{2} \binom{r_{α}^{0} − 1}{r_{β}^{0}} \frac{ij}{d} G_{β}^{0}G_{γ}^{0}, and

(7) G_{α}^{1} = 2\binom{d}{2}\frac{d}{12}(r_{α}^{1} − 1)G_{α}^{0} + \frac{d}{24} ∑ α_{k}G_{α′}^{0} + 2(r_{α}^{1} − 1) ∑ ; α=β ∐ γ i^{2}jG_{β}^{0}G_{γ}^{1}\binom{r_{α}^{1} − 2}{r_{β}^{0}}

+ ∑ α_{k}iG_{β}^{0}G_{γ}^{1}\binom{r_{α}^{1} − 1}{r_{β}^{0}}

The first sum in (6) and the second sum in (7) is over all ways of splitting α into two labelled partitions β of i and γ of j. The first sum in (7) is over all terms α_{k} of α, p + q = α_{k}, and where α′ is the labelled partition d = α_{1} + ⋯ + α̂_{k} + ⋯ + α_{l(α)} + p + q. Similarly, the second sum in (6) and the third sum in (7) is over all terms α_{k} of α, p + q = α_{k}, and ways of splitting α′ into two labelled partitions β of i and γ of j, with the p in labelled partition β and the q in labelled partition γ.

Note that along with the data G_{[1]}^{0} = 1, G_{[1]}^{1} = 0 (there is one degree 1 cover of ℙ^{1}, and it has genus 0), these recursions determine G_{α}^{0} and G_{α}^{1} for all α. In the case α = [1^{d}] (i.e. no ramification over ∞), these are the recursions of Graber and Pandharipande described in the introduction. Proof. If g = 0, the left side of (6) is deg β[\overline{I}_{α}^{0}]. By Section 2.1, it can be expressed as the sum of boundary points with certain multiplicities. The boundary points are of two types.

If the “roaming” ramification meets one of the r_{α}^{0} − 1 fixed ramification points over some point P ≠ ∞, the source curve splits into two components, one mapping with degree i (say), and one with degree j — this is a point of Δ_{0,i}. The ramification over ∞ must be partitioned among these components, as must the remaining r_{α}^{0}−2 branch points away from ∞. Given such degree i and j maps, there are ij ways of gluing a branch of the first curve over P to a branch of the second over P. There is an additional multiplicity of \frac{ij}{d} (from Pandharipande’s relation, Section 2.1), and a multiplicity of 2 from the multiplicity of the intersection of \overline{H}_{α}^{0} with Δ_{0,j} (Section 2.5). Finally, we must divide by 2 because the two components are not distinguished (any such degeneration of the curve into C_{1} ∪ C_{2} is counted twice, once when C_{1} corresponds to i, and once when it corresponds to j). This gives the first term in (6).

If the boundary point corresponds to when the “roaming” ramification meets one of the ramifications over ∞ (corresponding to the term α_{k}, say), and the branches of the node ramify with order p and q (p+q = α_{k}), the source curve splits into two components, one mapping with degree i, and one with degree j — this is a point of Δ_{0,i}. The ramification over ∞ must be partitioned among these components (with the p belonging to one labelled partition, and the q belonging to the other), as must the remaining r_{α}^{0} − 1 branch points away from ∞. There is a multiplicity of \frac{ij}{d} from Section 2.1, and we must divide by 2 because the two components are not distinguished. By Section 2.5, \overline{H}_{α}^{0} meets Δ_{0,i} with multiplicity α_{k}. This gives the second term in (6).

Equation (7), genus 1, is essentially the same.

If the “roaming” ramification meets one of the r_{α}^{1} − 1 fixed ramification points over P ≠ ∞, the source curve has a node. First, suppose the source curve is irreducible (and genus 0) — this is a point of Δ_{0}. Given a map from the normalization of that curve, there are \binom{d}{2} ways of gluing 2 different branches above P together to get a nodal curve. There is an additional multiplicity of \frac{d}{12} from Section 2.1, and a multiplicity of 2 from the multiplicity of intersection of \overline{H}_{α}^{1} with Δ_{0} (Section 2.5). This gives the first term in (7).

Second, suppose the source curve splits into two components, one of genus 0 and mapping with degree i (say), and one of genus 1 and mapping with degree j — this is a point of Δ_{0,i}. The ramification over ∞ must be partitioned among these components, as must the remaining r_{α}^{1} − 2 branch points away from ∞. Given such degree i and j maps, there are ij ways of gluing a branch of the first curve over P to a branch of the second over P. There is an additional multiplicity of i from Section 2.1, and a multiplicity of 2 from Section 2.5. This gives the third term in (7).

If the boundary point corresponds to when the “roaming” ramification meets one of the ramifications over ∞ (corresponding to the term α_{k}, say), and the branches of the node ramify with order p and q (p + q = α_{k}), suppose the source curve is irreducible — i.e. the boundary point lies on Δ_{0}. There is a multiplicity of \frac{d}{12} from Section 2.1, and we must divide by 2 because the two branches are not distinguished. By Section 2.5, \overline{H}_{α}^{1} meets Δ_{0} with multiplicity α_{k}. This gives the second term in (7).

Suppose otherwise that the source curve splits into two components, one of genus 0 mapping with degree i, and one of genus 1 mapping with degree j — i.e. the boundary point lies on Δ_{0,i}. The ramification over ∞ must be partitioned among these components (with the p belonging to one labelled partition, and the q belonging to the other), as must the remaining r_{α}^{1} − 1 branch points away from ∞. There is a multiplicity of i from Section 2.1. By Section 2.5, \overline{H}_{α}^{1} meets Δ_{0,i} with multiplicity α_{k}. This gives the fourth term in (7).

3. Combinatorics

3.1. Proof of Theorem 1.4. By inspection the result holds when d = 1. When d > 1, we show that \frac{r_{α}^{0}!T_{α}^{0}}{d ∏(α_{i}−1)!} (resp. \frac{r_{α}^{1}!T_{α}^{1}}{12 ∏(α_{i}−1)!}) satisfies the same recursion (Theorem 2.7) as G_{α}^{0} (resp. G_{α}^{1}).

Genus 0. Each tree counted by T_{α}^{0} has l(α) − 1 edges outside the clumps and d − l(α) edges inside the clumps.

The number of such trees with the choice of an edge e outside the clumps and the choice of a vertex v on that edge is 2(l(α) − 1)T_{α}^{0}. If edge e is removed, the tree breaks into two subtrees (and each clump belongs to one of the subtrees, splitting α into two labelled partitions β and γ), with (say) i and j vertices respectively (i + j = d). The number of ways of choosing the subtrees, along with the vertex in each subtree to lie on e, is ∑_{α=β ∐ γ}(iT_{β}^{0})(jT_{γ}^{0}). Hence

2(l(α) − 1)T_{α}^{0} = ∑ ; α=β ∐ γ iT_{β}^{0}jT_{γ}^{0}. (8)

The number of trees counted by T_{α}^{0} with the choice of an edge e inside the clump C corresponding to α_{k}, and a choice of a vertex v on edge e, is 2(α_{k} − 1)T_{α}^{0}. If edge e is removed, the tree breaks into subtrees, the α_{k} vertices in C are split into p and q (p + q = α_{k}), and the remaining clumps each belong to one of the subtrees as well. The number of ways of choosing this data is

2(α_{k} − 1)T_{α}^{0} = ∑ \binom{α_{k}}{p, q}(pT_{β}^{0})(qT_{γ}^{0})

where the sum is over all p + q = α_{k}, and the labelled partition α_{1} + ⋯ + α̂_{k} + ⋯ + α_{l(α)} + p + q is split into labelled partitions β (which must contain the p) and γ (which must contain the q). Summing over all α_{k} gives

2(d − l(α))T_{α}^{0} = ∑ \binom{α_{k}}{p, q}(pT_{β}^{0})(qT_{γ}^{0}) (9)

where the sum is now as described in Theorem 2.7. As r_{α}^{0} = (d − l(α)) + 2(l(α) − 1), adding (8) to half (9) gives

r_{α}^{0}T_{α}^{0} = ∑ ; α=β ∐ γ iT_{β}^{0}jT_{γ}^{0} + \frac{1}{2} ∑ \binom{α_{k}}{p, q}(pT_{β}^{0})(qT_{γ}^{0}).

Multiplying both sides by (r_{α}^{0} − 1)!/(d ∏(α_{i} − 1)!) gives the same recursion as in Theorem 2.7, with G_{δ}^{0} replaced by \frac{r_{δ}^{0}!T_{δ}^{0}}{d ∏(δ_{i}−1)!} for all δ, as desired.

Genus 1. This case is essentially the same. Each genus 1 graph counted by T_{α}^{1} has l(α) edges outside the clumps and d − l(α) edges inside the clumps.

The number of such graphs with the choice of an edge e outside the clumps and the choice of a vertex v on edge e is 2l(α)T_{α}^{1}. If edge e is removed, then the graph either remains connected, or breaks into two connected subgraphs.

Suppose the graph stays connected (and is hence a tree). Then the number of ways of choosing the tree, along with an ordered pair of distinct vertices (the endpoints of e), is d(d − 1)T_{α}^{0}.

Next, suppose the graph breaks into two connected subgraphs (so each clump belongs to one of the subgraphs, splitting α into β and γ), with (say) i and j vertices respectively (i + j = d). One of the subgraphs is genus 0, and the other is genus 1. The number of ways of choosing the subgraphs, along with the vertex in each subgraph to lie on e, is ∑_{α=β ∐ γ}(iT_{β}^{0})(jT_{γ}^{1}) + (iT_{β}^{1})(jT_{γ}^{0}).

Adding these two cases, we find:

2l(α)T_{α}^{1} = d(d − 1)T_{α}^{0} + 2 ∑ ; α=β ∐ γ(iT_{β}^{0})(jT_{γ}^{1}). (10)

The number of graphs counted by T_{α}^{1} with the choice of an edge e inside the clump C corresponding to α_{k}, and a choice of a vertex v on edge e, is 2(α_{k} − 1)T_{α}^{1}. If edge e is removed, the graph either remains connected (and genus 0) or breaks into two subgraphs (of genus 0 and 1).

If the graph remains connected, then edge e still breaks the clump of size α_{k} into two subtrees on p and q vertices (p + q = α_{k}). The number of ways of splitting the α_{k}-clump into a p-clump and a q-clump, then choosing the genus 0 graph, and then choosing the vertices in the pclump and q-clump (for endpoints of e) is ∑ pqT_{α′}^{0}\binom{α_{k}}{p,q} (where α′ is the labelled partition d = α_{1} + ⋯ + α̂_{k} + ⋯ + α_{l(α)} + p + q).

If the graph splits into two connected subgraphs, then the number of ways of splitting the α_{k}-clump into a p-clump and a q-clump, partitioning the remaining clumps between β and γ, choosing the endpoints of e in the p-clump and q-clump, and choosing the genus 0 and genus 1 subgraphs is 2 ∑ \binom{α_{k}}{p,q}pT_{β}^{0}qT_{γ}^{1}.

Adding these up over all α_{k} gives

2(d − l(α))T_{α}^{1} = ∑ pqT_{α′}^{0}\binom{α_{k}}{p, q} + 2 ∑ \binom{α_{k}}{p, q}pT_{β}^{0}qT_{γ}^{1}. (11)

As r_{α}^{1} = d + l(α), adding (10) to half (11) gives

r_{α}^{1}T_{α}^{1} = d(d − 1)T_{α}^{0} + \frac{1}{2} ∑ pqT_{α′}^{0}\binom{α_{k}}{p, q} + 2 ∑ ; α=β ∐ γ iT_{β}^{0}jT_{γ}^{1} + ∑ \binom{α_{k}}{p, q}pT_{β}^{0}qT_{γ}^{1}.

Multiplying both sides by (r_{α}^{1} − 1)!/(12 ∏(α_{i} − 1)!) gives the same recursion as in Theorem 2.7, with G_{δ}^{g} replaced by \frac{r_{δ}^{g}!T_{δ}^{g}}{12 ∏(δ_{i}−1)!} for all δ, and g = 0,1 as desired.

3.2. Proposition. — T_{α}^{0} = d^{l(α)−2} ∏ α_{i}^{α_{i}−1}. If e_{j} is the jth symmetric polynomial in the α_{i},

T_{α}^{1} = \frac{T_{α}^{0}}{2} (d^{2} − d − ∑_{j≥2} d^{2−j}(j − 2)!e_{j}).

Proof. The formula for T_{α}^{0} follows immediately from [L] Ex. 4.4.

For convenience, let

S_{i} = ∑_{\begin{matrix}α′⊂α \\ l(α′)=i \end{matrix}} (∏_{j} α′_{j}) (∑_{j} α′_{j}) = ∑_{\begin{matrix}α′ ∐ α′′=α \\ l(α′)=i \end{matrix}} (∏_{j} α′_{j}) (d − ∑_{j} α′′_{j}) = de_{i} − (i + 1)e_{i+1}.

The number of graphs counted in T_{α}^{1} where the cycle passes through only 1 clump of size α_{k} is \binom{α_{k}}{2}T_{α}^{0}: one edge of the cycle is outside the clump, and there are T_{α}^{0} choices for such graphs not including this edge, and \binom{α_{k}}{2} choices for this edges. Summing over all k, we have \frac{1}{2}T_{α}^{0}(d^{2} − d − 2e_{2}).

We next count the number of graphs counted in T_{α}^{1} where the cycle passes through i clumps (i > 1). The number of such graphs where the cycle passes through the i clumps corresponding to some α′ ⊂ α, l(α′) = i (where α′′ = α \ α′) can be counted as follows. There are ∏ α_{j}^{α_{j}−2} ways of choosing the edges inside the clumps (Cayley’s theorem). There are (i − 1)!/2 ways of choosing the cyclic ordering of the i clumps in the cycle. Then there are ∏(α′_{j})^{2} ways of choosing the cycle itself. Finally, by [L] Ex. 4.4 there are (∑ α′_{j})(∏ α′′_{j})d^{(l(α)−i+1)−2} ways of completing the graph. Adding these factors up over all the choices of α′ gives

∏_{j} α_{j}^{α_{j}−2} ∑_{\begin{matrix}α′ ∐ α′′=α \\ l(α′)=i \end{matrix}} \frac{(i − 1)!}{2} ∏_{j}(α′_{j})^{2} ∑_{j} α′_{j} ∏_{j} α′′_{j}d^{l(α)−i−1} = d^{l(α)−2} ∏_{j} α_{j}^{α_{j}−1} \frac{(i − 1)!}{2}d^{1−i}S_{i}

= T_{α}^{0} \frac{(i − 1)!}{2}d^{1−i}S_{i}

Summing over all i, and dividing by T_{α}^{0},

T_{α}^{1}/T_{α}^{0} = \frac{1}{2} (d^{2} − d − 2e_{2} + ∑_{i≥2}(i − 1)!d^{1−i}(de_{i} − (i + 1)e_{i+1}))

= \frac{1}{2} (d^{2} − d + ∑_{i≥2} ((i − 1)!e_{i}d^{2−i} − (i − 2)!d^{2−i}ie_{i}))

= \frac{1}{2} (d^{2} − d − ∑_{i≥2} d^{2−i}(i − 2)!e_{i})

Corollary 1.5 follows immediately.

4. Discussion and speculation

4.1. Other recursions. Other recursions initially seem more straightforward and natural than those of Theorem 2.7. For example, the number of factorisations of a permutation σ with given cycle structure into transpositions σ_{1} ⋯ σ_{r} can be recursively computed by considering the possibilities for σ_{r} (and the possible cycle structures of σσ_{r}), as in [GJ1] Lemma 2.2. However, the simplicity of the combinatorics of Section 3 suggests that the recursions of Theorem 2.7 are in some way the “right” way to view the problem.

4.2. Generating functions/potentials. If α is a partition (not labelled) of d, define v_{α} = ∏_{i≥1} v_{i}^{z_{α}(i)} where v_{1}, v_{2}, … are formal variables, and z_{α}(i) is the number of i’s in the partition α. Recall that h_{α} was defined as the size of the conjugacy class corresponding to α in S_{d}. Consider the following generating functions (or potential functions) for G_{α}^{0} and G_{α}^{1}:

F^{0} = ∑_{α⊢d} d\frac{G_{α}^{0}z^{d}u^{r_{α}^{0}}v_{α}h_{α}}{d!r_{α}^{0}!} , F^{1} = ∑_{α⊢d} 12\frac{G_{α}^{1}z^{d}u^{r_{α}^{1}}v_{α}h_{α}}{d!r_{α}^{1}!} .

Both sums are over ordinary partitions (i.e. not labelled) of d. (F^{0} is similar to the generating functions F̃ of [GJ1] Lemma 2.2 and Φ of [GJV] Section 3.)

Then Theorem 2.7 can be rephrased as a differential equation, analogous to the differential equation satisfied by the genus 0 Gromov-Witten potential ([FP]), or the differential equations satisfied by potentials for characteristic numbers of plane curves ([EK] Section 6, [V1]):

(12)  F_{u}^{0} = uz^{2}(F_{z}^{0})^{2} + \frac{1}{2} ∑_{p,q} pqv_{p+q}F_{v_{p}}^{0}F_{v_{q}}^{0},

(13)  F_{u}^{1} = uz^{2}(F_{zz}^{0} + 2F_{z}^{0}F_{z}^{1}) + ∑_{p,q} pqv_{p+q} (\frac{1}{2}F_{v_{p}v_{q}}^{0} + F_{v_{p}}^{0}F_{v_{q}}^{1}) .

In the genus 1 equation (13), the second term corresponds to the third term of (7) and vice versa. As these equations do not seem especially enlightening, the details of their derivations are omitted.

4.3. Higher genus.

The form of Theorem 1.4 is striking, and suggests immediate generalizations to higher genus. However, none of the obvious extensions seem to work. Surprising and beautiful partial results in higher genus are already known (described in the introduction), and it would be of interest to try to give these results a similar graph-theoretic interpretation.

Other approaches to Hurwitz numbers also involve graph enumeration problems. In particular, [A] and [SSV] both involved edge-ordered graphs. It would be worthwhile to understand the relationship between this graph-counting problem and that of this article, as the two interpretations are advantageous in different circumstances (here when g ≤ 1, there when l(α) is very small).

Another promising direction seems to be through the work of Ekedahl et al, who express Hurwitz numbers as Hodge integrals on \overline{M}_{g,n}. The recursions of Theorem 2.7 should follow from their analysis, as they are a consequence of the fact that the Hodge class is linearly equivalent to a sum of boundary divisors when g = 0 or 1. Also, intersections on \overline{M}_{g,n} are naturally sums over graphs, so the logical next step would be to try to give graph-theoretic interpretations to higher genus Hurwitz numbers.

Graber and Pandharipande have conjectured ([GP]) a recursion for genus 2 Hurwitz numbers with no ramification over ∞ (i.e. α is the labelled partition d = 1 + ⋯ + 1):

G_{[1^{d}]}^{2} = d^{2} (\frac{97}{136}d − \frac{20}{17}) G_{[1^{d}]}^{1} + ∑_{j=1}^{d−1} G_{[1^{j}]}^{0}G_{[1^{d−j}]}^{2}\binom{2d}{2j − 2}j(d − j) (−\frac{115}{17}j + 8d)

+ ∑_{j=1}^{d−1} G_{[1^{j}]}^{1}G_{[1^{d−j}]}^{1}\binom{2d}{2j}j(d − j) (\frac{11697}{34}j(d − j) − \frac{3899}{68}d^{2}) .

It is unclear why a genus 2 relation should exist (either combinatorially or algebro-geometrically). The relation looks as though it is induced by a relation in the Picard group of the moduli space, but no such relation exists. A proof of this conjecture may shed some light on the geometry of genus 2 pointed curves through the work of Ekedahl et al.

The grand motivating problem behind all of these results is that of enumerating the factorisations of a permutation σ ∈ S_{d} into r transpositions (not necessarily transitive) for any d, σ and r, and of giving this number concrete combinatorial meaning. One might speculate that this number would be an appropriate multiple of the number of graphs on d vertices (not necessarily connected), with clumps given by σ, with d − 1 + g edges (where g is given by r = d + l(σ) + 2g − 2), with some additional structure.

References

[A] V. I. Arnol’d, Topological classification of trigonometric polynomials and combinatorics of graphs with an equal number of vertices and edges, Functional analysis and its applications 30 no. 1 (1996) 1–17.

[CT] M. Crescimanno and W. Taylor, Large N phases of chiral QCD_{2}, Nuclear Phys. B 437 no. 1 (1995) 3–24.

[D] J. Dénes, The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959) 63–70.

[EK] L. Ernström and G. Kennedy, Contact cohomology of the projective plane, preprint 1998, math.AG/9703013.

[FP] W. Fulton and R. Pandharipande, Notes on stable maps and quantum cohomology, in Algebraic geometry Santa Cruz 1995 v. 2, J. Kollár, R. Lazarsfeld, D. Morrison eds., A.M.S., Providence, 1997.

[GL] V. V. Goryunov and S.K. Lando, On enumeration of meromorphic functions of the line, preprint.

[GJ1] I. P. Goulden and D. M. Jackson, Transitive factorisations into transpositions and holomorphic mappings on the sphere, Proc. of the A.M.S. 125 no. 1 (1997) 51–60.

[GJ2] I. P. Goulden and D. J. Jackson, manuscript in preparation.

[GJV] I. P. Goulden, D. M. Jackson and A. Vainshtein, The number of ramified coverings of the sphere by the torus and surfaces of higher genera, preprint 1998.

[GP] T. Graber and R. Pandharipande, personal communication.

[H] A. Hurwitz, Über die Anzahl der Riemann’schen Flächen mit gegebenen Verzweigungspunkten, Math. Ann. 55 (1902) 53–66.

[L] L. Lovasz, Combinatorial Problems and Exercises 2nd ed., Akadémiai Kiadó, Budapest, 1993.

[P] R. Pandharipande, Intersection of ℚ-divisors on Kontsevich’s moduli space \overline{M}_{0,n}(ℙ^{r}, d) and enumerative geometry, Trans. A.M.S., to appear.

[Sch] M. Schlessinger, Functors of Artin rings, Trans. A.M.S. 130 (1968) 208–222.

[S] M. Shapiro, personal communication.

[SSV] B. Shapiro, M. Shapiro, and A. Vainshtein, Ramified coverings of S^{2} with one degenerate branching point and enumeration of edge-ordered graphs, Adv. in Math. Sci. 34 (1997) 219–228.

[St] V. Strehl, Minimal transitive products of transpositions — the reconstruction of a proof of A. Hurwitz, Sém. Lothar. Combin. 37 (1996), Art. S37c, 12 pp. (electronic, see http://cartan.u-strasbg.fr:80/˜ slc/).

[V1] R. Vakil, Recursions for characteristic numbers of genus one plane curves, preprint 1998, submitted for publication; available at http//www-math.mit.edu/˜ vakil.

[V2] R. Vakil, The enumerative geometry of rational and elliptic curves in projective space, manuscript in preparation; earlier version math.AG/9709007.