text:
# Gromov-Witten theory, Hurwitz numbers, and Matrix models, I

## Part I Overview

### 1 Introduction

#### 1.1 Gromov-Witten theory, matrix models, and integrable hierarchies

Our goal here is to present a new path connecting the intersection theory of the moduli space $`\overline{M}_{g,n}`$ of stable curves to the theory of matrix models. The relationship between these subjects was first discovered by E. Witten in 1990 through a study of 2 dimensional quantum gravity . The path integral in the quantum gravity theory on a genus $`g`$ topological surface $`\mathrm{\Sigma }_g`$ admits two natural interpretations. First, the free energy of the theory may be expressed as a generating series of tautological intersections products in $`\overline{M}_{g,n}`$. A second approach via approximations by singular metrics on $`\mathrm{\Sigma }_g`$ is connected to the asymptotic expansions of Hermitian matrix integrals — the theory of matrix models. Witten conjectured that the Korteweg-de Vries equations (known to control the associated matrix models) governed the intersection theory of $`\overline{M}_{g,n}`$. These KdV equations completely determine the tautological intersections in $`\overline{M}_{g,n}`$. As there was no previous mathematical approach to these intersections, the relationship to matrix models and integrable systems came as a beautiful surprise.

In 1992, M. Kontsevich provided a mathematical connection between the intersection theory of $`\overline{M}_{g,n}`$ and matrix models. The connection required two main steps. First, Kontsevich constructed a combinatorial model for the intersection theory of $`\overline{M}_{g,n}`$ via a topological stratification of the moduli space defined by Strebel differentials . The combinatorial model expresses the tautological intersections as sums over trivalent graphs on $`\mathrm{\Sigma }_g`$. Further details of Kontsevich’s construction, some quite subtle, are discussed in .

Kontsevich’s second step was to interpret the trivalent graph summation as a Feynman diagram expansion for a new matrix integral (Kontsevich’s matrix model). The KdV equations were then deduced from the analysis of the matrix integral. The details of this second step are discussed in several papers, see for example .

Witten’s conjecture (Kontsevich’s theorem) is remarkable from several perspectives — it is certainly among the deepest known properties of the moduli space of curves. Once the connection to matrix models is made, combinatorial techniques and ideas from the theory of integrable systems may be used study the free energy $`F`$ and the partition function $`Z=e^F`$. For example, Witten’s conjecture may be reformulated in terms of Virasoro constraints: the KdV equations for $`F`$ are equivalent to the annihilation of $`Z`$ by a specific set of differential operators which form a representation of (a part of) the Virasoro algebra.

The moduli of stable curves $`\overline{M}_{g,n}`$ may be naturally viewed in the richer context of the moduli of stable maps $`\overline{M}_{g,n}(X)`$ from curves to target varieties $`X`$. Gromov-Witten theory is the study of tautological intersections in $`\overline{M}_{g,n}(X)`$. The development of Gromov-Witten theory was motivated by Gromov’s work on the moduli of pseudo-holomorphic maps in symplectic geometry and Witten’s study of 2 dimensional gravity . It is expected that the intersection theory of $`\overline{M}_{g,n}(X)`$ will again be governed by matrix models and their associated integrable hierarchies.

In particular, the Gromov-Witten theory of the target $`X=𝐏^1`$ has been intensively studied by the physicists T. Eguchi, K. Hori, C.-S. Xiong, Y. Yamada, and S.-K. Yang. A conjectural formal matrix model for $`𝐏^1`$ has led to a precise prediction for Gromov-Witten theory analogous to Witten’s conjecture: intersections in $`\overline{M}_{g,n}(𝐏^1)`$ are governed by the Toda equations (see ).

For arbitrary $`X`$, it remains unclear at present what the corresponding matrix model or the integrable hierarchy should be. However, there exists a precise conjecture for the associated Virasoro constraints. This was formulated in 1997 for an arbitrary nonsingular projective target variety $`X`$ by Eguchi, Hori, and Xiong (using also ideas of S. Katz) . This Virasoro conjecture generalizes the Virasoro formulation of Witten’s conjecture and is one of the most fundamental open questions in Gromov-Witten theory.

#### 1.2 Hurwitz numbers

The goal of the present paper is to provide a new and complete proof of Kontsevich’s combinatorial formula for intersections in $`\overline{M}_{g,n}`$. Our approach uses a connection between intersections in $`\overline{M}_{g,n}`$ and the enumeration of branched coverings of $`𝐏^1`$ — Strebel differentials play no role. In fact, two models for the intersection theory of $`\overline{M}_{g,n}`$ are naturally found from our perspective: Kontsevich’s model and an alternate model called the *edge-of-the-spectrum matrix model*. The relation between the latter matrix model and $`\overline{M}_{g,n}`$ was recognized in  and then used in .

Concretely, we consider the enumeration problem of Hurwitz covers of $`𝐏^1`$. Let $`\mu `$ be a partition of $`d`$ of length $`l`$. Let $`H_{g,\mu }`$ be the Hurwitz number: the number of genus $`g`$ degree $`d`$ covers of $`𝐏^1`$ with profile $`\mu `$ over $`\mathrm{}`$ and simple ramification over a fixed set of finite points. The path from the intersection theory of the moduli space of curves to matrix models developed here uses two approaches to the Hurwitz numbers.

First, the numbers $`H_{g,\mu }`$ may be expressed in terms of tautological intersection products in $`\overline{M}_{g,l}`$. The $`l`$-point generating series for intersections then arises naturally via the large $`N`$ asymptotics of $`H_{g,N\mu }`$.

The relationship between the numbers $`H_{g,\mu }`$ and the intersection theory of $`\overline{M}_{g,l}`$ was independently discovered in  (for $`\mu =1^d`$) and  (for all $`\mu `$). The method of  is a direct calculation in the Gromov-Witten theory of $`𝐏^1`$. The Hurwitz numbers arise by definition as intersections in $`\overline{M}_g(𝐏^1)`$. The virtual localization formula of  precisely relates these intersections to $`\overline{M}_{g,l}`$. The study of $`H_{g,\mu }`$ for general $`\mu `$ within the Gromov-Witten framework was completed in . The method of  follows a different path — the result is obtained by an analysis of a twisted Segre class construction for cones over $`\overline{M}_{g,l}`$.

Second, the Hurwitz numbers may be approached via graph enumeration. The large $`N`$ asymptotics of $`H_{g,N\mu }`$ is then related to the sum over trivalent graphs arising in Kontsevich’s model. This asymptotic analysis involves probabilistic techniques, in particular, a study of random trees is required.

#### 1.3 Plan of the paper

The Hurwitz path from the intersection theory of $`\overline{M}_{g,n}`$ to matrix models draws motivations and techniques from several distinct areas of mathematics. A parallel goal of the paper is to provide an exposition of the circle of ideas involving Gromov-Witten theory, Hurwitz numbers, and random graphs.

The paper consists of three parts. The first part covers the background material and explains the general strategy of the proof. We start with a review of Witten’s conjecture and Kontsevich’s combinatorial model for tautological intersections in Section 2.

The Hurwitz numbers, which are the main focus of the paper, are discussed in Section 3. Three characterizations of $`H_{g,\mu }`$ are given in Section 3.1. The relationship between the Hurwitz numbers and the intersection theory of moduli space is introduced in Sections 3.2-3.3. A summary of the asymptotic study of $`H_{g,\mu }`$ via graph enumeration is given in Section 3.4.

Section 4, concluding Part I of the paper, is devoted to a brief discussion of the edge-of-the-spectrum matrix model and Kontsevich’s matrix model. We also discuss there another connection between Hurwitz numbers and integrable hierarchies via the Toda equations. We will return to the material of Section 4 in the sequel  to this paper which will contain a more in depth discussion of matrix models and integrable hierarchies arising in Gromov-Witten theory.

Part II of the paper, consisting of Sections 5-7, contains a survey of the proof in Gromov-Witten theory of the formula for $`H_{g,\mu }`$ in the intersection theory of $`\overline{M}_{g,l}`$. Our exposition follows . An effort is made here to balance the geometrical ideas with the tools needed from Gromov-Witten theory: branch morphisms, virtual classes, and the virtual localization formula.

In Part III of the paper, we investigate the asymptotics of Hurwitz numbers using the methods of . Results from the theory of random trees, summarized in Section 8, play a significant role in this asymptotic analysis. In the end, Kontsevich’s combinatorial model is precisely recovered from the asymptotics of the Hurwitz numbers.

Finally, there are two appendices. The classical recursions for the Hurwitz numbers are recalled in Appendix A. These recursive formulas are obtained by studying the degenerations of covers as a finite branch point is moved to $`\mathrm{}`$. The degeneration formulas provide an elementary, if not very efficient, method of computing $`H_{g,\mu }`$. A short table of the values of the various integrals discussed in the paper is given in Appendix B. The tables cover the cases of $`g2`$ and $`d4`$.

#### 1.4 Acknowledgments

We thank J. Bryan, C. Faber, B. Fantechi, E. Getzler, A. Givental, T. Graber, E. Ionel, Y. Ruan, M. Shapiro, R. Vakil, and C.-S. Xiong for many discussions about Hurwitz numbers and Gromov-Witten theory. We thank Jim Pitman for his aid with the literature on random trees. A. O. was partially supported by DMS-9801466 and a Sloan foundation fellowship. R. P. was partially supported by DMS-0071473 and fellowships from the Sloan and Packard foundations.

### 2 Kontsevich’s combinatorial model for the intersection theory of $`\overline{M}_{g,n}`$

#### 2.1 Intersection theory of $`\overline{M}_{g,n}`$ and KdV

The intersection theory of $`\overline{M}_{g,n}`$ must be studied in the category of Deligne-Mumford stacks (or alternatively, in the orbifold category) to correctly handle the automorphism groups of the pointed curves. $`\overline{M}_{g,n}`$ is a complete, irreducible, nonsingular Deligne-Mumford stack of complex dimension $`3g3+n`$. Intersection theory for $`\overline{M}_{g,n}`$ was first developed in  (see also ).

We will require the tautological $`\psi `$ classes in $`H^2(\overline{M}_{g,n},)`$. For each marking $`i`$, there exists a canonical line bundle $`𝕃_i`$ on $`\overline{M}_{g,n}`$ determined by the following prescription: the fiber of $`𝕃_i`$ at the stable pointed curve $`(C,x_1,\mathrm{},x_n)`$ is the cotangent space $`T_C^{}(x_i)`$ of $`C`$ at $`x_i`$. We note while $`𝕃_i`$ is a stack line bundle, $`𝕃_i`$ only determines a $``$-divisor on the coarse moduli space. Let $`\psi _i`$ denote the first Chern class of $`𝕃_i`$.

Witten’s conjecture concerns the complete set of evaluations of intersections of the $`\psi `$ classes:

$$_{\overline{M}_{g,n}}\psi _1^{k_1}\mathrm{}\psi _n^{k_n}.$$
(2.1)
The symmetric group $`S_n`$ acts naturally on $`\overline{M}_{g,n}`$ by permuting the markings. Since the $`\psi `$ classes are permuted by this $`S_n`$ action, the integral (2.1) is unchanged by a permutation of the exponents $`k_i`$. A concise notation for these intersections which exploits the $`S_n`$ symmetry is given by:

$$\tau _{k_1}\mathrm{}\tau _{k_n}_g=_{\overline{M}_{g,n}}\psi _1^{k_1}\mathrm{}\psi _n^{k_n}.$$
(2.2)
Such products are well defined when the $`k_i`$ are non-negative integers and the dimension condition $`3g3+nk_i=0`$ holds. In all other cases, $`_{i=1}^n\tau _{k_i}_g`$ is defined to be zero. The empty product $`1_1`$ is also set to zero.

The simplest integral is

$$\tau _0^3_0=_{\overline{M}_{0,3}}\psi _1^0\psi _2^0\psi _3^0=1,$$

since $`\overline{M}_{0,3}`$ is a point. In fact, the genus 0 integrals are determined by the closed form :

$$\tau _{k_1}\mathrm{}\tau _{k_n}_0=\left(\genfrac{}{}{0pt}{}{n3}{k_1,\mathrm{},k_n}\right).$$
(2.3)
The first elliptic integral is $`\tau _1_1=1/24`$ which may be computed, for example, by studying a pencil of cubic plane curves.

A fundamental property of the integrals (2.2) is the string equation: for $`2g2+n>0`$,

$$\tau _0\underset{i=1}{\overset{n}{}}\tau _{k_i}_g=\underset{j=1}{\overset{n}{}}\tau _{k_j1}\underset{ij}{}\tau _{k_i}_g.$$

Equation (2.3) easily follows from the string equation and the evaluation $`\tau _0^3_0=1`$. A second property is the dilaton equation: for $`2g2+n>0`$,

$$\tau _1\underset{i=1}{\overset{n}{}}\tau _{k_i}_g=(2g2+n)\underset{i=1}{\overset{n}{}}\tau _{k_i}_g.$$

The string equation, dilaton equation, and the evaluation $`\tau _1_1=1/24`$ determine all the integrals (2.2) in genus 1.

Both the string and dilaton equations are derived from a comparison result describing the behavior of the $`\psi `$ classes under pull-back via the map

$$\pi :\overline{M}_{g,n+1}\overline{M}_{g,n}$$

forgetting the last point. Let $`i\{1,\mathrm{},n\}`$. The basic formula is:

$$\psi _i=\pi ^{}(\psi _i)+[D_i]$$
(2.4)
where $`D_i`$ is the boundary divisor in $`\overline{M}_{g,n}`$ with genus splitting $`g+0`$ and marking splitting $`\{1,\mathrm{},\widehat{i},\mathrm{},n\}\{i,n+1\}`$. That is, the general point of $`D_i`$ corresponds to a reducible curve $`C=C_1C_2`$ connected by a single node satisfying:

1. $`C_1`$ is nonsingular of genus $`g`$
2. $`C_2`$ is nonsingular of genus 0.
3. The markings $`\{1,\mathrm{},n\}\{i\}`$ lie on $`C_1`$ and the remaining marking $`\{i,n+1\}`$ lie on $`C_2`$.

The relation (2.4) implies the string and dilaton equations by a direct geometric argument (see, for example, ).

The KdV equations are differential equations satisfied by a generating series of the $`\psi `$ intersections. Let $`t`$ denote the set of variables $`\{t_i\}_{i=0}^{\mathrm{}}`$. Let $`\gamma =_{i=0}^{\mathrm{}}t_i\tau _i`$ be the formal sum. Consider the formal generating function for the integrals (2.2):

$$F_g(t)=\underset{n=0}{\overset{\mathrm{}}{}}\frac{\gamma ^n_g}{n!}.$$

The expression $`\gamma ^n_g`$ is defined by monomial expansion and multilinearity in the variables $`t_i`$. More concretely,

$`F_g(t)`$ $`=`$ $`{\displaystyle \underset{n1}{}}{\displaystyle \frac{1}{n!}}{\displaystyle \underset{k_1,\mathrm{},k_n}{}}\tau _{k_1}\mathrm{}\tau _{k_n}_gt_{k_1}\mathrm{}t_{k_n}`$
$`=`$ $`{\displaystyle \underset{\{n_i\}}{}}\tau _0^{n_0}\tau _1^{n_1}\tau _2^{n_2}\mathrm{}_g{\displaystyle \underset{i=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{t_i^{n_i}}{n_i!}},`$
where the last sum is over all sequences of nonnegative integers $`\{n_i\}`$ with finitely many nonzero terms. Let $`F`$ denote the full generating function:

$$F=\underset{g=0}{\overset{\mathrm{}}{}}F_g.$$

The genus subscript $`g`$ of a non-vanishing bracket $`\tau _{k_1}\mathrm{}\tau _{k_n}_g`$ is determined by the dimension condition $`3g3+n_{i=1}^nk_i=0.`$ Hence, $`F`$ is a faithful generating series of all the $`\psi `$ intersections in $`\overline{M}_{g,n}`$.

We will use the following notation for the derivatives of $`F`$:

$$\tau _{k_1}\tau _{k_2}\mathrm{}\tau _{k_n}=\frac{}{t_{k_1}}\frac{}{t_{k_1}}\mathrm{}\frac{}{t_{k_1}}F.$$
(2.5)
Note $`\tau _{k_1}\tau _{k_2}\mathrm{}\tau _{k_n}|_{t_i=0}=\tau _{k_1}\tau _{k_2}\mathrm{}\tau _{k_n}`$.

$`F`$ was conjectured by Witten to equal the free energy in $`2`$ dimensional quantum gravity and therefore to satisfy the KdV hierarchy. The classical KdV equation (first studied in the $`19^{th}`$ century to describe shallow water waves) is:

$$\frac{U}{t_1}=U\frac{U}{t_0}+\frac{1}{12}\frac{^3U}{t_0^3}.$$
(2.6)
Witten conjectured $`U=t_0t_0`$ satisfies (2.6). The KdV hierarchy for $`F`$ may be written in the following form (equation (2.6) is recovered in case $`n=1`$).

Witten’s Conjecture. For all $`n1`$,

$$(2n+1)\tau _n\tau _0^2=$$
(2.7)
$$\tau _{n1}\tau _0\tau _0^3+2\tau _{n1}\tau _0^2\tau _0^2+\frac{1}{4}\tau _{n1}\tau _0^4.$$

As an example, consider equation (2.7) for $`n=3`$ evaluated at $`t_i=0`$. We obtain:

$$7\tau _3\tau _0^2_1=\tau _2\tau _0_1\tau _0^3_0+\frac{1}{4}\tau _2\tau _0^4_0.$$

Use of the string equation yields:

$$7\tau _1_1=\tau _1_1\tau _0^3_0+\frac{1}{4}\tau _0^3_0.$$

Hence, we conclude $`\tau _1_1=1/24`$. The KdV equations (2.7) and the string equation together determine all the integrals (2.2) from $`\tau _0^3_0=1`$. Therefore, $`F`$ is uniquely determined by Witten’s conjecture.

#### 2.2 Kontsevich’s combinatorial model

We now explain the model found by Kontsevich for the generating series:

$$K_g(s_1,\mathrm{},s_n)=\underset{{\scriptscriptstyle k_i}=3g3+n}{}\tau _{k_1}\mathrm{}\tau _{k_n}_g\underset{i=1}{\overset{n}{}}\frac{(2k_i1)!!}{s_i^{2k_i+1}}$$
(2.8)
of $`\psi `$ intersections in $`\overline{M}_{g,n}`$.

Let $`\mathrm{\Sigma }_g`$ be an oriented topological surface of genus $`g`$. A *map* $`G`$ on $`\mathrm{\Sigma }_g`$ is a triple $`(V,E,\varphi )`$ satisfying the following conditions:

1. $`V\mathrm{\Sigma }_g`$ is a finite set of vertices,
2. $`E`$ is finite set of edges:

1. each edge is a simple path in $`\mathrm{\Sigma }_g`$ connecting two vertices of $`V`$,
    2. self-edges at vertices are permitted,
    3. distinct edge paths intersect only in vertices,
3. the graph $`G`$ is connected,
4. the complement of the union of the edges in $`\mathrm{\Sigma }_g`$ is a disjoint union of topological disks, called the *cells* of $`G`$,
5. $`\varphi `$ is a bijection of the set $`\mathrm{Cell}(G)`$ of cells with $`\{1,\mathrm{},|\mathrm{Cell}(G)|\}`$.

The origin of the term “map” is the following: one can visualize the cells of a map $`G`$ as different countries into which $`G`$ divides the surface $`\mathrm{\Sigma }_g`$.

The valence of a vertex $`v`$ is given by the number of half-edges incident to $`v`$. A map $`G`$ is called trivalent if every vertex has valence exactly 3. The map $`G`$ is called stable if

$$2g2+|\mathrm{Cell}(G)|>0.$$

Two maps $`G`$ and $`G^{}`$ on $`\mathrm{\Sigma }_g`$ are isomorphic if there is an orientation preserving homeomorphism of $`\mathrm{\Sigma }_g`$ which maps $`G`$ to $`G^{}`$ and respects $`\varphi `$. The automorphism group $`\text{Aut}(G)`$ is the finite group of symmetries of $`(V,E,\varphi )`$ induced by orientation preserving homeomorphisms of $`\mathrm{\Sigma }_g`$ that map $`G`$ to $`G`$ and respect the marking $`\varphi `$.

Let $`𝖦_{g,n}`$ denote the set of isomorphism classes of maps on $`\mathrm{\Sigma }_g`$ with $`n`$ cells and let $`𝖦_{g,n}^3𝖦_{g,n}`$ denote the subset of trivalent maps. The trivalent condition and the Euler characteristic constraint on $`G𝖦_{g,n}^3`$ imply:

$$|V|=\frac{2}{3}|E|,$$
(2.9)
$$|V|=2(2g2+n),$$
(2.10)
$`|E|`$, $`|V|`$ denote the cardinality of $`E`$ and $`V`$ respectively. It is then easy to see that $`𝖦_{g,n}^3`$ is a finite set. An example of an element of $`𝖦_{2,3}^3`$ is shown in Figure 1.

Let $`g0`$ and $`n`$ be fixed in the stable range $`2g2+n>0`$. Let the variables $`s_1,\mathrm{},s_n`$ correspond to the markings of $`G𝖦_{g,n}^3`$. Each edge $`eE`$ of $`G`$ borders two cells. Let $`i`$ and $`j`$ be the labels assigned by $`\varphi `$ to these cells. If both sides of $`e`$ border the same cell, then $`i=j`$. We denote

$$\stackrel{~}{s}(e)=s_i+s_j.$$

The fundamental result proven by Kontsevich is the following formula for $`K_g`$ in terms of combinatorics of trivalent maps:

###### Theorem 1.

$`K_g`$ is obtained by a sum over trivalent maps:

$$K_g(s_1,\mathrm{},s_n)=\underset{G𝖦_{g,n}^3}{}\frac{2^{2g2+n}}{|\text{Aut}(G)|}\underset{eE}{}\frac{1}{\stackrel{~}{s}(e)}.$$
(2.11)
Kontsevich’s proof requires a topological decomposition of $`\overline{M}_{g,n}`$ obtained via the theory of Strebel differentials (see , Appendix B). Aspects of the boundary behavior of this geometry are quite subtle. A discussion can also be found in .

### 3 Hurwitz numbers

#### 3.1 Three definitions of Hurwitz numbers

Three equivalent definitions of the Hurwitz numbers are discussed in this section. Definitions 3.1 and 3.2 will be used to provide a new proof of Theorem 1 connecting $`\psi `$ intersections in $`\overline{M}_{g,n}`$ to Kontsevich’s combinatorial model. Definition 3.3 relates the Hurwitz numbers to the combinatorics of the symmetric group and arises in the connection between Hurwitz numbers and the Toda equations in the Gromov-Witten theory of $`𝐏^1`$.

##### 3.1.1 Enumeration of branched coverings

We start with the definition of the Hurwitz numbers $`H_{g,\mu }`$ via covers of $`𝐏^1`$. Let $`g0`$ and let $`\mu `$ be a non-empty partition. Let $`|\mu |`$ denote the sum of the parts of $`\mu `$, and let $`\mathrm{}(\mu )`$ denote the length of $`\mu `$. A Hurwitz cover of $`𝐏^1`$ of genus $`g`$ and ramification $`\mu `$ over $`\mathrm{}`$ is a morphism

$$\pi :C𝐏^1$$

satisfying the following properties:

1. $`C`$ is a nonsingular, irreducible genus $`g`$ curve,
2. the divisor $`\pi ^1(\mathrm{})C`$ has profile equal to the partition $`\mu `$,
3. the map $`\pi `$ is simply ramified over $`𝐀^1=𝐏^1\mathrm{}`$.

Note that condition (ii) implies

$$\mathrm{deg}\pi =|\mu |.$$

By the Riemann-Hurwitz formula, the number of simple ramification points of $`\pi `$ over $`𝐀^1`$ is:

$$r(g,\mu )=2g2+|\mu |+\mathrm{}(\mu ).$$

Let $`U_r`$ denote a fixed set of $`r=r(g,\mu )`$ distinct points in $`𝐀^1`$ — it will be convenient for us to take $`U_r`$ equal to the set of $`r^{th}`$ roots of unity in $`=𝐀^1`$. We will require the simple ramification points of $`\pi `$ to lie over $`U_r`$.

Two covers

$$\pi :C𝐏^1,\pi ^{}:C^{}𝐏^1$$

are isomorphic if there exits an isomorphism of curves $`\varphi :CC^{}`$ satisfying $`\pi ^{}\varphi =\pi `$. Each cover $`\pi `$ has an naturally associated automorphism group $`\text{Aut}(\pi )`$.

###### Definition 3.1.

$`H_{g,\mu }`$ is a weighted count of the distinct Hurwitz covers $`\pi `$ of genus $`g`$ with ramification $`\mu `$ over $`\mathrm{}`$ and simple ramification over $`U_r`$. Each such cover is weighted by $`1/|\text{Aut}(\pi )|`$.

##### 3.1.2 Enumeration of branching graphs

The Hurwitz numbers admit a second definition via enumeration of graphs, see for example . Let $`g0`$ and $`\mu `$ be fixed. Let $`r=r(g,\mu )`$ and $`U_r=\{\zeta _1,\mathrm{},\zeta _r\}`$ be the set of $`r^{th}`$ roots of unity as above.

A *branching graph* $`H`$ on an oriented topological surface $`\mathrm{\Sigma }_g`$ consists of the data $`(V,E,\gamma :EU_r)`$ satisfying the following conditions:

1. the vertex set $`V\mathrm{\Sigma }_g`$ consists of $`|\mu |`$ distinct points,
2. the set $`E`$ consists of $`r`$ edges:

1. each edge is a simple path in $`\mathrm{\Sigma }_g`$ connecting two vertices of $`V`$,
    2. self-edges at vertices are not permitted,
    3. distinct edge paths intersect only in vertices,
3. the graph $`H`$ is connected,
4. the function $`\gamma `$ is a bijection,
5. at each vertex $`vV`$, the cyclic order of the edge markings (with respect to the orientation of $`\mathrm{\Sigma }_g`$) agrees with the cyclic order of the roots of unity (with respect to the standard orientation of $``$),
6. the complement of the union of the edges is a disjoint union of $`l=\mathrm{}(\mu )`$ topological disks $`D_1,\mathrm{},D_l`$.

Let $`D_i`$ be a cell bounded by the sequence of edges $`e_{12},\mathrm{},e_{s1}`$ of the graph $`H`$. Assume the edge circuit is clockwise with respect to the orientation of $`D_i`$ restricted from $`\mathrm{\Sigma }_g`$. Then, to each pair of edges $`e_{k1,k}`$, $`e_{k,k+1}`$ there is an associated positive angle given by:

$$\mathrm{}(e_{k1,k},e_{k,k+1})=\mathrm{arg}\left(\frac{\gamma (e_{k1,k})}{\gamma (e_{k,k+1})}\right)(0,2\pi ].$$

The sum of these angles along the boundary of $`D_i`$ is a multiple of $`2\pi `$. In other words, the following perimeter of the cell $`D_i`$

$$\mathrm{per}(D_i)=\frac{1}{2\pi }\underset{k=1}{\overset{s}{}}\mathrm{}(e_{k1,k},e_{k,k+1})$$

is a positive integer.

The cyclic ordering condition (v) implies that $`_{i=i}^l\mathrm{per}(D_i)=|\mu |`$. The last condition in the definition of a branching graph is:

1. The partition $`\mu `$ equals $`(\mathrm{per}(D_1),\mathrm{},\mathrm{per}(D_l))`$.

Two branching graphs $`H`$ and $`H^{}`$ on $`\mathrm{\Sigma }_g`$ are isomorphic if there exists an orientation preserving homeomorphism of $`\mathrm{\Sigma }_g`$ which maps $`H`$ to $`H^{}`$ and respects the edge markings. The automorphism group $`\text{Aut}(H)`$ is the finite group of symmetries of $`(V,E)`$ induced by orientation preserving homeomorphisms of $`\mathrm{\Sigma }_g`$ which map $`H`$ to $`H`$ and respect the edge markings.

Let $`𝖧_{g,\mu }`$ denote the set of isomorphism classes of genus $`g`$ branching graphs with perimeter $`\mu `$. The second definition of the Hurwitz numbers is by an enumeration of graphs:

###### Definition 3.2.

$`H_{g,\mu }`$ equals a weighted count of the branching graphs $`H`$ in $`𝖧_{g,\mu }`$, where each graph $`H`$ is weighted by $`1/|\text{Aut}(H)|`$.

Definition 3.2 can be seen to agree with Definition 3.1 by a direct association of a branching graph to each Hurwitz cover with ramification $`\mu `$. Let $`\pi :C𝐏^1`$ be a Hurwitz cover of genus $`g`$ with ramification $`\mu `$ over infinity and simple ramification over $`U_r`$. First, observe that $`\pi `$ is unramified over the open unit disk at the origin:

$$B=𝐀^1.$$

Therefore, $`\pi ^1(B)`$ is the disjoint union of exactly $`|\mu |`$ open disks

$$B_1,\mathrm{},B_{|\mu |}C.$$

Let $`\overline{B}_i`$ and $`B_i=\overline{B}_iB_i`$ denote the closure and the boundary of $`B_i`$ respectively.

Let $`q`$ be an intersection point of two different closed disks $`\overline{B}_i`$ and $`\overline{B}_j`$. Then $`q`$ must be a ramification point of $`\pi `$ and hence $`\pi (q)U_r`$. In fact, as $`\pi `$ is simply ramified over $`U_r`$, every element $`\zeta U_r`$ must lie under exactly one intersection of different closed disks. Therefore, there are exactly $`r`$ intersection points of pairs of closed disks $`Q=\{q_1,\mathrm{},q_r\}`$, in bijective correspondence $`\pi `$ with the set $`U_r`$.

Define a branching graph $`H=(V,E,\gamma :EU_r)`$ on the Riemann surface $`C`$ by the following data:

1. $`V=\pi ^1(0)`$,
2. the edge set $`E`$ corresponds to the intersection set $`Q`$,
3. the function $`\gamma :EU_r`$ is defined by the projection $`\pi :QU_r`$.

The edges $`E`$ are constructed as follows. Suppose

$$q=\overline{B}_i\overline{B}_j$$

and $`\zeta =\pi (q)`$. Let $`[0,\zeta ]`$ be the segment connecting $`0`$ to $`\zeta `$ in $`𝐀^1`$. The edge associated to $`q`$ is defined to be the unique component of $`\pi ^1([0,\zeta ])`$ that connects the centers of $`B_i`$ and $`B_j`$. The required conditions (i)-(vii) of a branching graph are easily checked.

Conversely, every branching graph on $`\mathrm{\Sigma }_g`$ with perimeter $`\mu `$ corresponds to a Hurwitz cover with ramification $`\mu `$ which can be obtained by reversing the above construction. The automorphism groups of the Hurwitz cover and of the branching graph coincide under this identification. We therefore conclude that Definitions 3.1 and 3.2 agree.

Figures 2 and 3 should help visualize the relationship between Definitions 3.1 and 3.2. Suppose we have a covering $`\pi `$ of $`𝐏^1`$ which satisfies the conditions of Definition 3.1, such as the one shown schematically in Figure 2.

In Figure 3, we see the preimage of the unit circle $`B`$ under $`\pi `$ consists of $`\mathrm{deg}\pi `$ disks which meet at the ramification points of $`\pi `$. Such points correspond bijectively under $`\pi `$ to the roots of unity. The centers of the disks form the vertices of the branching graph $`H`$, and the intersection points of the disks correspond to the edges of $`H`$. Since the edges of $`H`$ are labeled by roots of unity, we can define the angle between two edges and then the perimeters of the cells of $`H`$. In Figure 3, most edge labels of $`H`$ are omitted except on a small part of $`H`$ which is magnified.

##### 3.1.3 Counting factorizations into transpositions

A third approach to the Hurwitz numbers via the combinatorics of the symmetric group $`S_{|\mu |}`$ also plays a role in Gromov-Witten theory. A Hurwitz cover of genus $`g`$ with ramification $`\mu `$ over $`\mathrm{}`$ and simple ramification over $`U_r`$ can be associated to an ordered sequence of transpositions $`(\gamma _1,\mathrm{},\gamma _r)`$ of $`S_{|\mu |}`$ satisfying the following two properties:

1. $`\gamma _1,\mathrm{},\gamma _r`$ generate $`S_{|\mu |}`$,
2. the product $`\gamma _1\gamma _2\mathrm{}\gamma _r`$ has cycle structure $`\mu `$.

The associated Hurwitz cover is found by the following topological construction.

The fundamental group $`\pi _1(𝐀^1U_r)`$ is freely generated by the loops around the points $`U_r`$. Let

$$\stackrel{~}{𝐀^1U_r}$$

denote the universal cover of $`𝐀^1U_r`$. The sequence $`(\gamma _1,\mathrm{},\gamma _r)`$ defines an action of $`\pi _1(𝐀^1U_r)`$ on $`\{1,2,\mathrm{},|\mu |\}`$. This determines an unramified, $`|\mu |`$-sheeted covering space

$$\pi ^0:C^0𝐀^1U_r$$

defined by the mixing construction:

$$C^0=\stackrel{~}{𝐀^1U_r}\times _{\pi _1(𝐀^1U_r)}\{1,2,\mathrm{}|\mu |\}.$$

The covering $`C^0`$ is connected by condition (a). $`C^0`$ is naturally endowed with a complex structure and may be canonically completed to yield a Hurwitz cover $`\pi :C𝐏^1`$ of genus $`g`$ and ramification $`\mu `$ by condition (b). All Hurwitz covers of genus $`g`$ with ramification $`\mu `$ over $`\mathrm{}`$ and simple ramification over $`U_r`$ arise in this way. Therefore, the following definition of the Hurwitz numbers is equivalent to Definition 3.1

###### Definition 3.3.

$`H_{g,\mu }`$ equals $`1/|\mu |!`$ times the number of $`r`$-tuples of 2-cycles satisfying (a) and (b).

Formulas for $`H_{g,\mu }`$ in terms of the characters of the symmetric group were deduced by Burnside from this perspective. In fact, Hurwitz’s original computations of covering numbers were obtained via symmetric group calculations .

#### 3.2 Hurwitz numbers and the intersection theory of $`\overline{M}_{g,n}`$

The Hurwitz numbers are naturally expressed in terms of tautological intersections in $`\overline{M}_{g,n}`$. However, we will require here not only the $`\psi `$ classes arising in Witten’s conjecture, but also the $`\lambda `$ classes. Let the Hodge bundle

$$𝔼\overline{M}_{g,n}$$

be the rank $`g`$ vector bundle with fiber $`H^0(C,\omega _C)`$ over the moduli point $`(C,p_1,\mathrm{},p_n)`$. The $`\lambda `$ classes are the Chern classes of the Hodge bundle:

$$\lambda _i=c_i(𝔼)H^{2i}(\overline{M}_{g,n},).$$

The $`\psi `$ and $`\lambda `$ classes are tautological classes on the moduli space of curves. A foundational treatment of the tautological intersection theory of $`\overline{M}_{g,n}`$ can be found in  (see  for a current perspective).

Let $`\mu =(\mu _1,\mathrm{},\mu _l)`$ be a non-empty partition with positive parts. Let $`\text{Aut}(\mu )`$ denote the permutation group of symmetries of the parts of $`\mu `$. The Hurwitz numbers $`H_{g,\mu }`$ are related to the intersection theory of $`\overline{M}_{g,l}`$ by the following formula.

###### Theorem 2.

Let $`2g2+\mathrm{}(\mu )>0`$. The Hurwitz number $`H_{g,\mu }`$ satisfies:

$$H_{g,\mu }=\frac{(2g2+|\mu |+l)!}{|\text{Aut}(\mu )|}\underset{i=1}{\overset{l}{}}\frac{\mu _i^{\mu _i}}{\mu _i!}_{\overline{M}_{g,l}}\frac{_{k=0}^g(1)^k\lambda _k}{_{i=1}^l(1\mu _i\psi _i)}.$$
(3.1)
Theorem 2 was proven by T. Ekedahl, Lando, M. Shapiro, and Vainshtein  using a theory of twisted Segre classes for cone bundles over $`\overline{M}_{g,n}`$. In case $`\mu =1^d`$, the case of trivial ramification over $`\mathrm{}`$, formula (3.1) was independently found and proven in  via a direct integration in Gromov-Witten theory. This approach was later refined in  to yield the formula (3.1) for the general partition $`\mu `$.

The proof of  begins with an integral formula in Gromov-Witten theory for the Hurwitz numbers. Let $`\overline{M}_g(𝐏^1,d)`$ be the moduli space of stable maps of genus $`g`$ and degree $`d`$ to $`𝐏^1`$. There is branch morphism:

$$br:\overline{M}_g(𝐏^1,d)\text{Sym}^{2g2+2d}(𝐏^1)$$

which assigns to each stable maps $`f:C𝐏^1`$ the branch divisor in the target . Using Definition 1 of the Hurwitz numbers and properties of the virtual class, an integral formula

$$H_{g,1^d}=_{[\overline{M}_g(𝐏^1,d)]^{vir}}br^{}(\xi _p)$$
(3.2)
may be obtained. Here, $`\xi _p`$ is (the Poincaré dual) of the point class of $`\text{Sym}^{2g2+2d}(𝐏^1)`$.

Integrals in Gromov-Witten are evaluated against the virtual fundamental class of the moduli space of maps $`[\overline{M}_g(𝐏^1,d)]^{vir}`$. The moduli space of maps itself may be quite ill-behaved as all possible stable maps occur — including maps with reducible domains, collapsed components, and maps defined by special linear series. In general, $`\overline{M}_g(𝐏^1,d)`$ is reducible and of impure dimension. However, Gromov-Witten theory is based on the remarkably uniform behavior of the virtual class. Integrals against the virtual class are easier to understand than general intersections in the moduli space of maps.

The virtual localization formula of  provides a direct approach to the integral in (3.2). The moduli space $`\overline{M}_g(𝐏^1,d)`$ has a natural $`^{}`$-action induced by the standard $`^{}`$-action on $`𝐏^1`$. By construction, $`br^{}(\xi _p)`$ is seen to be an $`^{}`$-equivariant class. The $`^{}`$-fixed loci in $`\overline{M}_g(𝐏^1,d)`$ are well-known to be products of moduli spaces of pointed curves . The localization formula then precisely relates equivariant integrals against $`[\overline{M}_g(𝐏^1,d)]^{vir}`$ to tautological intersections in the moduli space of pointed curves. Formula (3.1) for $`\mu =1^d`$ is the result.

In case $`\mu `$ is arbitrary, the above strategy may be followed on an appropriate component of the moduli space

$$\overline{M}_g(𝐏^1,d(\mu )=|\mu |)$$

via an elegant localization analysis provided in .

Sections 5-6 contains a review of the Gromov-Witten theory of $`𝐏^1`$ and the virtual localization formula. The proof of Theorem 2 is presented in Section 7 following .

#### 3.3 Asymptotics of the Hurwitz numbers I: $`\psi `$ integrals

Let $`\mu `$ be a partition with $`l`$ parts $`\mu _1,\mathrm{},\mu _l`$ (assumed here to be distinct). Let $`N\mu `$ denote the partition obtained by scaling each part of $`\mu `$ by $`N`$. The asymptotics of $`H_{g,N\mu }`$ as $`N\mathrm{}`$ are easily related to the $`l`$-point function in $`2`$-dimensional quantum gravity by Theorem 2. After a Laplace transform, Kontsevich’s series (2.8) is found.

The $`l`$-point function $`P_g`$ is defined by the following equation (for $`2g2+l>0`$):

$$P_g(x_1,\mathrm{},x_l)=\underset{_ik_i=3g3+l}{}\tau _{k_1}\mathrm{}\tau _{k_l}_g\underset{i=1}{\overset{l}{}}x_i^{k_i}.$$
(3.3)
The $`l`$-point function $`P_g`$ contains the data of the full set of $`\psi `$ integrals on $`\overline{M}_{g,l}`$.

Define the function $`H_g(\mu _1,\mathrm{},\mu _l)`$ as the following limit:

$$H_g(\mu _1,\mathrm{},\mu _l)=\underset{N\mathrm{}}{lim}\frac{1}{N^{3g3+l/2}}\frac{H_{g,N\mu }}{e^{N|\mu |}r(g,N\mu )!},$$
(3.4)
A direct application of Theorem 2 together with Stirling’s formula (8.5) then yields the following result governing the asymptotics of the Hurwitz numbers.

###### Proposition 3.4.

We have:

$$H_g(\mu _1,\mathrm{},\mu _l)=\frac{1}{(2\pi )^{l/2}}\frac{1}{_{i=1}^l\mu _i^{1/2}}P_g(\mu _1,\mathrm{},\mu _l).$$

Let $`\mu `$ be a vector with distinct, positive, rational parts. The asymptotics of $`H_{g,N\mu }`$ are then well-defined over sufficiently divisible $`N`$, and Proposition 3.4 remains valid. It is natural to define $`H_g(x_1,\mathrm{},x_l)`$ for all positive real values by Proposition 3.4.

Let $`LH_g`$ denote the Laplace transform of the function $`H_g`$:

$`LH_g(y_1,\mathrm{},y_l)`$ $`=`$ $`{\displaystyle _{x_{>0}^l}}e^{yx}{\displaystyle \frac{1}{(2\pi )^{l/2}}}{\displaystyle \frac{1}{_{i=1}^lx_i^{1/2}}}P_g(x)𝑑x`$
$`=`$ $`{\displaystyle \underset{{\scriptscriptstyle k_i}=3g3+l}{}}\tau _{k_1}\mathrm{}\tau _{k_l}_g{\displaystyle \underset{i=1}{\overset{l}{}}}{\displaystyle \frac{(2k_i1)!!}{(2y_i)^{k_i+\frac{1}{2}}}}`$
The variable substitution $`s_i=\sqrt{2y_i}`$ relates the answer to Kontsevich’s model.

###### Theorem 3.

The Laplace transform of $`H_g`$ in the variables $`s_i`$ equals Kontsevich’s generating series for $`\psi `$ integrals:

$$LH_g(y_1,\mathrm{},y_l)=\underset{{\scriptscriptstyle k_i}=3g3+l}{}\tau _{k_1}\mathrm{}\tau _{k_l}_g\underset{i=1}{\overset{l}{}}\frac{(2k_i1)!!}{s_i^{2k_i+1}},s_i=\sqrt{2y_i}.$$

We have completed the path from Hurwitz numbers to $`\psi `$ integrals via Definition 1 and Gromov-Witten theory. The result after taking the appropriate asymptotics and the Laplace transform is Kontsevich’s series (2.8).

#### 3.4 Asymptotics of the Hurwitz numbers II: graph enumeration

Let $`\mu `$ be a partition with $`l`$ distinct parts as above. The asymptotics of the Hurwitz numbers $`H_{g,N\mu }`$ may be studied alternatively via Definition 3.2 and an analysis of graphs. The result after Laplace transform exactly equals Kontsevich’s sum over trivalent maps on $`\mathrm{\Sigma }_g`$ (2.11). The two approaches to the asymptotics of the Hurwitz numbers together yield a new proof of Theorem 1.

Let $`𝖦_{g,n}^3𝖦_{g,n}`$ denote the subset of maps with at least trivalent vertices. In case $`2g2+n>0`$, there exists a natural map

$$\mathrm{hmt}:𝖦_{g,n}𝖦_{g,n}^3$$

which we call the *homotopy type map*. It is constructed as follows.

First, given a map $`G𝖦_{g,n}`$ one repeatedly removes all univalent vertices from $`G`$ together with the incident edges until there are no more univalent vertices. After that, one removes all $`2`$-valent vertices by concatenating their incident edges. The resulting map is, by definition, $`\mathrm{hmt}(G)`$. It is clear that

$$|\mathrm{Cell}(G)|=|\mathrm{Cell}(\mathrm{hmt}(G))|.$$

By definition, two maps $`G`$ and $`G^{}`$ on $`\mathrm{\Sigma }_g`$ have the same homotopy type if $`\mathrm{hmt}(G)=\mathrm{hmt}(G^{})`$.

In case the parts of $`\mu `$ are distinct, there is a natural mapping

$$\mathrm{und}:𝖧_{g,\mu }𝖦_{g,\mathrm{}(\mu )}$$

from branching graphs to underlying maps which forgets the edge labels. The composition of $`\mathrm{und}`$ and $`\mathrm{hmt}`$ defines homotopy type and homotopy equivalence for branching graphs in $`𝖧_{g,\mu }`$. For example, the homotopy type $`G`$ corresponding to the branching graph $`H`$ from Figure 3 is shown in Figure 4.

Kontsevich’s combinatorial model is naturally found from the asymptotic enumeration of branching graphs by their homotopy type.

For any $`G𝖦_{g,l}^3`$, let $`H_{G,\mu }`$ denote the (weighted) number of branching graphs $`H`$ on $`\mathrm{\Sigma }_g`$ of homotopy type $`G`$. By Definition (3.2) of the Hurwitz numbers,

$$H_{g,N\mu }=\underset{G𝖦_{g,l}^3}{}H_{G,N\mu },$$

Since $`𝖦_{g,l}^3`$ is a finite set, we have

$$H_g(\mu _1,\mathrm{},\mu _l)=\underset{G𝖦_{g,l}^3}{}\underset{N\mathrm{}}{lim}\frac{1}{N^{3g3+l/2}}\frac{H_{G,N\mu }}{e^{N|\mu |}r(g,N\mu )!}.$$
(3.5)
The contribution of $`G`$ to (3.5) is determined by an asymptotic analysis in Section 9. If $`G`$ is not trivalent, the contribution vanishes. For trivalent graphs, the contribution of $`G`$ to (3.5) is found to equal, after the Laplace transform, the contribution of $`G`$ to (2.11). As a consequence, we obtain the following result:

###### Theorem 4.

The Laplace transform of $`H_g`$ in the variables $`s_i`$ equals a sum over trivalent graphs:

$$LH_g(y_1,\mathrm{},y_l)=\underset{G𝖦_{g,l}^3}{}\frac{2^{2g2+l}}{|\text{Aut}(G)|}\underset{eE}{}\frac{1}{\stackrel{~}{s}(e)},s_i=\sqrt{2y_i}.$$

Theorems 3 and 4 together provide a new proof of Theorem 1.

The analysis of Section 9 is based on the study of trees undertaken in Section 8. The (multivalued) inverse of the homotopy type map may be viewed as generating trees over the edges of $`G`$. The large $`N`$ asymptotics of $`H_{G,N\mu }`$ is thus governed by the theory of random trees.

### 4 Matrix models and integrable hierarchies

In this section we indicate several connections between the material in this paper and the theory of matrix models and integrable hierarchies. A more detailed treatment of this fundamentally important subject will be given in the sequel to this paper . Some references to existing literature are given below.

#### 4.1 Edge-of-the-spectrum matrix model

##### 4.1.1 Wick’s formula

Consider the linear space of all $`N\times N`$ Hermitian matrices and the Gaussian measure on it with density $`e^{\frac{1}{2}\mathrm{tr}M^2}`$. The expectations with respect to this measure will be denoted by

$$f_N=\frac{{\displaystyle f(M)\mathrm{exp}\left(\mathrm{tr}M^2/2\right)𝑑M}}{{\displaystyle \mathrm{exp}\left(\mathrm{tr}M^2/2\right)𝑑M}}.$$
(4.1)
It is clear that this measure has mean zero and its covariance matrix is easily found to be

$$M_{ij}M_{kl}_N=\{\begin{array}{cc}1,\hfill & (k,l)=(j,i),\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$
(4.2)
Expectations of any monomials in the $`M_{ij}`$’s can be computed using Wick’s rule: the expectation is a sum over all ways to group the factors in pairs of the products of the pair covariances. For example:

$$\begin{array}{c}M_{ab}M_{cd}M_{ef}M_{gh}=M_{ab}M_{cd}M_{ef}M_{gh}+\hfill \\ \hfill M_{ab}M_{ef}M_{cd}M_{gh}+M_{ab}M_{gh}M_{cd}M_{ef}=\\ \hfill \delta _{ad}\delta _{bc}\delta _{eh}\delta _{fg}+\delta _{af}\delta _{be}\delta _{ch}\delta _{dg}+\delta _{ah}\delta _{bg}\delta _{cf}\delta _{de}.\end{array}$$

The combinatorics of such expansions can be very conveniently handled using diagrammatic techniques (a very accessible introduction to this subject can be found in ).

For example, the diagrammatic interpretation of the expectation

$$\mathrm{tr}M^4_N=\underset{i,j,k,l=1}{\overset{N}{}}M_{ij}M_{jk}M_{kl}M_{li}_N$$

is the following. We place the indices $`i`$, $`j`$, $`k`$, $`l`$ on the vertices of a square and place the matrix elements $`M_{ij}`$, $`M_{jk}`$, $`M_{kl}`$, $`M_{li}`$ on the corresponding edges. The pairing in Wick’s formula can be interpreted as gluing pairs of sides of the square together. Formula (4.2) implies then that the side identifications have to satisfy:

* identified vertices carry equal indices,
* the result is a closed and orientable surface,

see Figure 5. Since each combinatorial scheme in Figure 5 contributes a power of $`N`$ for every vertex on the resulting surface, we conclude that

$$\mathrm{tr}M^4_N=2N^3+N.$$

Similarly, the expectation $`\mathrm{tr}M^k_N`$ can be diagrammatically interpreted as counting surfaces glued out of a $`k`$-gon.

##### 4.1.2 Asymptotics of maps on surfaces

More generally, an expectation of the form

$$\underset{j=1}{\overset{l}{}}\mathrm{tr}M^{k_i}_N$$

counts surfaces that one can glue out of a $`k_1`$-gon, $`k_2`$-gon, $`\mathrm{}`$, and a $`k_l`$-gon. More specifically, each polygon here comes with a choice of a special vertex because the monomial

$$M_{i_1i_2}M_{i_2i_3}\mathrm{}M_{i_ki_1}$$
(4.3)
corresponds to a $`k`$-gon diagram with factors $`M_{i_ri_{r+1}}`$ placed on its edges together with a choice of the vertex from which we start reading the word (4.3).

As a matter of fact, we have already encountered such a combinatorial structure under the name of a ”map”. Indeed, if a surface $`\mathrm{\Sigma }`$ is glued out of $`l`$ polygons, then the boundaries of the polygons form, according to the definition in Section 2.2, a map on the surface $`\mathrm{\Sigma }`$ with $`l`$ cells. It follows that:

$$\frac{1}{N^{|k|/2}}\underset{j=1}{\overset{l}{}}\mathrm{tr}M^{k_i}_N=\underset{\mathrm{\Sigma }}{}N^{\chi (\mathrm{\Sigma })l}\mathrm{Map}_\mathrm{\Sigma }(k_1,\mathrm{},k_l).$$
(4.4)
Here, $`|k|=k_i`$. The summation is over all orientable, but not necessarily connected, homeomorphism classes of surfaces $`\mathrm{\Sigma }`$. $`\mathrm{Map}_\mathrm{\Sigma }(k_1,\mathrm{},k_l)`$ is the number of maps $`G`$ on $`\mathrm{\Sigma }`$ satisfying:

1. $`G`$ is a map on $`\mathrm{\Sigma }`$ with $`l`$ cells marked by $`1,\mathrm{},l`$,
2. the perimeters of cells (in the usual graph metric) are $`k_1,k_2,\mathrm{},k_l`$,
3. on the boundary of each cell, one vertex is specified as the first vertex.

The isomorphisms of such objects are isomorphisms of the underlying maps which preserve the additional structure. The choice of a vertex at the boundary of each cell eliminates all nontrivial automorphisms.

As the function $`\mathrm{Map}_\mathrm{\Sigma }(k_1,\mathrm{},k_l)`$ vanishes unless $`|k|`$ is even, we will assume $`|k|`$ to be even. Also, as the enumeration of maps on disconnected surfaces is easily deduced from the connected case, we will study the function $`\mathrm{Map}_g`$ enumerating maps on the genus $`g`$ connected surface $`\mathrm{\Sigma }_g`$.

Consider now the limit as the $`k_i`$’s increase to infinity at fixed relative rates. In other words, introduce an extra parameter $`\kappa `$ and assume that

$$\frac{k_i}{\kappa }x_i,\kappa \mathrm{}.$$

The following limit

$$\mathrm{map}_g(x_1,\mathrm{},x_l)=\underset{\kappa \mathrm{}}{lim}\frac{\mathrm{Map}_g(k_1,\mathrm{},k_l)}{2^{|k|}\kappa ^{3g3+3l/2}}$$
(4.5)
was computed in  and, by comparison with Kontsevich’s combinatorial model, it was observed that

$$P_g(x_1,\mathrm{},x_l)=\frac{\pi ^{l/2}}{2^g}\frac{\mathrm{map}_g(2x_1,\mathrm{},2x_l)}{\sqrt{x_1\mathrm{}x_l}},$$
(4.6)
where $`P_g`$ denotes the $`l`$-point function defined in Section 3.3.

Comparing Proposition 3.4 to (4.6), we find the asymptotics of the enumeration of branching graphs $`𝖧_{g,\mu }`$ and the asymptotics of map enumeration by $`\mathrm{Map}_g(k_1,\mathrm{},k_l)`$ are closely related. Each branching graph determines an underlying map by forgetting edge labels (see Section 3.4). The branching graph of Figure 3 determines the map shown in Figure 6.

The function from branching graphs to underlying maps destroys the perimeter data of the branching graph. However, the asymptotic behavior of perimeters is governed by basic principles which apply for both the branching graphs and the underlying maps. Borrowing terminology from statistical physics, the enumeration of branchings graphs by their perimeters and the enumeration of maps by their perimeters belong to the same universality class. This universality class is quite large (see, for example, ). Another classical combinatorial problem in the same universality class is the problem of increasing subsequences in a random permutation, see . The methods that we use in Sections 8 and 9 to analyze the asymptotics of the Hurwitz numbers are parallel to the methods used in  for the asymptotic enumeration of maps.

In the case of branching graphs, the asymptotics is related to the intersection theory of $`\overline{M}_{g,n}`$ by Proposition 3.4. Therefore, a conceptual explanation of relation (4.6) is obtained (complementing the derivation of ).

##### 4.1.3 Edge of the spectrum

The asymptotic function $`\mathrm{map}_g`$ has a natural extension $`\mathrm{map}_\mathrm{\Sigma }`$ to disconnected surfaces $`\mathrm{\Sigma }`$ which satisfies the obvious multiplicativity in connected components. Formulas (4.4) and (4.5) together imply, provided each $`k_i`$ is even, the limit:

$$\underset{j=1}{\overset{l}{}}\mathrm{tr}\left(\frac{M}{2\sqrt{N}}\right)^{k_i}_N\underset{\mathrm{\Sigma }}{}\mathrm{map}_\mathrm{\Sigma }(x_1,\mathrm{},x_l),$$
(4.7)
as $`N\mathrm{}`$ and $`k_i\mathrm{}`$ in such a way that

$$\frac{k_i}{N^{2/3}}x_i.$$

In case some of the $`k_i`$ are odd, certain distributions of the $`k_i`$ between the connected pieces of $`\mathrm{\Sigma }`$ become prohibited by parity and, consequently, the corresponding terms in (4.7) should be omitted.

It is well known (see ) that, as $`N\mathrm{}`$, the eigenvalue distribution of the scaled matrix $`{\displaystyle \frac{M}{2\sqrt{N}}}`$ converges to the (non-random) semicircle law with density

$$\frac{2}{\pi }\sqrt{1x^2}dx,x[1,1].$$

It is clear that the eigenvalues near the edges $`\pm 1`$ of the spectrum make the maximal contribution to the traces of large powers of $`M/2\sqrt{N}`$ in (4.7). This is why we call the matrix model (4.7) the edge-of-the-spectrum matrix model.

The behavior of eigenvalues near the edges $`\pm 1`$ in the $`N\mathrm{}`$ limit is very well studied, see for example . Let $`\rho (x_1,\mathrm{},x_l;N)`$ denote the $`l`$-point correlation function for the eigenvalues of $`M/2\sqrt{N}`$. By definition, $`\rho (x_1,\mathrm{},x_l;N)dx_i`$ is the probability of finding an eigenvalue in each of the infinitesimal intervals $`[x_i,x_i+dx_i]`$. These correlation functions have the following $`N\mathrm{}`$ asymptotics

$$N^{2l/3}\rho (1+\frac{x_1}{N^{2/3}},\mathrm{},1+\frac{x_l}{N^{2/3}})det\left[𝖪_{\text{Ai}}(x_i,x_j)\right]_{1i,jl},$$
(4.8)
where $`𝖪_{\text{Ai}}`$ is the following kernel involving the classical Airy function

$$𝖪_{\text{Ai}}(x,y)=\frac{\mathrm{Ai}(2x)\mathrm{Ai}^{}(2y)\mathrm{Ai}^{}(2x)\mathrm{Ai}(2y)}{xy}.$$

The formula (4.8) together with (4.6) results in a closed Gaussian integral formula for the $`l`$-point function $`P_g`$, see . It also shows that the appearance of Airy functions in both (4.8) and  is not a coincidence.

Another application of the edge-of-the-spectrum matrix model is the following. After Kontsevich’s combinatorial formula (2.11) is established, the derivation of Witten’s KdV equations requires an additional analysis. Kontsevich’s original approach was to study an associated matrix integral (Kontsevich’s matrix model) which will be discussed in Section 4.2. Alternatively, one can deduce, as was done in , the KdV equations using the edge-of-the-spectrum model and the the work of Adler, Shiota, and van Moerbeke .

#### 4.2 Kontsevich’s matrix model

Let $`\mathrm{\Lambda }`$ be a diagonal $`N\times N`$ matrix with positive real eigenvalues $`s_1,\mathrm{},s_N`$. Instead of the Gaussian measure (4.1) one can consider a more general Gaussian measure on the space of Hermitian $`N\times N`$ matrices $`M`$ with density $`e^{\frac{1}{2}\mathrm{tr}\mathrm{\Lambda }M^2}`$. We denote expectations of a function $`f(M)`$ respect to this measure by

$$f_{N,\mathrm{\Lambda }}=\frac{{\displaystyle f(M)\mathrm{exp}\left(\mathrm{tr}\mathrm{\Lambda }M^2/2\right)𝑑M}}{{\displaystyle \mathrm{exp}\left(\mathrm{tr}\mathrm{\Lambda }M^2/2\right)𝑑M}}$$

The covariance matrix of this Gaussian measure is easily found to be:

$$M_{ij}M_{kl}_{N,\mathrm{\Lambda }}=\{\begin{array}{cc}\frac{2}{s_i+s_j},\hfill & (k,l)=(j,i),\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$

Expectations of any monomials in the $`M_{ij}`$ can be again computed using Wick’s rule.

Kontsevich’s matrix integral $`\mathrm{\Theta }_N`$ is defined by:

$$\mathrm{\Theta }_N(s_1,\mathrm{},s_N)=\mathrm{exp}\left(\frac{i}{6}\mathrm{tr}M^3\right)_{N,\mathrm{\Lambda }}.$$
(4.9)
Expanding the exponential by Taylor series and applying Wick’s formula leads to the expansion:

$$\text{log}\mathrm{\Theta }_N(s_1,\mathrm{},s_N)=\underset{g0}{}\underset{n1}{}(2)^{2g2+n}\underset{G𝖦_{g,n}^3(N)}{}\frac{1}{|\text{ Aut}(G)|}\underset{eE}{}\frac{1}{\stackrel{~}{s}(e)},$$
(4.10)
where $`𝖦_{g,n}^3(N)`$ denotes the set of trivalent maps with $`n`$ marked cells labeled by a subset of the numbers $`\{1,2,\mathrm{},N\}`$. The logarithm function in (4.10) has the effect of selecting only connected diagrams.

A change of variables is required to relate $`\mathrm{\Theta }_N`$ to the free energy $`F`$ arising in Witten’s conjectures. Let $`t^N`$ denote the variable set $`\{t_i^N\}_{i=0}^{\mathrm{}}`$. For $`i0`$, let

$$t_i^N=\underset{k=1}{\overset{N}{}}\frac{(2i1)!!}{s_k^{2i+1}}.$$
(4.11)
Substitution into $`F`$ yields:

$`F(t^N)`$ $`=`$ $`{\displaystyle \underset{n1,k_1,\mathrm{},k_n}{}}{\displaystyle \frac{1}{n!}}\tau _{k_1}\mathrm{}\tau _{k_n}t_{k_1}^N\mathrm{}t_{k_n}^N`$
$`=`$ $`{\displaystyle \underset{n1,k_1,\mathrm{},k_n}{}}{\displaystyle \frac{(1)^n}{n!}}\tau _{k_1}\mathrm{}\tau _{k_n}{\displaystyle \underset{1l_1,\mathrm{},l_nN}{}}{\displaystyle \underset{i=1}{\overset{n}{}}}{\displaystyle \frac{(2k_i1)!!}{s_{l_i}^{2k_i1}}}`$
$`=`$ $`{\displaystyle \underset{g0}{}}{\displaystyle \underset{n1}{}}(2)^{2g2+n}{\displaystyle \underset{G𝖦_{g,n}^3(N)}{}}{\displaystyle \frac{1}{|\text{ Aut}(G)|}}{\displaystyle \underset{eE}{}}{\displaystyle \frac{1}{\stackrel{~}{s}(e)}},`$
The last equality is a consequence of Theorem 1. Therefore,

$$F(t^N)=\text{log}\mathrm{\Theta }_N(s_1,\mathrm{},s_N).$$

As $`N\mathrm{}`$, the change of variables (4.11) is faithful to higher and higher orders. The entire function $`F`$ may be recovered in the large $`N`$ limit.

###### Theorem 5.

$`F`$ is the large $`N`$ limit of Kontsevich’s matrix model:

$$F(t)=\underset{N\mathrm{}}{lim}\mathrm{\Theta }_N(t^N).$$

Witten’s KdV equations for $`F`$ are proven in  from the analysis of Kontsevich’s matrix integral. An exposition of this analysis can be found in .

#### 4.3 Matrix models of $`2`$-dimensional quantum gravity

In quantum gravity, one wishes to compute a Feynman integral of matter fields over all possible topologies and metrics on a 2-dimensional worldsheet. One way to make mathematical sense out of such integration is to interpret the result as a suitable integral over the moduli spaces of curves, see . Another approach is to discretize the problem: instead of all possible metrics one can consider, for example, only surfaces tessellated into standard squares, or into more general polygons. In a suitable limit, in which the number of tiles goes to infinity, one expects to be able to compute physically significant quantities from this approximations.

Diagrammatic techniques for matrix integrals provide a very powerful tool for enumerating tessellations and investigating their asymptotic behavior (see, for example, the surveys  as well the original papers . More concretely, consider an integral over the space of $`N\times N`$ Hermitian matrices of the following form

$$Z(V,N)=e^{N\mathrm{tr}V(M)}𝑑M$$

where

$$V(x)=\frac{1}{2}x^2+\gamma (x)[x]$$

is a polynomial (usually assumed to be even). After an expansion by Wick’s formula, $`Z(V,N)`$ yields a weighted enumeration of surfaces tessellated into polygons. The weight involves the genus of the surface, the automorphisms group of the tessellation, and the coefficients of the polynomial $`V`$ corresponding to the tiles of the tessellation.

The physically interesting limit (the double scaling limit) is obtained when the coefficients of the polynomial $`V`$ approach certain critical values simultaneously as $`N\mathrm{}`$. Formal manipulation with asymptotics of orthogonal polynomials shows that this limit is governed by the KdV hierarchy, see for example  for a survey. This is precisely what led Witten to conjecture that the same hierarchy describes intersections on the moduli spaces of curves.

However, rigorous mathematical investigation of the corresponding double-scaling asymptotics of orthogonal polynomials is a very difficult problem. At present, only the case of even quartic potential $`V`$ has been analyzed completely . In this respect, the matrix integral $`Z(V,N)`$, is a much more problematic object than Kontsevich’s matrix model or the edge of the spectrum matrix model.

#### 4.4 The Toda equation for $`𝐏^1`$

The moduli space $`\overline{M}_{g,n}`$ may be viewed as the moduli space of maps to a point. The Hurwitz path to matrix models is found in the geometry of maps to $`𝐏^1`$. It is perhaps natural then to seek a link between the Gromov-Witten theory of target varieties $`X`$ and matrix models via the geometry of maps to $`X\times 𝐏^1`$. While this direction has promise, no constructions have yet been found even for $`X=𝐏^1`$.

Instead, the study of the Gromov-Witten theory of the target variety $`X=𝐏^1`$ is again linked to the Hurwitz numbers. The Toda equation (conjecturally) constrains the free energy $`F`$ of $`𝐏^1`$. The generating series $`H`$ of the Hurwitz numbers has been proven to satisfy an analogous Toda equation via a representation theoretic analysis of $`H_{g,\mu }`$ . The functions $`F`$ and $`H`$ may be partially identified through the basic Hurwitz numbers $`H_{g,1^d}`$ . The two Toda equations agree in this region of overlap.

We explain here the basic relationship between the Gromov-Witten theory of $`𝐏^1`$, the Hurwitz numbers, and the Toda equation. The tautological classes in $`H^{}(\overline{M}_{g,n}(𝐏^1,d),)`$ which we will consider are of two types. First, the classes $`\psi _i`$ are defined on the moduli space $`\overline{M}_{g,n}(𝐏^1,d)`$ by the same construction used for $`\overline{M}_{g,n}`$: $`\psi _i`$ is the Chern class of the $`i^{th}`$ cotangent line bundle. The tautological evaluation maps,

$$\text{ev}_j:\overline{M}_{g,n}(𝐏^1,d)𝐏^1,$$

defined for each marking $`j`$ provide a structure not present in the study of $`\overline{M}_{g,n}`$. The second type of tautological class is:

$$\text{ev}_j^{}(\omega )H^2(\overline{M}_{g,n}(𝐏^1,d),),$$

where $`\omega H^2(𝐏^1,)`$ is the point class. The intersections of products of $`\psi _i`$ and $`\text{ev}_j^{}(\omega )`$ in $`\overline{M}_{g,n}(𝐏^1,d)`$ are the gravitational descendents of $`𝐏^1`$. The bracket notation for the descendent integrals is:

$$\underset{i=1}{\overset{r}{}}\tau _{a_i}\underset{j=r+1}{\overset{r+s}{}}\tau _{b_j}(\omega )_{g,d}^{𝐏^1}=_{[\overline{M}_{g,n}(𝐏^1,d)]^{vir}}\underset{i=1}{\overset{r}{}}\psi _i^{a_i}\underset{j=r+1}{\overset{r+s}{}}\psi _j^{b_j}\text{ev}_j^{}(\omega ).$$
(4.12)
All integrals in Gromov-Witten theory are evaluated against the virtual fundamental class.

The free energy $`F`$ of $`𝐏^1`$ is a complete generating function of the integrals (4.12). Let the variables $`x_i`$ and $`y_j`$ correspond to the classes $`\psi _i`$ and $`\text{ev}_j^{}(\omega )`$. Let $`x`$ and $`y`$ denote the sets of variables $`\{x_i\}_{i=0}^{\mathrm{}}`$ and $`\{y_i\}_{i=0}^{\mathrm{}}`$ respectively. $`F`$ is defined by the formula:

$$F(\lambda ,x,y)=\underset{g0}{}\underset{d0}{}\underset{n0}{}\lambda ^{2g2}\frac{\gamma ^n_{g,d}^{𝐏^1}}{n!},$$
(4.13)
where $`\gamma =_{i0}x_i\tau _i+y_i\tau _i(\omega )`$. The bracket in (4.13) is viewed as linear in the variables $`x`$ and $`y`$.

The (conjectural) Toda equation for $`F`$ may be written in the following form:

$$\mathrm{exp}\left(F(x_0+\lambda )+F(x_0\lambda )2F\right)=\lambda ^2F_{y_0y_0},$$
(4.14)
where $`F(x_0\pm \lambda )=F(\lambda ,x_0\pm \lambda ,x_1,x_2,\mathrm{},y_0,y_1,y_2,\mathrm{}).`$ Equation (4.14) has its origins in the study of matrix models believed to be related to the Gromov-Witten theory of $`𝐏^1`$ . Proofs of the genus 0 and 1 implications of the Toda equation can be found in . The Toda equation (4.14) determines $`F`$ from degree $`d=0`$ descendent invariants of $`𝐏^1`$.

A very similar Toda equation holds for the generating function of the Hurwitz numbers $`H_{g,\mu }`$. Let $`p`$ denotes the variable set $`\{p_i\}_{i=1}^{\mathrm{}}`$. For each partition $`\mu `$ of $`d`$ with parts $`\mu _1,\mathrm{},\mu _l`$, let

$$p_\mu =p_{\mu _1}\mathrm{}p_{\mu _l}.$$

Define the Hurwitz generating function $`H`$ by:

$$H(\lambda ,y_0,p)=\underset{g0}{}\underset{d>0}{}\underset{\mu d}{}\lambda ^{2g2}e^{dy_0}\frac{H_{g,\mu }}{(2g2+d+l)!}p_\mu .$$

The definition of the Hurwitz numbers via the symmetric group in Section 3.1 may be used to prove a Toda equation for $`H`$. More precisely, the function $`H`$ is linked to the Toda lattice hierarchy of Takasaki and Ueno in representation theory . One specialization of this hierarchy is the following:

###### Proposition 4.1.

$`H`$ satisfies the Toda equation:

$$\mathrm{exp}\left(H(y_0+\lambda )+H(y_0\lambda )2H\right)=\lambda ^2e^{y_0}H_{p_1y_0}.$$
(4.15)
The Toda equations for the free energy $`F`$ and the Hurwitz function $`H`$ are connected through a partial identification of these two series. Perhaps the Toda equation for $`F`$ could be proven by a better understanding of this relationship.

Let $`H_{g,d}`$ be the Hurwitz number of genus $`g`$, degree $`d`$, simply ramified covers of $`𝐏^1`$. By definition, $`H_{g,d}`$ equals $`H_{g,1^d}`$. The generating function $`\stackrel{~}{H}`$ of the Hurwitz numbers $`H_{g,d}`$ is obtained by a restriction of $`H`$:

$`\stackrel{~}{H}(\lambda ,y_0)`$ $`=`$ $`{\displaystyle \underset{g0}{}}{\displaystyle \underset{d>0}{}}\lambda ^{2g2}e^{dy_0}{\displaystyle \frac{H_{g,d}}{(2g2+2d)!}}`$
$`=`$ $`H(\lambda ,y_0,p_1=1,p_{i2}=0).`$
The Hurwitz numbers $`H_{g,d}`$ arise in Gromov-Witten theory as descendent integrals of $`𝐏^1`$ .

###### Proposition 4.2.

For all $`g0`$ and $`d>0`$,

$$H_{g,d}=\tau _1(\omega )^{2g+2d2}_{g,d}^{𝐏^1}.$$

The generating function $`\stackrel{~}{H}`$ is therefore obtained by a restriction of $`F`$:

$`\stackrel{~}{H}(\lambda ,y_0)`$ $`=`$ $`{\displaystyle \underset{g0}{}}{\displaystyle \underset{d>0}{}}\lambda ^{2g2}e^{dy_0}{\displaystyle \frac{\tau _1(\omega )^{2g+2d2}_{g,d}^{𝐏^1}}{(2g2+2d)!}}`$
$`=`$ $`F(\lambda ,x_{i0}=0,y_0,y_1=1,y_{i2}=0).`$
There are two natural Toda equations for $`\stackrel{~}{H}`$ obtained from the Toda equations for $`F`$ and $`H`$ respectively.

###### Theorem 6.

The two Toda equations (4.14) and (4.15) specialize to a unique Toda equation for $`\stackrel{~}{H}`$:

$$\mathrm{exp}\left(\stackrel{~}{H}(y_0+\lambda )+\stackrel{~}{H}(y_0\lambda )2\stackrel{~}{H}\right)=\lambda ^2e^{y_0}\stackrel{~}{H}_{y_0y_0}.$$
(4.16)
Theorem 6 provides strong evidence for the (conjectural) Toda equation for $`F`$.

The Toda equation for the Hurwitz series $`H`$ was found in the search for a proof of prediction (4.16) of the Toda equation for $`𝐏^1`$. One may reasonably hope the connection between the Toda equations for $`H`$ and $`F`$ is stronger than Theorem 6. However, a direct extension of Proposition 4.2 relating all the Hurwitz numbers $`H_{g,\mu }`$ to descendents has not been discovered. The natural context for the Toda equation in  suggests the larger class of double Hurwitz numbers may be related fundamentally to the Gromov-Witten theory of $`𝐏^1`$.

## Part II Hurwitz numbers in Gromov-Witten theory

### 5 Gromov-Witten theory of $`𝐏^1`$

#### 5.1 Stable maps

Let $`X`$ be a nonsingular projective variety. A path integral over the space of differential maps $`\pi :\mathrm{\Sigma }_gX`$ naturally arises in the topological gravity theory with target $`X`$. A stationary phase analysis then yields the following string theoretic result: the path integral localizes to the space of holomorphic maps from Riemann surfaces to $`X`$ . The path integral therefore should be equivalent to classical integration over a space of holomorphic maps.

The moduli of maps may be studied in algebraic geometry by the equivalence of the holomorphic and algebraic categories in complex dimension 1. However, the moduli space $`M_{g,n}(X,\beta )`$ of $`n`$-pointed algebraic maps $`\pi :(C,p_1,\mathrm{},p_n)X`$ satisfying

1. $`C`$ is a nonsingular curve of genus $`g`$,
2. $`p_1,\mathrm{},p_nC`$ are distinct points,
3. $`\pi _{}[C]=\beta H_2(X,)`$,

is not compact. For example, the domain may degenerate to a nodal curve, the points may meet, or the map itself may acquire a singularity. The compactification

$$M_{g,n}(X,\beta )\overline{M}_{g,n}(X,\beta )$$

by stable maps plays a central role in Gromov-Witten theory — it is conjectured to be the correct compactification for calculating the path integral of the gravity theory.

The moduli space of stable maps $`\overline{M}_{g,n}(X,\beta )`$ parameterizes $`n`$-pointed algebraic maps

$$\pi :(C,p_1,\mathrm{},p_n)X$$

satisfying:

1. $`C`$ is a compact, connected, reduced, (at worst) nodal curve of arithmetic genus $`g`$,
2. $`p_1,\mathrm{},p_nC`$ are distinct and lie in the nonsingular locus,
3. $`\pi _{}[C]=\beta `$,
4. $`\pi `$ has no infinitesimal automorphisms.

A special point of the domain $`C`$ is a marked point $`p_i`$ or a nodal point. An infinitesimal automorphism of a map $`\pi `$ is a tangent field $`v`$ of the domain $`C`$ which vanishes at the special points and satisfies $`d\pi (v)=0`$. Stable maps were defined by Kontsevich in . A construction of the moduli space can be found in .

An irreducible component $`EC`$ is $`\pi `$-collapsed if the image $`\pi (E)`$ is a point. Property (iv) is equivalent to a geometric condition on each $`\pi `$-collapsed component: $`\pi `$ has no infinitesimal automorphisms if and only if the normalization

$$\stackrel{~}{E}E$$

of each $`\pi `$-collapsed component $`E`$ contains the preimages of at least $`32g(\stackrel{~}{E})`$ special points of $`C`$. As $`32g(\stackrel{~}{E})>0`$ only if $`g(\stackrel{~}{E})=0`$ or $`1`$, this condition only constrains rational and elliptic components. If the entire domain $`C`$ is $`\pi `$-collapsed, property (iv) is equivalent to the Deligne-Mumford stability condition for pointed curves $`(C,p_1,\mathrm{},p_n)`$. The moduli space $`\overline{M}_{g,n}(X,0)`$ is therefore isomorphic to $`X\times \overline{M}_{g,n}`$. In particular, $`\overline{M}_{g,n}`$ is recovered as the space of stable maps to a point.

The moduli space $`\overline{M}_{g,n}(X,\beta )`$ is not always a nonsingular Deligne-Mumford stack — in fact, the space may be singular, non-reduced, reducible, and of impure dimension. While $`M_{g,n}(X,\beta )\overline{M}_{g,n}(X,\beta )`$ is an open subset, the inclusion is not necessarily dense. The space of stable maps may be quite complicated even when $`M_{g,n}(X,\beta )`$ is empty.

Most pathologies occur even in case $`X=𝐏^1`$. Consider, for example, $`\overline{M}_2(𝐏^1,2)`$. The closure of the locus of hyperelliptic maps $`M_2(𝐏^1,2)`$ yields an irreducible component of $`\overline{M}_2(𝐏^1,2)`$ of dimension 6. However, the set of maps obtained by attaching a $`\pi `$-collapsed genus 2 curve to a rational double cover of $`𝐏^1`$ forms another component of dimension 7. In fact, $`\overline{M}_2(𝐏^1,2)`$ contains 7 irreducible components in all. One of the few global geometric properties always satisfied by $`\overline{M}_{g,n}(𝐏^1,d)`$ is connectedness .

#### 5.2 Branch morphisms

Let $`g0`$ and $`d>0`$. The moduli space $`\overline{M}_g(𝐏^1,d)`$ supports a natural branch morphism $`br`$ which will play a basic role in the study of the Hurwitz numbers.

The branch morphism is first constructed for the open moduli space $`M_g(𝐏^1,d)`$. Let $`\pi :C𝐏^1`$ be a degree $`d`$ map with a nonsingular domain $`C`$. A branch divisor on $`𝐏^1`$ is obtained from the ramifications of $`\pi `$. More precisely, the branch divisor $`br(\pi )`$ is the $`\pi `$ push-forward of the degeneracy locus of the differential map on $`C`$:

$$\pi ^{}\omega _{𝐏^1}\omega _C,$$
(5.1)
where $`\omega _{𝐏^1}`$ and $`\omega _C`$ denote the canonical bundles of $`𝐏^1`$ and $`C`$ respectively. By the Riemann-Hurwitz formula, $`br(\pi )`$ has degree

$$r=2g(C)2+2d.$$

A branch morphism from $`M_g(𝐏^1,d)`$ to the space of divisors,

$$br:M_g(𝐏^1,d)\text{Sym}^r(𝐏^1),$$
(5.2)
is defined algebraically by the universal degeneracy locus (5.1).

A branch divisor $`br(\pi )`$ is constructed for stable maps $`\pi :C𝐏^1`$ by the following definition. Let $`NC`$ be the cycle of nodes of $`C`$. Let $`\nu :\stackrel{~}{C}C`$ be the normalization of $`C`$. Let $`A_1,\mathrm{},A_a`$ be the components of $`\stackrel{~}{C}`$ which dominate $`𝐏^1`$, and let $`\{a_i:A_i𝐏^1\}`$ denote the natural maps. As $`a_i`$ is a surjective map between nonsingular curves, the branch divisor $`br(a_i)`$ is defined by (5.1). Let $`B_1,\mathrm{},B_b`$ be the components of $`\stackrel{~}{C}`$ contracted over $`𝐏^1`$, and let $`f(B_j)=q_j𝐏^1`$. Define $`br(\pi )`$ by:

$$br(\pi )=\underset{i}{}br(a_i)+\underset{j}{}(2g(B_j)2)[q_j]+2\pi _{}(N).$$
(5.3)
Formula (5.3) associates an effective divisor of degree $`r`$ on $`𝐏^1`$ to every moduli point $`[\pi ]\overline{M}_g(𝐏^1,d)`$.

The branch divisor $`br(\pi )`$ for stable maps may be constructed canonically from the complex:

$$R\pi _{}[\pi \omega _{𝐏^1}\omega _C],$$
(5.4)
well-defined in the derived category. An effective divisor on $`𝐏^1`$ is extracted from (5.4) via a determinant construction. An algebraic branch morphism

$$br:\overline{M}_g(𝐏^1,d)\text{Sym}^r(𝐏^1)$$
(5.5)
is then obtained from the universal complex (5.4). The required derived category arguments can be found in .

#### 5.3 Virtual classes

##### 5.3.1 Perfect obstruction theories

Let $`X`$ be a nonsingular projective variety. The expected or virtual dimension of the moduli space $`\overline{M}_{g,n}(X,\beta )`$ is:

$$_\beta c_1(X)+\text{dim}(X)(1g)+3g3+n.$$

$`\overline{M}_{g,n}(X,\beta )`$ carries a canonical obstruction theory which yields a virtual class

$$[\overline{M}_{g,n}(X,\beta )]^{vir}A_{\text{exp}}(\overline{M}_{g,n}(X,\beta ),)$$

in the expected rational Chow group. The virtual class of $`\overline{M}_{g,n}(X,\beta )`$ was first constructed in . The virtual class plays a fundamental role in Gromov-Witten theory — all cohomology evaluations in the theory are taken against the virtual class.

The virtual class of $`\overline{M}_{g,n}(X,\beta )`$ is constructed via a canonical perfect obstruction theory carried by the moduli of maps. A perfect obstruction theory on scheme (or Deligne-Mumford stack) $`V`$ consists of the following data:

1. A two term complex of vector bundles $`E^{}=[E^1E^0]`$ on $`V`$.
2. A morphism $`\varphi :E^{}L_V^{}`$ in the derived category $`D_{qcoh}^{}(V)`$ to the cotangent complex $`L_V^{}`$ satisfying two properties:

1. $`\varphi `$ induces an isomorphism in cohomology in degree 0.
    2. $`\varphi `$ induces a surjection in cohomology in degree -1.

A virtual fundamental class of dimension $`dim(E^0)dim(E^1)`$ is canonically associated to the data (i) and (ii).

##### 5.3.2 Categories of complexes

Let $`C_{qcoh}^{}(V)`$ be the category of complexes of quasi-coherent sheaves bounded from above on $`V`$. The objects of $`C_{qcoh}^{}(V)`$ are complexes,

$$F^{}=[\mathrm{}F^1F^0F^1\mathrm{}],$$

satisfying $`F_i=0`$ for $`i`$ sufficiently large. The morphisms of $`C_{qcoh}^{}(V)`$ are chain maps of complexes.

A chain map $`\sigma :F^{}\stackrel{~}{F}^{}`$ is a quasi-isomorphism if $`\sigma `$ induces an isomorphism on cohomology: $`H^{}(\sigma ):H^{}(F^{})H^{}(\stackrel{~}{F}^{})`$.

The objects of derived category $`D_{qcoh}^{}(V)`$ are also complexes of quasi-coherent sheaves bounded from above on $`V`$. However, the morphisms of $`D_{qcoh}^{}(V)`$ are obtained by inverting all quasi-isomorphisms in $`C_{qcoh}^{}(V)`$. A basic result is a morphism $`F^{}G^{}`$ in $`D_{qcoh}^{}(V)`$ may be represented by a diagram:

$$\begin{array}{ccc}\stackrel{~}{F}^{}& \stackrel{\tau }{}& G^{}\\ \sigma & & \\ F^{},\end{array}$$

where $`\sigma `$ is a quasi-isomorphism and $`\tau `$ is map of complexes.

An excellent reference for the derived category is . A more informal introduction may be found in .

##### 5.3.3 Cotangent complexes

The cotangent complex $`L_V^{}`$ is a canonical object (up to equivalence) of $`D_{qcoh}^{}(V)`$. While the full complex $`L_V^{}`$ is constructed abstractly, we will see the essential properties which are required here can be described concretely.

If $`V`$ is nonsingular, $`L_V^{}`$ is defined by the 1 term complex $`[\mathrm{\Omega }_V]`$ in degree 0 determined by the cotangent bundle. A nonsingular space $`V`$ carries a canonical trivial perfect obstruction theory:

$$\varphi :[0\mathrm{\Omega }_V]\stackrel{}{}L_V^{}.$$

We will see the virtual fundamental class of this trivial theory is the ordinary fundamental class of $`V`$. For arbitrary $`V`$, the cotangent complex may be viewed as a generalized cotangent bundle.

We first note the $`k`$ cut-off functor is well-defined in $`D_{qcoh}^{}(V)`$:

$$F^k=[\frac{F^k}{Im(F^{k1})}F^{k+1}F^{k+2}\mathrm{}],$$

for any complex $`F^{}`$.

The cut-off $`L_V^1`$ of the cotangent complex for singular $`V`$ may be geometrically identified by the following construction. Let

$$\overline{M}Y$$
(5.6)
be an embedding in a nonsingular scheme (or Deligne-Mumford stack) $`Y`$. The cut-off of $`L_V^{}`$ is represented by:

$$L_{\overline{M}}^1=[I/I^2\mathrm{\Omega }_Y𝒪_{\overline{M}}].$$
(5.7)
Here, $`I`$ is the ideal sheaf of $`VY`$. The complex (5.7) is independent (up to equivalence in the derived category) of the embedding (5.6).

The representation (5.6) easily implies the cohomology of $`L_V^{}`$ in degree 0 is the sheaf of differentials $`\mathrm{\Omega }_{\overline{M}}`$. The cohomology of $`L_V^{}`$ is degree -1 is also determined by (5.6): $`H^1(L_V^{})`$ encodes singularity data of $`\overline{M}`$.

For the study of perfect obstruction theories and virtual classes, it will suffice to restrict the cotangent complex to the cut-off $`L_{\overline{M}}^1`$.

Stack quotient constructions of $`\overline{M}_{g,n}(X,\beta )`$ prove the existence of nonsingular embeddings (5.6) for the moduli space of maps . The quotient constructions also show the abundance of locally free sheaves on $`\overline{M}_{g,n}(X,\beta )`$ — a valuable property for the derived category.

##### 5.3.4 Distinguished triangles

Before proceeding, we include here a short review of mapping cones and distinguished triangles in the derived category.

Let $`A`$ be a complex in $`C_{qcoh}^{}(V)`$. Let $`A[1]`$ denote the shifted complex with negative differential:

$$A[1]^i=A^{i+1},d_A[1]=d_A.$$

Let $`\gamma :A^{}B^{}`$ be a morphism of complexes. The mapping cone $`M[\gamma ]`$ is the complex with terms and differentials:

$$M[\gamma ]^i=A[1]^iB^i,(d_A[1],\gamma +d_B).$$

The mapping cone may be canonically placed in a triangle of morphisms:

$$A^{}\stackrel{\gamma }{}B^{}M[\gamma ]^{}A[1]^{}.$$
(5.8)
A triangle of morphisms in the derived category,

$$X^{}Y^{}Z^{}X[1]^{},$$
(5.9)
is a distinguished triangle if there exist:

1. a map of complexes $`\gamma :A^{}B^{}`$,
2. a triple of isomorphisms in $`D_{qcoh}^{}(V)`$,

$$A^{}\stackrel{}{}X^{},B^{}\stackrel{}{}Y^{},M[\gamma ]^{}\stackrel{}{}Z^{},$$

which together yield an isomorphism of the triangles (5.8) and (5.9) in the derived category.

If the triangle (5.9) is distinguished, it is easily proven that

$$Y^{}Z^{}X[1]^{}Y[1]^{},$$

$$Z^{}X[1]^{}Y[1]^{}Z[1]^{},$$

are distinguished triangles as well. In this sense, the notion of a distinguished triangle has a cyclic triangular symmetry.

Finally, we note that a distinguished triangle yields a long exact sequence in cohomology by a standard result in homological algebra.

##### 5.3.5 The perfect obstruction theory of the moduli of maps

Let

$$\overline{M}=\overline{M}_{g,n}(X,\beta )$$

The perfect obstruction theory of $`\overline{M}`$ is obtained from the deformation theory of maps. The main step is a construction of a perfect obstruction theory $`\stackrel{~}{E}^{}`$ relative to the morphism

$$\tau :\overline{M}𝔐$$

where $`𝔐`$ is the Artin stack of quasi-stable curves. The deformation theory of maps

$$\pi :CX$$

from a fixed domain curve $`C`$ is well-known: the tangent and obstruction spaces are $`H^0(C,\pi ^{}T_X)`$ and $`H^1(C,\pi ^{}T_X)`$ respectively. A canonical relative perfect obstruction theory is then defined by:

$$\stackrel{~}{E}^{}=[R^{}\rho _{}(\pi ^{}T_X)]^{}L_\tau ^{},$$
(5.10)
where $`\rho :U\overline{M}`$ is the universal curve and $`L_\tau ^{}`$ is the relative cotangent complex of the morphism $`\tau `$ (see ). The relative theory satisfies conditions (a) and (b) for the morphism (5.10).

The relative cotangent complex $`L_\tau ^{}`$ is determined by a distinguished triangle:

$$\tau ^{}L_𝔐^{}L_{\overline{M}}^{}L_\tau ^{}\tau ^{}L_𝔐^{}[1],$$
(5.11)
which generalizes the sequence of relative differentials of a morphism. The pull-back $`\tau ^{}L_𝔐^{}`$ is canonically identified on $`\overline{M}`$:

$$\tau ^{}L_𝔐^{}\stackrel{}{=}[R^{}\underset{¯}{Hom}_{𝒪_{\overline{M}}}(,𝒪_U)(\mathrm{\Omega }_\rho (P))]^{}[1].$$

Here, $`\mathrm{\Omega }_\rho `$ is the sheaf of relative differentials on $`U`$, and $`P`$ is the divisor of marked points.

The absolute theory $`E^{}`$ for $`\overline{M}`$ is then constructed by including the deformations of the domain curve via a canonical distinguished triangle.

$$\begin{array}{ccccccc}\tau ^{}L_𝔐^{}& & E^{}& & [R^{}\rho _{}(\pi ^{}T_X)]^{}& & \tau ^{}L_𝔐^{}[1]\\ & & \varphi & & & & & & \\ \tau ^{}L_𝔐^{}& & L_{\overline{M}}& & L_\tau ^{}& & \tau ^{}L_𝔐^{}[1].\end{array}$$
(5.12)
The right arrow on the top line of (5.12) is obtained from the canonical morphism,

$$\pi ^{}\mathrm{\Omega }_X\stackrel{d\pi }{}\mathrm{\Omega }_\rho \mathrm{\Omega }_\rho (P),$$

together with the identification

$$R^{}\rho _{}(\pi ^{}T_X)\stackrel{}{=}R^{}\underset{¯}{Hom}_{𝒪_{\overline{M}}}(,𝒪_U)(\pi ^{}\mathrm{\Omega }_X).$$

The top line is then defined to be the distinguished triangle obtained from the right arrow. The bottom line of (5.12) is the canonical distinguished triangle of cotangent complexes obtained from the bottom right arrow. The construction of the diagram is then formal once the canonical morphisms in the right square are shown to commute.

The projectivity of $`X`$ may be used to find a two term sequences of vector bundles representing both the terms and the morphism,

$$[R^{}\rho _{}(\pi ^{}T_X)]^{}\tau ^{}L_𝔐^{}[1],$$

in the derived category (see ). By the mapping cone construction, $`E^{}`$ then admits a three term representation:

$$[E^1E^0E^1].$$
(5.13)
The stability condition on the moduli space of maps implies the cohomology of $`E^{}`$ vanishes in degree 1. Hence, the sequence (5.13) can be reduced to a two term complex.

The defining conditions (i) and (ii) of a perfect obstruction theory are easily verified for:

$$\varphi :E^{}L_{\overline{M}}^{},$$

by the long exact sequence obtained from diagram (5.12).

The diagram (5.12) is the primary method of studying the obstruction theory $`E^{}`$. Treatments can be found in  (the latter pursues a different perspective). A foundational exposition of these obstruction theories will be developed in .

Let $`[\pi :(C,p_1,\mathrm{},p_n)X]`$ be a moduli point of $`\overline{M}`$. The cohomologies of the dual complex $`[E_{[\pi ]}^{}]^{}`$ are the tangent and obstruction spaces of $`\overline{M}`$ at $`[\pi ]`$. The long exact sequence in cohomology of (the dual of) the top line of (5.12) yields the the familiar tangent-obstruction sequence:

$$0\text{Ext}^0(\mathrm{\Omega }_C(P),𝒪_C)H^0(C,\pi ^{}T_X)\text{Tan}(\pi )$$
(5.14)
$$\text{Ext}^1(\mathrm{\Omega }_C(P),𝒪_C)H^1(C,\pi ^{}T_X)\text{Obs}(\pi )0.$$

The following Lemma provides a basic example of the use of the perfect obstruction theory.

###### Lemma 5.1.

If $`H^1(C,\pi ^{}T_X)=0`$, then $`[\pi ]`$ is a nonsingular point of the Deligne-Mumford stack $`\overline{M}_{g,n}(X,\beta )`$.

Proof. If $`H^1(C,\pi ^{}T_X)=0`$, then $`\text{Obs}(\pi )=0`$. By semicontinuity, the obstruction space vanishes for every moduli point in an open set $`M`$ containing $`[\pi ]`$. Therefore, the complex $`E^{}`$ must have locally free cohomology in degree 0 and vanishing cohomology in degree -1 on $`M`$. By conditions (a) and (b) of the perfect obstruction theory, the cotangent complex must also have locally free cohomology in degree 0 and vanishing cohomology in degree -1 on $`M`$.

Consider an embedding $`MY`$ in a nonsingular Deligne-Mumford stack. The cut-off of the cotangent complex is

$$[I_M/I_M^2\mathrm{\Omega }_Y𝒪_M].$$

By the cohomology conditions, we conclude $`I_M/I_M^2`$ is locally free and injects into $`\mathrm{\Omega }_Y𝒪_M`$. By the local criterion for nonsingularity, $`M`$ is nonsingular.

We note the restriction of the perfect obstruction theory to $`M`$ yields the trivial perfect obstruction theory on a nonsingular space — where $`\varphi `$ is an isomorphism. ∎

##### 5.3.6 Construction of virtual classes

The perfect obstruction theory yields a map in the derived category

$$\varphi :E^{}L_{\overline{M}}^{}.$$

After an exchange of representatives and cutting-off, we may assume

$$\varphi :E^{}[I/I^2\mathrm{\Omega }_Y𝒪_{\overline{M}}]$$
(5.15)
is a map of complexes. The virtual class is obtained from the geometry of (5.15).

The mapping cone associated to (5.15) is the following complex of sheaves:

$$E^1E^0I/I^2\stackrel{\gamma }{}\mathrm{\Omega }_Y0.$$
(5.16)
The above complex (5.16) is right exact by conditions (a) and (b) satisfied by $`\varphi `$. Let $`Q`$ denote the kernel of $`\gamma `$. $`Q`$ is naturally a quotient of $`E^1`$ by right exactness.

Let $`S`$ be a coherent sheaf on $`\overline{M}`$. The symmetric tensors define a sheaf of $`𝒪_{\overline{M}}`$ algebras,

$$𝒮=\underset{k=0}{\overset{\mathrm{}}{}}Sym^k(S),$$

on $`\overline{M}`$. The abelian cone $`C(S)`$ is defined to be

$$Spec(𝒮)\overline{M}.$$

In case $`S`$ is a vector bundle, $`C(S)`$ is the total space of $`S^{}`$. We let $`E_0`$, $`E_1`$ denote $`C(E^0)`$, $`C(E^1)`$ respectively.

The sequence (5.16) yields an exact sequence of abelian cones:

$$0TYE_0\times _{\overline{M}}C(I/I^2)C(Q)0.$$

Here, the vector bundle $`TY`$ acts fiberwise and freely on the abelian cone $`E_0\times _{\overline{M}}C(I/I^2)`$ with quotient $`C(Q)`$.

Recall the normal cone $`C_{\overline{M}/Y}`$ is defined by:

$$C_{\overline{M}/Y}=Spec(\underset{k=0}{\overset{\mathrm{}}{}}I^k/I^{k+1})\overline{M}.$$

$`C_{\overline{M}/Y}`$ has pure dimension equal to $`dim(Y)`$ (see ). There is closed embedding of $`C_{\overline{M}/Y}C(I/I^2)`$ given by a natural surjection of algebras:

$$\underset{k=0}{\overset{\mathrm{}}{}}Sym^k(I/I^2)\underset{k=0}{\overset{\mathrm{}}{}}I^k/I^{k+1}.$$

The fundamental geometric fact is that the subcone

$$E_0\times _{\overline{M}}C_{\overline{M}/Y}E_0\times _{\overline{M}}C(I/I^2)$$

is invariant under the $`TY`$ action . The quotient cone

$$D=\frac{E_0\times _{\overline{M}}C_{\overline{M}/Y}}{TY}$$

is of pure dimension equal to $`dim(E_0)`$ and lies in $`C(Q)`$. There is an embedding of abelian cones

$$C(Q)E_1$$

obtained from the surjection $`E^1C(Q)`$. Hence $`DE_1`$.

Let $`z:\overline{M}E_1`$ be the inclusion of the zero section of the vector bundle $`E_1`$. Certainly $`z^1(D)=\overline{M}`$ as $`D`$ is a cone. The refined intersection product therefore yields a cycle class,

$$z^![D]A_{dim(E_0)dim(E_1)}(\overline{M},).$$

The virtual fundamental class of the perfect obstruction theory is defined to equal $`z^![D]`$.

The trivial perfect obstruction theory on a nonsingular space is easily seen to yield the ordinary fundamental class as the virtual class.

##### 5.3.7 Properties

The virtual class of $`\overline{M}_{g,n}(𝐏^1,d)`$ satisfies several remarkable properties — only two of which will be required here.

Since the inclusion of the moduli of maps with nonsingular domains,

$$M_{g,n}(𝐏^1,d)\overline{M}_{g,n}(𝐏^1,d),$$

is open, there is a well-defined restriction of the virtual class.

###### Proposition 5.2.

Let $`d1`$. $`M_{g,n}(𝐏^1,d)`$ is a nonsingular Deligne-Mumford stack of expected dimension $`2g2+2d+n`$. The restriction of virtual class is the ordinary fundamental class of $`M_{g,n}(𝐏^1,d)`$.

Proof. Let $`[\pi :(C,p_1,\mathrm{},p_n)𝐏^1]`$ determine a moduli point of $`M_{g,n}(𝐏^1,d)`$. The nonsingularity, the dimensionality, and the identification of the virtual class follow directly from the vanishing of $`\text{Obs}(\pi )`$ — as can be seen by Lemma 5.1 the definitions of Sections 5.3.6. The canonical right exact sequence:

$$\text{Ext}^1(\mathrm{\Omega }_C(D),𝒪_C)\stackrel{i}{}H^1(C,\pi ^{}T_{𝐏^1})\text{Obs}(\pi )0$$

is obtained from the tangent-obstruction sequence (5.14). Since $`C`$ is nonsingular, $`\text{Ext}^1(\mathrm{\Omega }_C(D),𝒪_C)=H^1(C,T_C(D))`$. Moreover, the map $`i`$ factors by:

$$H^1(C,T_C(D))H^1(C,T_C)H^1(C,\pi ^{}T_{𝐏^1}).$$
(5.17)
The first map in (5.17) is certainly surjective. Since $`d>0`$, the sheaf map $`T_C\pi ^{}T_{𝐏^1}`$ has a torsion quotient and the second map in (5.17) is also surjective. Hence, $`i`$ is surjective and $`\text{Obs}(\pi )=0`$. ∎

The second required property of the virtual class is the $`^{}`$-localization formula discussed in Section 6.

### 6 Virtual localization

#### 6.1 Atiyah-Bott localization

Let $`V`$ be a nonsingular algebraic variety (or Deligne-Mumford stack) equipped with an algebraic $`^{}`$-action. The Atiyah-Bott localization formula expresses equivariant integrals over $`V`$ as a sum of contributions over the $`^{}`$-fixed subloci.

Let $`H_{^{}}^{}(V)`$ denote the equivariant cohomology of $`V`$ with $``$-coefficients. Let $`H_{^{}}^{}(B^{})=[t]`$ be the standard presentation of the equivariant cohomology ring of $`^{}`$. The equivariant cohomology ring $`H_{^{}}^{}(V)`$ is canonically a $`H_{^{}}^{}(B^{})`$-module. Let

$$H_{^{}}^{}(V)_{[\frac{1}{t}]}=H_{^{}}^{}(V)[t,\frac{1}{t}]$$

denote the $`H_{^{}}^{}(B^{})`$-module localization at the element $`tH_{^{}}^{}(B^{})`$.

Let $`A_{}^{^{}}(V)`$ denote the closely related equivariant Chow ring of $`V`$ with $``$-coefficients (defined in  via homotopy quotients in the algebraic category). $`A_{}^{^{}}(V)`$ is a module over $`A_{^{}}^{}(B^{})=[t]`$.

Let $`\{V_i^f\}`$ be the connected components of the $`^{}`$-fixed locus, and let

$$\iota :_iV_i^fV$$

denote the inclusion morphism. The nonsingularity of $`V`$ implies each $`V_i^f`$ is also nonsingular . Let $`N_i`$ denote the normal bundle of $`V_i^f`$ in $`V`$, and let $`e(N_i)`$ denote the equivariant Euler class (top Chern class) of $`N_i`$.

The Atiyah-Bott localization formula  is:

$$[V]=\iota _{}\underset{i}{}\frac{[V_i^f]}{e(N_i)}H_{^{}}^{}(V)_{[\frac{1}{t}]}$$
(6.1)
The formula is well-defined as the Euler classes $`e(N_i)`$ are invertible in the localized equivariant cohomology ring.

By a result of Edidin-Graham, formula (6.1) holds also in the localized equivariant Chow ring $`A_{}^{^{}}(V)_{[\frac{1}{t}]}`$.

Let $`\xi H_{^{}}^{}(V)`$ be a class of degree equal to (twice) the dimension of $`V`$. The Bott residue formula  expresses integrals over $`V`$ in terms of fixed point data:

$$_V\xi =\underset{i}{}_{V_i^f}\frac{\iota ^{}(\xi )}{e(N_i)}.$$

The Bott residue formula is an immediate consequence of (6.1). Localization therefore provides an effective method of computing integrals over $`V`$ when the fixed loci $`V_i^f`$ are well-understood.

#### 6.2 Localization of virtual classes

Let $`V`$ be an algebraic variety (or Deligne-Mumford stack) equipped with a $`^{}`$-action. Let $`V`$ carry a perfect obstruction theory $`\varphi :E^{}L_V^{}`$ equipped with an equivariant $`^{}`$-action. While $`V`$ may be arbitrarily singular, a localization formula for the virtual class holds.

Let $`\{V_i^f\}`$ be the connected components of the scheme theoretic $`^{}`$-fixed locus as before. Since $`V`$ may be singular, the components $`V_i^f`$ may be singular as well. However, each $`V_i^f`$ is equipped with a canonical perfect obstruction theory . Moreover, a normal complex can be found for each $`V_i^f`$ (replacing the normal bundle in the nonsingular case). Together, these constructions yield a natural extension of the Atiyah-Bott localization formula to virtual classes.

Let $`E_i^{}`$ denote the restriction of the complex $`E^{}`$ to $`V_i^f`$. The complex $`E_i^{}`$ may be decomposed by $`^{}`$-characters:

$$E_i^{}=E_i^{,f}E_i^{,m},$$

where the first summand corresponds to the trivial character (the $`^{}`$-fixed part) and the second summand corresponds to all the non-trivial characters (the $`^{}`$-moving part). A canonical morphism

$$\varphi _i:E_i^{,f}L_{V_i^f}^{}$$
(6.2)
is obtained from the $`^{}`$-fixed part of $`\varphi `$. It is shown in  that (6.2) is a perfect obstruction theory on $`V_i^f`$. The $`^{}`$-moving part $`E_i^{,m}`$ is the defined to be the virtual (co)normal complex $`[N_i^{vir}]^{}`$.

The virtual localization formula  is:

$$[V]^{vir}=\iota _{}\underset{i}{}\frac{[V_i^f]^{vir}}{e(N_i^{vir})}A_{^{}}^{}(V)_{[\frac{1}{t}]}.$$
(6.3)
The Euler class of $`N_i^{vir}=[E_{0,i}^mE_{1,i}^m]`$ is defined to be:

$$e(N_i^{vir})=\frac{e(E_{0,i}^m)}{e(E_{1,i}^m)}.$$

The virtual localization formula is well-defined since the Euler classes of the moving parts of the bundles $`E_{0,i}`$ and $`E_{1,i}`$ are invertible after localization. The proof of (6.3) in  requires the existence of a $`^{}`$-equivariant embedding $`VY`$ in a nonsingular variety (or Deligne-Mumford stack) $`Y`$.

In case $`V`$ is nonsingular, the Atiyah-Bott localization formula is recovered from (6.3) via the trivial $`^{}`$-equivariant perfect obstruction theory on $`V`$.

If the nonsingular target $`X`$ admits a $`^{}`$-action, a canonical $`^{}`$-action by translation is induced on $`\overline{M}_{g,n}(X,\beta )`$. Stack quotient constructions prove the existence of $`^{}`$-equivariant nonsingular embeddings for $`\overline{M}_{g,n}(X,\beta )`$ in this case . The virtual localization formula then provides an effective tool in the study of integrals in Gromov-Witten theory of $`X`$.

#### 6.3 Virtual localization for $`\overline{M}_g(𝐏^1,d)`$

##### 6.3.1 The $`^{}`$-action on $`𝐏^1`$

We first establish our $`^{}`$-action conventions on $`𝐏^1`$. Let $`V=^2`$. Let $`^{}`$ act on $`V`$ with weights $`0,1`$:

$$t[v_0,v_1]=[v_0,tv_1].$$
(6.4)
The action (6.4) canonically induces a $`^{}`$-action on $`𝐏^1=𝐏(V)`$. This action will be fixed throughout the paper.

We identify $`0,\mathrm{}𝐏^1`$ with the $`^{}`$-fixed points of $`𝐏(V)`$:

$$p_0=[1,0],p_1=[0,1].$$

The canonical $`^{}`$-actions on the tangent spaces to $`𝐏(V)`$ at $`p_0`$, $`p_1`$ have weights $`+1`$, $`1`$ respectively.

##### 6.3.2 The $`^{}`$-action on $`\overline{M}_g(𝐏^1,d)`$

The $`^{}`$-action on $`𝐏^1`$ canonically induces a $`^{}`$-action on $`\overline{M}_g(𝐏^1,d)`$ by translation of maps:

$$t[\pi ]=[t\pi ].$$

As the perfect obstruction theory of $`\overline{M}_{g,n}(𝐏^1,d)`$ is constructed canonically, $`^{}`$-equivariance is immediate.

The virtual localization formula is studied here for the translation action on $`\overline{M}_{g,n}(𝐏^1,d)`$ following . Four properties of the geometry allow for a complete analysis of the virtual localization formula:

1. The $`^{}`$-fixed locus in $`\overline{M}_{g,n}(𝐏^1,d)`$ is a disjoint union of nonsingular (Deligne-Mumford stack) components.
2. Each $`^{}`$-fixed component is isomorphic a quotient of products of moduli stacks of pointed curves $`\overline{M}_{\gamma ,l}`$.
3. The virtual structure on the $`^{}`$-fixed components is the canonical trivial structure on a nonsingular space.
4. The Euler class of the normal complex is identified in terms of tautological $`\psi `$ and $`\lambda `$ classes on the fixed components.

##### 6.3.3 The $`^{}`$-fixed components

Following , we can identify the components of the $`^{}`$-fixed locus of $`\overline{M}_{g,n}(𝐏^1,d)`$ with a set of graphs. We will always assume $`d>0`$.

A graph $`\mathrm{\Gamma }G_{g,n}(𝐏^1,d)`$ consists of the data $`(V,E,N,\gamma ,j,\delta )`$ where:

1. $`V`$ is the vertex set,
2. $`\gamma :V^0`$ is a genus assignment,
3. $`j:V\{0,1\}`$ is a bipartite structure,
4. $`E`$ is the edge set,

1. If the edge $`e`$ connects $`v,v^{}V`$, then $`j(v)j(v^{})`$ (in particular, there are no self edges),
    2. $`\mathrm{\Gamma }`$ is connected,
5. $`\delta :E^{>0}`$ is a degree assignment,
6. $`N=\{1,\mathrm{},n\}`$ is a set of markings incident to vertices,
7. $`g=_{vV}\gamma (v)+h^1(\mathrm{\Gamma })`$,
8. $`d=_{eE}\delta (e).`$

The $`^{}`$-fixed components of $`\overline{M}_{g,n}(𝐏^1,d)`$ are in bijective correspondence with the graph set $`G_{g,n}(𝐏^1,d)`$.

Let $`\pi :(C,p_1,\mathrm{},p_n)𝐏^1`$ be a $`^{}`$-fixed stable map. The images of all marked points, nodes, contracted components, and ramification points must lie in the $`^{}`$-fixed point set $`\{p_0,p_1\}`$ of $`𝐏^1`$. In particular, each non-contracted irreducible component $`DC`$ is ramified only over the two fixed points $`\{p_0,p_1\}`$. Therefore $`D`$ must be nonsingular and rational. Moreover, the restriction $`\pi |_D`$ is uniquely determined by the degree $`deg(\pi |_D)`$, $`\pi |_D`$ must be the rational Galois cover with full ramification over $`p_0`$ and $`p_1`$.

To an invariant stable map $`\pi :(C,p_1,\mathrm{},p_n)𝐏^1`$, we associate a graph $`\mathrm{\Gamma }G_{g,n}(𝐏^1,d)`$ as follows:

1. $`V`$ is the set of connected components of $`\pi ^1(\{p_0,p_1\})`$,
2. $`\gamma (v)`$ is the arithmetic genus of the component corresponding to $`v`$ (taken to be 0 if the component is an isolated point),
3. $`j(v)`$ is defined by $`\pi (v)=p_{j(v)}`$,
4. $`E`$ is the set of non-contracted irreducible components $`DC`$,
5. $`\delta (D)=deg(\pi |_D)`$,
6. $`N`$ is the marking set.

Conditions (vii-viii) hold by definition.

The set of $`^{}`$-fixed stable maps with given graph $`\mathrm{\Gamma }`$ is naturally identified with a finite quotient of a product of moduli spaces of pointed curves. Define:

$$\overline{M}_\mathrm{\Gamma }=\underset{vV}{}\overline{M}_{\gamma (v),val(v)}.$$

The valence $`val(v)`$ is the number of incident edges and markings. $`\overline{M}_{0,1}`$ and $`\overline{M}_{0,2}`$ are interpreted as points in this product. Over $`\overline{M}_\mathrm{\Gamma }`$, there is a canonical universal family of $`^{}`$-fixed stable maps,

$$\rho :U\overline{M}_\mathrm{\Gamma },$$

$$\pi :U𝐏^1,$$

yielding a morphism of stacks $`\tau _\mathrm{\Gamma }:\overline{M}_\mathrm{\Gamma }\overline{M}_{g,n}(𝐏^1,d).`$

There is a natural automorphism group $`A_\mathrm{\Gamma }`$ acting equivariantly on $`U`$ and $`\overline{M}_\mathrm{\Gamma }`$ with respect to the morphisms $`\rho `$ and $`\pi `$. $`A_\mathrm{\Gamma }`$ acts via automorphisms of the Galois covers (corresponding to the edges) and the symmetries of the graph $`\mathrm{\Gamma }`$. $`A_\mathrm{\Gamma }`$ is filtered by an exact sequence of groups:

$$1\underset{eE}{}/\delta (e)A_\mathrm{\Gamma }\text{Aut}(\mathrm{\Gamma })1$$

where $`\text{Aut}(\mathrm{\Gamma })`$ is the automorphism group of $`\mathrm{\Gamma }`$: $`\text{Aut}(\mathrm{\Gamma })`$ is the subgroup of the permutation group of the vertices and edges which respects all the structures of $`\mathrm{\Gamma }`$. $`\text{Aut}(\mathrm{\Gamma })`$ naturally acts on $`_{\mathrm{edges}}/\delta (e)`$ and $`A_\mathrm{\Gamma }`$ is the semidirect product.

Let $`Q_\mathrm{\Gamma }`$ denote the quotient stack $`\overline{M}_\mathrm{\Gamma }/A_\mathrm{\Gamma }`$. The induced map:

$$\tau _\mathrm{\Gamma }/A_\mathrm{\Gamma }:Q_\mathrm{\Gamma }\overline{M}_{g,n}(𝐏^1,d)$$

is a closed immersion of Deligne-Mumford stacks. It should be noted that the subgroup $`_{\mathrm{edges}}/\delta (e)`$ acts trivially on $`\overline{M}_\mathrm{\Gamma }`$. $`_\mathrm{\Gamma }`$ is a nonsingular Deligne-Mumford stack.

The above set-theoretic analysis proves a component of the $`^{}`$-fixed stack of $`\overline{M}_{g,n}(𝐏^1,d)`$ is supported on the substack $`Q_\mathrm{\Gamma }`$.

##### 6.3.4 The $`^{}`$-fixed perfect obstruction theory

Let $`\varphi :E^{}L_{\overline{M}_{g,n}(𝐏^1,d)}^{}`$ denote the $`^{}`$-equivariant perfect obstruction theory of the moduli of maps. Let $`E_{,\mathrm{\Gamma }}`$ denote the restriction of $`E_{}`$ to $`Q_\mathrm{\Gamma }`$. Denote the cohomology of $`E_{,\mathrm{\Gamma }}`$ by:

$$0\text{Tan}E_{0,\mathrm{\Gamma }}E_{1,\mathrm{\Gamma }}\text{Obs}0.$$
(6.5)
The tangent-obstruction sequence may be studied on $`Q_\mathrm{\Gamma }`$ — the sequence is obtained from the cohomology of the (dual of) the restriction to $`Q_\mathrm{\Gamma }`$ of the top distinguished triangle of (5.12). The fiber of the tangent-obstruction sequence over $`[\pi ]Q_\mathrm{\Gamma }`$ is:

$$0\text{Ext}^0(\mathrm{\Omega }_C(P),𝒪_C)H^0(C,\pi ^{}T_{𝐏^1})\text{Tan}$$
(6.6)
$$\text{Ext}^1(\mathrm{\Omega }_C(P),𝒪_C)H^1(C,\pi ^{}T_{𝐏^1})\text{Obs}0.$$

The elements of (6.6) are vector bundles on $`Q_\mathrm{\Gamma }`$ (instead of possibly singular sheaves) as theirs ranks are constant on $`[\pi ]Q_\mathrm{\Gamma }`$.

The scheme structure of the $`^{}`$-fixed stack supported on $`Q_\mathrm{\Gamma }`$ may be determined from the perfect obstruction theory. The Zariski tangent space at $`[\pi ]`$ to the $`^{}`$-fixed stack is $`\text{Tan}_{[\pi ]}^f`$. A direct study of the $`^{}`$-fixed part of (6.6) in  shows this Zariski tangent space to be isomorphic to the tangent space of $`Q_\mathrm{\Gamma }`$. As $`Q_\mathrm{\Gamma }`$ is a nonsingular stack, we may conclude the $`Q_\mathrm{\Gamma }`$ is a component of the $`^{}`$-fixed stack.

The second use of (6.6) is to determine the perfect obstruction theory of the $`^{}`$-fixed component $`Q_\mathrm{\Gamma }`$ induced by $`\varphi `$. An analysis of the $`^{}`$-fixed part of (6.6) immediately implies the induced perfect obstruction theory is trivial . It is quite easy to analyze the sequence (6.6) as the stable maps parameterized by $`Q_\mathrm{\Gamma }`$ are of a uniformly simple character.

The virtual localization formula for $`\overline{M}_{g,n}(𝐏^1,d)`$ may now be written as:

$$[\overline{M}_{g,n}(𝐏^1,d)]^{vir}=\underset{\mathrm{\Gamma }G_{g,n}(𝐏^1,d)}{}\frac{1}{|A_\mathrm{\Gamma }|}\frac{\tau _\mathrm{\Gamma }[\overline{M}_\mathrm{\Gamma }]}{e(N_\mathrm{\Gamma }^{vir})}$$
(6.7)
in $`A_{}^{^{}}(\overline{M}_{g,n}(𝐏^1,d))_{[\frac{1}{t}]}`$. The $`^{}`$-fixed loci $`Q_\mathrm{\Gamma }`$ enter (6.7) as push-forwards of $`\overline{M}_\mathrm{\Gamma }`$ via $`\tau _\mathrm{\Gamma }`$.

##### 6.3.5 The normal complex

The tangent-obstruction sequence (6.6) also determines the Euler class of the normal complex of $`^{}`$-fixed loci induced by $`\varphi `$. The moving parts of the vector bundle sequences (6.5-6.6) imply:

$$\frac{1}{e(N^{vir})}=\frac{e(\text{Ext}^0(\mathrm{\Omega }_C(P),𝒪_C)^m)}{e(\text{Ext}^1(\mathrm{\Omega }_C(P),𝒪_C)^m)}\frac{e(H^1(C,\pi ^{}T_{𝐏^1})^m)}{e(H^0(C,\pi ^{}T_{𝐏^1})^m)}.$$
(6.8)
Let $`\mathrm{\Gamma }G_{g,n}(𝐏^1,d)`$. The above identification (6.8) precisely specifies the $`\tau _\mathrm{\Gamma }`$ pull-back of $`1/e(N^{vir})`$ to $`\overline{M}_\mathrm{\Gamma }`$,

$$\overline{M}_\mathrm{\Gamma }=\underset{vV}{}\overline{M}_{\gamma (v),val(v)}.$$
(6.9)
The pull-backs of the Euler classes of the vector bundles on the right of (6.8) naturally split over the vertex factors of $`\mathrm{\Gamma }`$. We will find:

$$\tau _\mathrm{\Gamma }^{}(\frac{1}{e(N^{vir})})=(1)^d\underset{vV}{}\frac{1}{N(v)},$$
(6.10)
where the vertex contributions $`1/N(v)`$ lie in localized equivariant cohomology,

$$\frac{1}{N(v)}A_{}^{^{}}(\overline{M}_{\gamma (v),val(v)})_{[\frac{1}{t}]}.$$

##### 6.3.6 Vertex contributions

Intermediate vertex and edge contributions $`1/\stackrel{~}{N}(v)`$ and $`1/\stackrel{~}{N}(e)`$ naturally arise in the geometric analysis of the (6.8). The intermediate contributions will be joined to yield the single vertex contribution $`1/N(v)`$.

There are four types of vertices which we treat independently here. In integration formulas, a uniform treatment of the four types is often found.

A vertex $`v`$ is stable if $`2\gamma (v)2+val(v)>0.`$ If $`v`$ is stable, the factor $`\overline{M}_{\gamma (v),val(v)}`$ is a factor of $`\overline{M}_\mathrm{\Gamma }`$ by (6.9). The intermediate contribution $`1/\stackrel{~}{N}(v)`$ will be a equivariant cohomology class on the factor $`\overline{M}_{\gamma (v),val(v)}`$ in this case.

$``$ Let $`v`$ be a stable vertex. Let $`e_1,\mathrm{},e_l`$ denote the distinct edges incident to $`v`$ (in bijective correspondence to a subset of the (local) markings of the moduli space $`\overline{M}_{\gamma (v),val(v)}`$). Let $`\psi _i`$ denote the cotangent line of the marking corresponding to $`e_i`$.

$`{\displaystyle \frac{1}{\stackrel{~}{N}(v)}}`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{l}{}}}{\displaystyle \frac{1}{\frac{(1)^{j(v)}t}{\delta (e_i)}\psi _i}}`$
$`((1)^{j(v)}t)^{l1}`$
$`{\displaystyle \underset{i=0}{\overset{\gamma (v)}{}}}(1)^i((1)^{j(v)}t)^{\gamma (v)i}\lambda _i.`$
The three factors in $`1/\stackrel{~}{N}(v)`$ are the contributions of $`\text{Ext}^1(\mathrm{\Omega }_C(P),𝒪_C)^m`$, $`H^0(C,\pi ^{}T_X)^m`$, and $`H^1(C,\pi ^{}T_X)^m`$ respectively. $`\text{Ext}^0(\mathrm{\Omega }_C(P),𝒪_C)^m`$ does not contribute to stable vertices.

We note both the tautological $`\psi `$ and $`\lambda `$ classes enter in $`1/\stackrel{~}{N}(v)`$. The Gromov-Witten theory of $`𝐏^1`$ is therefore fundamentally related to the intersection theory of the moduli space of curves.

If $`v`$ is an unstable vertex, then $`\gamma (v)=0`$ and $`val(v)2`$. There are three unstable cases: two with valence 2 and one with valence 1.

$``$ Let $`v`$ be an unmarked vertex with $`\gamma (v)=0`$ and $`val(v)=2`$. Let $`e_1`$ and $`e_2`$ be the two incident edges. Then:

$$\frac{1}{\stackrel{~}{N}(v)}=\frac{1}{\frac{(1)^{j(v)}t}{\delta (e_1)}+\frac{(1)^{j(v)}t}{\delta (e_2)}}(1)^{j(v)}t=\frac{1}{\frac{1}{\delta (e_1)}+\frac{1}{\delta (e_2)}}.$$

The factors are obtained from $`\text{Ext}^1(\mathrm{\Omega }_C(P),𝒪_C)^m`$ and $`H^0(C,\pi ^{}T_{𝐏^1})^m`$ respectively.

$``$ Let $`v`$ be a $`1`$-marked vertex with $`\gamma (v)=0`$ and $`val(v)=2`$. Let $`e`$ be the unique incident edge. Then:

$$\frac{1}{\stackrel{~}{N}(v)}=1,$$

there are no contributing factors.

$``$ Let $`v`$ be an unmarked vertex with $`\gamma (v)=0`$ and $`val(v)=1`$. Let $`e`$ be the unique incident edge. Then:

$$\frac{1}{\stackrel{~}{N}(v)}=\frac{(1)^{j(v)}t}{\delta (e)},$$

where $`\text{Ext}^0(\mathrm{\Omega }_C(P),𝒪_C)^m`$ is the only contributing factor.

All of these contributions are easily extracted from an analysis of (6.8) .

##### 6.3.7 Edge contributions

Let $`eE`$ be an edge corresponding to the non-contracted irreducible component $`DC`$ (where

$$[\pi :(C,p_1,\mathrm{},p_n)𝐏^1]$$

is a moduli point parameterized by $`\overline{M}_\mathrm{\Gamma }`$). The edge contribution,

$$\frac{1}{\stackrel{~}{N}(e)}A_{}^{^{}}(B^{})_{[\frac{1}{t}]},$$

is the inverse Euler class of the $`^{}`$-representation $`H^0(D,\pi ^{}T_{𝐏^1})^m.`$ The contribution is obtained from $`H^0(C,\pi ^{}T_{𝐏^1})^m`$.

Consider the $`^{}`$-equivariant Euler sequence on $`𝐏^1`$:

$$0𝒪𝒪(1)VT𝐏^10.$$

After pulling back to $`D`$ and taking cohomology, we find:

$$0H^0(D,𝒪(\delta (e)))VH^0(D,\pi ^{}T𝐏^1)0.$$
(6.11)
The $`^{}`$-weight on $``$ is trivial, and the weights of $`H^0(D,𝒪(\delta (e)))`$ are:

$$\frac{it}{\delta (e)},0i\delta (e).$$

The weights of $`V`$ are $`0,1`$. The weights of the of the middle term in (6.11) are therefore the pairwise sums:

$$\frac{it}{\delta (e)},1\frac{it}{\delta (e)},0i\delta (e).$$

As only the moving weights concern us, we find:

$$\frac{1}{\stackrel{~}{N}(e)}=\frac{1}{(1)^{\delta (e)}\frac{\delta (e)!^2}{\delta (e)^{2\delta (e)}}t^{2\delta (e)}}.$$

By the analysis of , the contributions $`1/\stackrel{~}{N}(v)`$ and $`1/\stackrel{~}{N}(e)`$ together account for the entire right side of (6.8). We find:

$$\tau _\mathrm{\Gamma }^{}(\frac{1}{e(N^{vir})})=\underset{vV}{}\frac{1}{\stackrel{~}{N}(v)}\underset{eE}{}\frac{1}{\stackrel{~}{N}(e)}.$$
(6.12)
##### 6.3.8 $`1/N(v)`$

Since the intermediate edge contribution $`(1)^{\delta (e)}\stackrel{~}{N}(e)`$ admits a square root,

$$\sqrt{\frac{(1)^{\delta (e)}}{\stackrel{~}{N}(e)}}=\frac{\delta (e)^{\delta (e)}}{\delta (e)!}t^{\delta (e)},$$

the edge contributions may be distributed to the incident vertices. Let $`v`$ be a vertex with incident edges $`e_1,\mathrm{},e_l`$. Define $`1/N(v)`$ by:

$$\frac{1}{N(v)}=\frac{1}{\stackrel{~}{N}(v)}\underset{i=1}{\overset{l}{}}\frac{\delta (e_i)^{\delta (e_i)}}{\delta (e_i)!}t^{\delta (e_i)}.$$

Equation (6.12) then immediately implies (6.10).

##### 6.3.9 Integration

Virtual localization yields an integration formula for the Gromov-Witten theory of $`𝐏^1`$. The expected dimension of the moduli space $`\overline{M}_{g,n}(𝐏^1,d)`$ is $`2g2+2d+n`$. Let $`\xi `$ be an equivariant class

$$\xi H_{^{}}^{2(2g2+2d+n)}(\overline{M}_{g,n}(𝐏^1,d),).$$

Via the canonical morphism,

$$H_{^{}}^{}(\overline{M}_{g,n}(𝐏^1,d),)H^{}(\overline{M}_{g,n}(𝐏^1,d),),$$

The class $`\xi `$ may be viewed as an equivariant lift of an ordinary cohomology class on $`\overline{M}_{g,n}(𝐏^1,d)`$ — called the non-equivariant limit of $`\xi `$.

The virtual residue formula for the integral of $`\xi `$ obtained from virtual localization is:

$$_{[\overline{M}_{g,n}(𝐏^1,d)]^{vir}}\xi =\underset{\mathrm{\Gamma }G_{g,n}(𝐏^1,d)}{}\frac{(1)^d}{|A_\mathrm{\Gamma }|}_{\overline{M}_\mathrm{\Gamma }}\frac{\tau _\mathrm{\Gamma }^{}(\xi )}{_{vV}N(v)}.$$
(6.13)
The left side of (6.13) is equal to the integral of the non-equivariant limit of $`\xi `$. Only the $`t^0`$ terms contribute to the right side after integration.

Formula (6.13) effectively relates integrals in the Gromov-Witten theory of $`𝐏^1`$ to tautological integrals over the moduli space of curves.

#### 6.4 Gravitational descendents

We explain here an application of the virtual localization formula to the descendent invariants of $`𝐏^1`$:

$$\underset{i=1}{\overset{r}{}}\tau _{a_i}\underset{j=r+1}{\overset{r+s}{}}\tau _{b_j}(\omega )_{g,d}^{𝐏^1}=_{[\overline{M}_{g,n}(𝐏^1,d)]^{vir}}\underset{i=1}{\overset{r}{}}\psi _i^{a_i}\underset{j=r+1}{\overset{r+s}{}}\psi _j^{b_j}\text{ev}_j^{}(\omega ).$$
(6.14)
All terms of integrand of (6.14) are equipped with canonical $`^{}`$-equivariant lifts. First, the $`^{}`$-action is canonically lifted to the cotangent classes $`\psi _i`$ of $`\overline{M}_{g,n}(𝐏^1,d)`$. Second, the class $`\omega =c_1(𝒪(1))`$ is canonically lifted to $`H_{^{}}^2(𝐏^1,)`$ via the canonical $`^{}`$-action on $`𝒪(1)`$ — the $`^{}`$-action on $`V`$ induces an action on the tautological line $`𝒪(1)`$ and (by dualizing) an action on $`𝒪(1)`$. The $`^{}`$-action on $`𝒪(1)`$ has fiber weights

$$w_0=0,w_1=1$$

over the points $`p_0,p_1𝐏^1`$ respectively. Finally, the class $`\text{ev}_j^{}(\omega )`$ may be canonically lifted from the lift of $`\omega `$.

Let $`\xi `$ denote the canonical lift of the integrand of (6.14). The virtual localization formula applied to $`\xi `$ determines the descendent invariant in terms of tautological integrals over the moduli spaces of curves:

$$\underset{i=1}{\overset{r}{}}\tau _{a_i}\underset{j=r+1}{\overset{r+s}{}}\tau _{b_j}(\omega )_{g,d}^{𝐏^1}=\underset{\mathrm{\Gamma }G_{g,n}(𝐏^1,d)}{}\frac{(1)^d}{|A_\mathrm{\Gamma }|}_{\overline{M}_\mathrm{\Gamma }}\frac{\tau _\mathrm{\Gamma }^{}(\xi )}{_{vV}N(v)}.$$

The pull-back of $`\xi `$ to $`\overline{M}_\mathrm{\Gamma }`$ factorizes over the vertices of $`\mathrm{\Gamma }`$:

$$\tau _\mathrm{\Gamma }^{}(\xi )=\underset{vV}{}\xi (v).$$

There are four types of vertex contributions $`\xi (v)`$.

$``$ Let $`v`$ be a stable vertex. Let $`\{1,\mathrm{},r+s\}`$ denote the (global) marking set of $`\overline{M}_{g,r+s}(𝐏^1,,d)`$. Let

$$R\{1,\mathrm{},r\},S\{r+1,\mathrm{}r+s\}$$

denote the subsets of the global markings lying on $`v`$. Then,

$$\xi (v)=\underset{iR}{}\psi _i^{a_i}\underset{iS}{}\psi _i^{b_i}w_{j(v)}tH_{^{}}^{}(\overline{M}_{\gamma (v),val(v)}).$$

Note this contribution vanishes if $`j(v)=0`$ and $`S`$ is non-empty.

$``$ Let $`v`$ be an unmarked vertex with $`\gamma (v)=0`$ and $`val(v)=2`$. Then,

$$\xi (v)=1.$$

$``$ Let $`v`$ be a $`1`$-marked vertex with $`\gamma (v)=0`$ and $`val(v)=2`$. Let $`e`$ denote the unique edge incident to $`e`$. If the marking $`i`$ of $`v`$ satisfies $`1ir`$, then

$$\xi (v)=\left(\frac{(1)^{j(v)}t}{\delta (e)}\right)^{a_i}.$$

If the marking $`i`$ of $`v`$ satisfies $`r+1ir+s`$, then

$$\xi (v)=\left(\frac{(1)^{j(v)}t}{\delta (e)}\right)^{b_i}w_{j(v)}t.$$

Note the second contribution vanishes if $`j(v)=0`$.

$``$ Let $`v`$ be an unmarked vertex with $`\gamma (v)=0`$ and $`val(v)=1`$. Then,

$$\xi (v)=1.$$

We find an explicit formula for the gravitational descendent invariants of $`𝐏^1`$ in terms of tautological integrals over the moduli space of curves.

###### Proposition 6.1.

The gravitational descendents of $`𝐏^1`$ are determined by graph sums of Hodge integrals:

$$\underset{i=1}{\overset{r}{}}\tau _{a_i}\underset{j=r+1}{\overset{r+s}{}}\tau _{b_j}(\omega )_{g,d}^{𝐏^1}=\underset{\mathrm{\Gamma }G_{g,n}(𝐏^1,d)}{}\frac{(1)^d}{|A_\mathrm{\Gamma }|}_{\overline{M}_\mathrm{\Gamma }}\underset{vV}{}\frac{\xi (v)}{N(v)}.$$

### 7 From Hurwitz numbers to Hodge integrals

#### 7.1 The proof of Theorem 2

The Hurwitz numbers $`H_{g,\mu }`$ count genus $`g`$ covers of $`𝐏^1`$ with profile $`\mu `$ over $`\mathrm{}`$ and simple ramification over a fixed set of finite points. The relationship between Hurwitz numbers and Hodge integrals is proven here via the Gromov-Witten theory of $`𝐏^1`$.

The proof of Theorem 2 is immediate in case $`\mu `$ is trivial, the case of the Hurwitz numbers $`H_{g,d}`$. The Hurwitz numbers $`H_{g,d}`$ arise as integrals against $`[\overline{M}_g(𝐏^1,d)]^{vir}`$ via the branch morphism. The Hodge integral relationship is then a direct consequence of the virtual residue formula. The argument for $`H_{g,d}`$ is explained first in Section 7.2.

Theorem 2 is proven for arbitrary profile $`\mu `$ in Section 7.3. The Hurwitz numbers $`H_{g,\mu }`$ arise as integrals over natural components of $`\overline{M}_g(𝐏^1,d)`$. A detailed analysis is required to extract the relevant component contributions from the virtual residue formula . Our presentation in Section 7.3 follows .

#### 7.2 The Hurwitz number $`H_{g,d}`$

##### 7.2.1 Integrals

The Hurwitz number $`H_{g,d}=H_{g,1^d}`$ counts genus $`g`$ covers of $`𝐏^1`$ étale over $`\mathrm{}`$ with

$$r=2g2+2d$$

fixed finite simple ramification points. The branch morphism $`br`$ constructed in Section 5.2 is:

$$br:\overline{M}_g(𝐏^1,d)\text{Sym}^r(𝐏^1).$$

Let $`\xi _p`$ denote (the Poincaré dual of) the point class of $`\text{Sym}^r(𝐏^1)`$.

###### Proposition 7.1.

The Hurwitz number $`H_{g,d}`$ is an integral in Gromov-Witten theory:

$$H_{g,d}=_{[\overline{M}_g(𝐏^1,d)]^{vir}}br^{}(\xi _p).$$

Proof. The locus $`M_g(𝐏^1,d)\overline{M}_g(𝐏^1,d)`$ is nonsingular (of the expected dimension) by Proposition 5.2.

Let $`z_1,\mathrm{},z_r𝐏(V)`$ be distinct points. If $`[\pi :C𝐏^1]`$ is a stable map with a singular domain curve, then the divisor $`br(\pi )`$ must contain a double point. Therefore, $`br^1(_{i=1}^r[z_i])M_g(𝐏^1,d)`$. By Bertini’s Theorem applied to the morphism

$$br:M_g(𝐏^1,d)\text{Sym}^r(𝐏^1)=𝐏^r,$$

a general divisor $`_{i=1}^r[z_i]`$ intersects the stack $`M_g(𝐏^1,d)`$ transversely via $`br`$ in a finite number of points. These intersections are exactly the finitely many Hurwitz covers $`H_{g,d}`$ ramified over $`\{z_i\}`$ (weighted by $`1/|\text{Aut}|`$ in the intersection product). ∎

##### 7.2.2 Localization

We follow the conventions set in Section 6.3.1 regarding the $`^{}`$-action on $`𝐏^1=𝐏(V)`$.

The canonical $`^{}`$-actions on the spaces $`\overline{M}_g(𝐏^1,d)`$ and $`\text{Sym}^r(𝐏^1)`$ are $`br`$-equivariant by the canonical construction of the branch morphism .

Let $`\xi `$ be the $`^{}`$-equivariant lift of the point class $`\xi _p`$ corresponding to the $`^{}`$-fixed divisor $`r[p_0]\text{Sym}^r(𝐏(V))`$. The integral,

$$H_{g,d}=_{[\overline{M}_g(𝐏^1,d)]^{vir}}br^{}(\xi ),$$

may then be evaluated via the virtual residue formula:

$$H_{g,d}=\underset{\mathrm{\Gamma }G_g(𝐏^1,d)}{}\frac{(1)^d}{|A_\mathrm{\Gamma }|}_{\overline{M}_\mathrm{\Gamma }}\frac{br^{}(\xi )}{_{vV}N(v)}.$$
(7.1)
$`\text{Sym}^r(𝐏^1)`$ has $`r+1`$ isolated fixed points: $`(ra)[p_0]+a[p_1]`$, for $`0ar`$. For each graph $`\mathrm{\Gamma }`$, the morphism $`br`$ contracts $`\overline{M}_\mathrm{\Gamma }`$ to a fixed point of $`\text{Sym}^r(𝐏^1)`$. Therefore, $`br^{}(\xi )|_{\overline{M}_\mathrm{\Gamma }}=0`$ unless $`br(\overline{M}_\mathrm{\Gamma })=r[p_0].`$

Let $`[\pi :C𝐏^1]`$ be a stable map such that $`br(\pi )=r[p_0]`$. All nodes, collapsed components, and ramifications of $`\pi `$ must lie over $`p_0`$. Hence, if $`br(\overline{M}_\mathrm{\Gamma })=r[p_0]`$, the graph $`\mathrm{\Gamma }`$ may not have any vertices of positive genus or valence greater than 1 lying over $`p_1`$. Moreover, the degrees of the edges of $`\mathrm{\Gamma }`$ must all be 1.

Exactly one graph $`\mathrm{\Gamma }_0`$ satisfies $`br(\overline{M}_\mathrm{\Gamma })=r[p_0]`$. $`\mathrm{\Gamma }_0`$ is determined by the following construction. $`\mathrm{\Gamma }_0`$ has a unique genus $`g`$ vertex $`v_0`$ lying over $`p_0`$ which is incident to exactly $`d`$ degree 1 edges. The edges connect $`v_0`$ to $`d`$ unstable, unmarked vertices $`v_1^1,\mathrm{},v_1^d`$ of valence 1 and genus 0 lying over $`p_1`$.

By definition, $`\overline{M}_{\mathrm{\Gamma }_0}=\overline{M}_{g,d}`$. Since the automorphism group of $`\mathrm{\Gamma }_0`$ is the full permutation group of the edges, $`|A_{\mathrm{\Gamma }_0}|=d!`$. The vertex contributions of the Euler class of the normal complex were found in Section 6.3.8:

$$\frac{1}{N(v_0)}=\frac{t^gt^{g1}\lambda _1+t^{g2}\lambda _2t^{g3}\lambda _3+\mathrm{}+(1)^g\lambda _g}{_{i=1}^d(t\psi _i)}t^1,$$

for the unique vertex over $`p_0`$ and

$$\frac{1}{N(v_1^i)}=1,$$

for each of the $`d`$ unstable vertices over $`p_1`$.

By the excess intersection formula, the class $`br^{}(\xi )|_{\overline{M}_\mathrm{\Gamma }}`$ is the $`^{}`$-equivariant Euler class of the normal bundle of the point $`r[p_0]`$ in $`\text{Sym}^r(𝐏(V))`$:

$$br^{}(\xi )|_{\overline{M}_{\mathrm{\Gamma }_0}}=r!t^r,$$

easily computed, for example, via the canonical isomorphism

$$\text{Sym}^r(𝐏^1)=𝐏(\text{Sym}^rV^{}).$$

The sum (7.1) contains only one term:

$$H_{g,d}=\frac{(1)^d}{|A_{\mathrm{\Gamma }_0}|}_{\overline{M}_{\mathrm{\Gamma }_0}}\frac{br^{}(\xi )}{_{vV}N(v)}.$$

After substitution of the identified factors, we find:

Theorem 2. (For $`H_{g,d}`$).

$$H_{g,d}=\frac{(2g2+2d)!}{d!}_{\overline{M}_{g,d}}\frac{1\lambda _1+\lambda _2\lambda _3+\mathrm{}+(1)^g\lambda _g}{_{i=1}^d(1\psi _i)},$$

for $`(g,d)(0,1),(0,2)`$.

The genus 0 formula,

$$H_{0,d}=\frac{(2d2)!}{d!}d^{d3},$$
(7.2)
immediately follows from Theorem 2 together with the evaluations:

$$_{\overline{M}_{0,n}}\psi _1^{a_1}\mathrm{}\psi _n^{a_n}=\left(\genfrac{}{}{0pt}{}{n3}{a_1,\mathrm{},a_n}\right).$$

Equation (7.2) was first found by Hurwitz.

#### 7.3 The Hurwitz number $`H_{g,\mu }`$

##### 7.3.1 Overview

The proof of Theorem 2 for $`H_{g,\mu }`$ requires a study of maps with fixed profile over $`\mathrm{}`$. However, the strategy of Section 7.2 is maintained. The Hurwitz number $`H_{g,\mu }`$ is first identified as an integral over a restricted moduli space of maps. Then, Theorem 2 is deduced from a vertex contribution via the virtual residue formula. The presentation here follows .

##### 7.3.2 Moduli spaces and integrals

Let $`C`$ be a nonsingular genus $`g`$ curve. Let $`\pi :C𝐏^1`$ be a map with profile $`\mu =(m_1,\mathrm{},m_l)`$ over $`p_1=\mathrm{}`$. Let $`d=|\mu |`$ be the degree of $`\pi `$. Let $`r=2g2+d+l`$ be the number of simple ramifications of $`\pi `$ over finite points. Let $`k=_i(m_i1)=dl`$. The branch morphism is:

$$br:\overline{M}_g(𝐏^1,d)\text{Sym}^{r+k}(𝐏^1)=𝐏^{r+k}.$$

Let $`L_k`$ denote the linear subspace of $`\text{Sym}^{r+k}(𝐏^1)`$ defined by:

$$L_k=\{D+k[p_1]|D\text{Sym}^r(𝐏^1)\}.$$

As $`\pi `$ has profile $`\mu `$ over $`p_1`$, the branch divisor satisfies $`br(\pi )L_k`$. Define $`\overline{M}_g(L_k)`$ by the $`^{}`$-equivariant fiber square:

$$\begin{array}{ccc}\overline{M}_g(L_k)& & \overline{M}_g(𝐏^1,d)\\ br_k& & br& & \\ L_k& \stackrel{\iota }{}& \text{Sym}^{r+k}(𝐏^1).\end{array}$$
(7.3)
A virtual class of dimension $`r`$ is induced on $`\overline{M}_g(L_k)`$ by the Gysin map:

$$[\overline{M}_g(L_k)]^{vir}=\iota ^![\overline{M}_g(𝐏^1,d)]^{vir}.$$

Theorem 2 is proven by virtual localization on $`\overline{M}_g(L_k)`$.

As before, let $`M_g(𝐏^1,d)`$ be the open moduli space of maps with nonsingular domains. By Proposition 5.2, $`M_g(𝐏^1,d)`$ is a nonsingular Deligne-Mumford stack of pure dimension $`r+k`$. Let $`M_g(\mu )M_g(𝐏^1,d)`$ denote the (reduced) substack of maps with profile $`\mu `$ over $`p_1`$. $`M_g(\mu )`$ is of pure dimension $`r`$. Let

$$M_g(\mu )\overline{M}_g(\mu )$$

denote the closure.

$`\overline{M}_g(\mu )`$ is a substack of $`\overline{M}_g(L_k)`$ equal to a union of irreducible components. The restricted branch divisor is well-defined:

$$br_k=\overline{M}_g(\mu )L_k.$$

Let $`\xi _p`$ denote (the Poincaré dual of) the point class of $`L_k`$.

###### Proposition 7.2.

The Hurwitz number $`H_{g,\mu }`$ is an integral:

$$H_{g,\mu }=_{[\overline{M}_g(\mu )]}br_k^{}(\xi _p).$$

Proof. The integral is well-defined as $`\overline{M}_g(\mu )`$ is of pure dimension $`r`$. By Bertini’s Theorem, a general point $`_{i=1}^r[z_i]+k[p_1]`$ of $`L_k`$ intersects the stack $`\overline{M}_g(\mu )`$ transversely via $`br_k`$ in a finite number of nonsingular points of $`M_g(\mu )`$. These intersections are exactly the finitely many Hurwitz covers $`H_{g,\mu }`$ simply ramified over $`\{z_i\}`$ (weighted by $`1/|\text{Aut}|`$ in the intersection product). ∎

##### 7.3.3 Multiplicity

The moduli space $`M_g(\mu )M_g(𝐏^1,d)`$ occurs as an open set of the intersection $`br^1(L_k)M_g(𝐏^1,d)`$. The multiplicity of $`br^1(L_k)M_g(𝐏^1,d)`$ along $`M_g(\mu )`$ will be required in the proof of Theorem 2.

###### Lemma 7.3.

The intersection $`br^1(L_k)M_g(𝐏^1,d)`$ is of uniform multiplicity

$$\text{mult}(\mu )=k!\underset{i=1}{\overset{l}{}}\frac{m_i^{m_i1}}{m_i!}$$

along $`M_g(\mu )`$.

Proof. Let $`mr+k`$. Let $`x_1,\mathrm{},x_m`$ be distinct points of $`𝐏^1`$. Define the linear space $`L(x_1,\mathrm{},x_m)\text{Sym}^{r+k}(𝐏^1)`$ by:

$$L(x_1,\mathrm{},x_m)=\{D+\underset{i=1}{\overset{m}{}}[x_i]|D\text{Sym}^{r+km}(𝐏^1)\}.$$

Let $`[\pi ]M_g(\mu )`$ be a map with simple ramification over the points $`z_1,\mathrm{}z_r𝐏^1`$. Assume the linear space $`L(z_1,\mathrm{},z_r)`$ intersects $`M_g(\mu )`$ transversely via $`br`$ at nonsingular reduced points (including $`[\pi ]`$). The assumption holds for all $`[\pi ]`$ in a dense open subset of $`M_g(\mu )`$ by Bertini’s Theorem.

Let $`\{z_j^{}(s)\}_{j=1}^k`$ be holomorphic paths in $`𝐏^1`$ satisfying:

1. $`z_{j_1}^{}(s)z_{j_2}^{}(s)`$, for all $`j_1j_2`$ and $`0s`$,
2. $`z_j^{}(0)=p_1`$, for all $`j`$.

The substacks $`br^1(L(z_1^{}(s),\mathrm{},z_k^{}(s)))M_g(𝐏^1,d)`$ form a flat family specializing to $`br^1(L_k)M_g(𝐏^1,d)`$ at $`s=0`$.

For all except finitely many special values of $`s`$, $`z_iz_j^{}(s).`$ At nonspecial values, $`L(z_1,\mathrm{},z_r)`$ intersects $`br^1(L(z_1^{}(s),\mathrm{},z_k^{}(s)))`$ transversely via $`br`$ at nonsingular reduced points corresponding to $`H_{g,d}`$ Hurwitz covers with simple ramification over $`\{z_i\}\{z_j^{}(s)\}`$.

Let $`H(s)`$ denote the set of the Hurwitz covers specified by $`s`$. Let $`H(\pi )H(s)`$ be the subset of Hurwitz covers which specialize to $`[\pi ]`$ as $`s0`$. The multiplicity of $`br^1(L_k)`$ at $`[\pi ]`$ is equal to $`|H(\pi )|`$.

$`H(s)`$ is equal to the set of $`(r+k)`$-tuples of 2-cycles

$$(\gamma _1,\mathrm{},\gamma _r,\gamma _1^{},\mathrm{}\gamma _k^{})$$

modulo $`S_d`$-conjugation satisfying:

1. $`\gamma _1,\mathrm{},\gamma _r,\gamma _1^{},\mathrm{},\gamma _k^{}`$ generate a transitive subgroup of $`S_d`$,
2. $`_{i=1}^r\gamma _i_{j=1}^k\gamma _j^{}=1`$.

Let $`c_{m_1}\mathrm{}c_{m_l}S_d`$ be a fixed element with cycle decomposition $`\mu `$. The elements $`H(\pi )H(s)`$ bijectively correspond to solutions of the equation:

$$\underset{j=1}{\overset{k}{}}\gamma _j^{}=c_{m_1}\mathrm{}c_{m_l}.$$
(7.4)
The number of solutions of (7.4) is proven to equal

$$k!\underset{i=1}{\overset{l}{}}\frac{m_i^{m_i1}}{m_i!}$$

in Lemma 7.4 below. ∎

###### Lemma 7.4.

The equation $`_{j=1}^k\gamma _j^{}=c_{m_1}\mathrm{}c_{m_l}S_d`$ has

$$k!\underset{i=1}{\overset{l}{}}\frac{m_i^{m_i1}}{m_i!}$$

solutions for $`k`$-tuples $`(\gamma _1^{},\mathrm{},\gamma _k^{})`$.

Proof. A $`2`$-cycle $`(x_1x_2)`$ lies in the span of a cycle $`c=(y_1\mathrm{}y_m)`$ if

$$\{x_1,x_2\}\{y_1,\mathrm{},y_m\}.$$

Each solution of

$$\underset{j=1}{\overset{k}{}}\gamma _j^{}=c_{m_1}\mathrm{}c_{m_l}$$
(7.5)
has the following property: for each $`i`$, exactly $`m_i1`$ of the $`2`$-cycles $`\gamma _j^{}`$ lie in the span of $`c_{m_i}`$.

An elegant proof of the above property is given in . A solution of (7.4) defines a degree $`d`$ cover $`D𝐏^1`$ with simple ramifications determined by $`\{\gamma _j^{}\}`$ at fixed finite points $`q_1,\mathrm{}q_k`$ and profile $`\mu `$ over $`p_1`$. The arithmetic genus of $`D`$ is $`1l`$ by the Riemann-Hurwitz formula. As the preimage of $`p_1`$ contains $`l`$ nonsingular points of $`D`$, $`D`$ has at most $`l`$ components. Hence, $`D`$ must consist of exactly $`l`$ disconnected genus 0 components $`_{i=1}^lD_i`$. Each $`D_i`$ is fully ramified over $`p_1`$ with profile $`m_i`$. Therefore, $`D_i`$ must be simply ramified over exactly $`m_i1`$ finite points. The proof of the property is complete.

As the number of factorizations of an $`m`$-cycle into $`m1`$ transpositions in $`S_m`$ is well-known to be $`m^{m2}`$, the solutions of (7.5) are now easily counted:

$$\left(\genfrac{}{}{0pt}{}{k}{m_11,\mathrm{},m_l1}\right)\underset{i=1}{\overset{l}{}}m_i^{m_i2}=k!\underset{i=1}{\overset{l}{}}\frac{m_i^{m_i1}}{m_i!}.$$

##### 7.3.4 Localization

The virtual localization formula for $`\overline{M}_g(𝐏^1,d)`$ yields:

$$[\overline{M}_g(L_k)]^{vir}=\underset{\mathrm{\Gamma }G_g(𝐏^1,d)}{}\frac{1}{|A_\mathrm{\Gamma }|}\frac{\tau _\mathrm{\Gamma }[\overline{M}_\mathrm{\Gamma }]br^{}[L_k]}{e(N_\mathrm{\Gamma }^{vir})}$$
(7.6)
in $`A_{}^{^{}}(\overline{M}_g(L_k))_{[\frac{1}{t}]}`$ via the Gysin map.

Let $`\xi `$ be the $`^{}`$-equivariant lift of the point class $`\xi _p`$ of $`L_k`$ corresponding to the $`^{}`$-fixed point $`r[p_0]+k[p_1]L_k`$. The integral

$$_{[\overline{M}_g(L_k)]^{vir}}br_k^{}(\xi )$$
(7.7)
is determined by the localization formula (7.6).

However, the Hurwitz number $`H_{g,\mu }`$ is not equal to (7.7), but rather to the corresponding integral over $`\overline{M}_g(\mu )`$ by Proposition 7.2. The central result is the identification of the contribution of $`\overline{M}_g(\mu )`$ to the integral (7.7).

Let $`\mathrm{\Gamma }_\mu `$ be the following distinguished graph. $`\mathrm{\Gamma }_\mu `$ has a unique genus $`g`$ vertex $`v_0`$ lying over $`p_0`$ which is incident to exactly $`l`$ edges of degrees $`m_1,\mathrm{},m_l`$. The edges connect $`v_0`$ to $`l`$ unstable, unmarked vertices $`v_1^1,\mathrm{},v_1^l`$ of valence 1 and genus 0 lying over $`p_1`$.

###### Proposition 7.5.

$$mult(\mu )_{\overline{M}_g(\mu )}br_k^{}(\xi )=\frac{1}{|A_{\mathrm{\Gamma }_\mu }|}_{\overline{M}_{\mathrm{\Gamma }_\mu }}\frac{br^{}[L_k]br_k^{}(\xi )}{e(N_{\mathrm{\Gamma }_\mu }^{vir})}.$$

Proposition 7.5 is proven in Section 7.3.6 below.

By definition, $`\overline{M}_{\mathrm{\Gamma }_\mu }=\overline{M}_{g,l}`$. The order of the automorphism group is easily determined:

$$|A_{\mathrm{\Gamma }_\mu }|=|\text{Aut}(\mu )|\underset{i=1}{\overset{l}{}}m_i.$$

The vertex contributions of the Euler class of the normal complex,

$$\frac{1}{e(N_{\mathrm{\Gamma }_\mu }^{vir})}=\frac{1}{_{vV}N(v)},$$

were found in Section 6.3.8:

$$\frac{1}{N(v_0)}=\frac{t^gt^{g1}\lambda _1+t^{g2}\lambda _2t^{g3}\lambda _3+\mathrm{}+(1)^g\lambda _g}{_{i=1}^d(\frac{t}{m_i}\psi _i)}t^{l1d}\underset{i=1}{\overset{l}{}}\frac{m_i^{m_i}}{m_i!},$$

for the unique vertex over $`p_0`$ and

$$\frac{1}{N(v_1^i)}=\frac{t^{1m_i}}{m_i}\frac{m_i^{m_i}}{m_i!},$$

for the $`i^{th}`$ unstable vertex over $`p_1`$.

By the excess intersection formula, the class

$$br^{}(L_k)br_k^{}(\xi )|_{\overline{M}_\mathrm{\Gamma }}=(1)^kr!k!t^{r+k}$$

is the $`^{}`$-equivariant Euler class of the normal bundle of the point $`r[p_0]+k[p_1]`$ in $`\text{Sym}^{r+k}(𝐏^1)`$.

After substitution of these identified factors, Propositions 7.2 \- 7.5 and Lemma 7.3 yield Theorem 2. The Hurwitz number $`H_{g,\mu }`$ equals

$$\frac{(2g2+|\mu |+l)!}{|\text{Aut}(\mu )|}\underset{i=1}{\overset{l}{}}\frac{m_i^{m_i}}{m_i!}_{\overline{M}_{g,l}}\frac{1\lambda _1+\lambda _2\lambda _3+\mathrm{}+(1)^g\lambda _g}{_{i=1}^l(1m_i\psi _i)},$$

in the stable range $`2g2+\mathrm{}(\mu )>0`$.

##### 7.3.5 Localization isomorphisms

The following result proven in  will be used several times in the proof of Proposition 7.5.

###### Lemma 7.6.

Let $`V`$ be an algebraic variety (or Deligne-Mumford stack) equipped with a $`^{}`$-action. Let

$$\iota :_iV_i^fV$$

be the inclusion of the connected components of the $`^{}`$-fixed locus of $`V`$. Then $`\iota _{}`$ is an isomorphism after localization:

$$\iota _{}:\underset{i}{}A_{}^{^{}}(V_i^f)_{[\frac{1}{t}]}\stackrel{}{}A_{}^{^{}}(V)_{[\frac{1}{t}]}.$$
(7.8)
Proof. We prove the result in case $`V`$ admits a nonsingular $`^{}`$-equivariant embedding $`VY`$. The full result in proven in .

The surjectivity of $`\iota _{}`$ after localization follows from the right exact sequence of equivariant Chow groups of a closed inclusion:

$$A_{}^{^{}}(_iV_i^f)A_{}^{^{}}(V)A_{}^{^{}}(U)0.$$

Since $`U`$ admits a fixed point free $`^{}`$-action, there is an isomorphism

$$A_{}^{^{}}(U)\stackrel{}{=}A_{}(U/^{}).$$

The right Chow group has finite grading (as $`U/^{}`$ is a finite dimensional algebraic variety (or Deligne-Mumford stack)) . Therefore, $`A_{}^{^{}}(U)`$ is $`t`$-torsion and vanishes after localization.

Injectivity is easily proven in case $`V`$ admits an equivariant nonsingular embedding $`VY`$. Let

$$j:Y^fY$$

denote the inclusion of the $`^{}`$-fixed locus. $`Y^f`$ is nonsingular (but possibly disconnected) Let $`N`$ denote the normal bundle of $`Y^fY`$. Since $`Y^fV=_iV_i^f`$, there is a Gysin map obtained by intersection with $`Y_f`$ in $`Y`$:

$$j^!:A^{^{}}(V)\underset{i}{}A^{^{}}(V_i^f).$$

The composition $`j^!\iota _{}`$ is equal to multiplication by $`e(N)`$. As $`e(N)`$ is invertible after localization, $`\iota `$ is injective after localization. ∎

As the moduli space $`\overline{M}_g(𝐏^1,d)`$ admits $`^{}`$-equivariant nonsingular embeddings, Lemma 7.6 will only be used in the restricted case considered in the proof.

##### 7.3.6 Proof of Proposition 7.5

Let $`X_0=\overline{M}_g(\mu )`$. $`X_0`$ is a union of irreducible components of $`\overline{M}_g(\mu )`$ of pure dimension $`r`$. Let $`_{j0}X_j=\overline{M}_g(L_k)`$ where $`\{X_j\}_{j1}`$ are the remaining irreducible components of $`\overline{M}_g(\mu )`$. The virtual class admits a (non-canonical) decomposition:

$$[\overline{M}_g(L_k)]^{vir}=\iota _{}\underset{j0}{}R_jA_r^{^{}}(\overline{M}_g(L_k)),$$

where $`R_jA_r^{^{}}(X_j)`$. Since $`X_0`$ is of multiplicity $`mult(\mu )`$ in $`br^1(L_k)M_g(𝐏^1,d)`$,

$$R_0=mult(\mu )[X_0].$$

The classes $`\{R_j\}_{j1}`$ are quite difficult to describe.

The $`^{}`$-fixed loci of $`\overline{M}_g(L_k)`$ correspond to the set of graphs

$$G_g(\mu )G_g(𝐏^1,d)$$

satisfying $`br(\overline{M}_\mathrm{\Gamma })L_k`$. Let $`Q_\mathrm{\Gamma }=\overline{M}_\mathrm{\Gamma }/A_\mathrm{\Gamma }`$ denote the $`^{}`$-fixed locus corresponding to $`\mathrm{\Gamma }`$ (as in Section 6.3.3). The localization formula (7.6) may be written as:

$$[\overline{M}_g(L_k)]^{vir}=\iota _{}\underset{\mathrm{\Gamma }G_g(𝐏^1,d)}{}C_\mathrm{\Gamma }A_{}^{^{}}(\overline{M}_g(L_k))_{[\frac{1}{t}]},$$

where $`C_\mathrm{\Gamma }A_{}^{^{}}(Q_\mathrm{\Gamma })_{[\frac{1}{t}]}`$.

To prove Proposition 7.5, we must show:

$$_{\overline{M}_g(L_k)}\iota _{}R_0br_k^{}(\xi )=_{\overline{M}_g(L_k)}\iota _{}C_{\mathrm{\Gamma }_\mu }br_k^{}(\xi ).$$
(7.9)
For each $`j0`$, we may use the localization isomorphism of Lemma 7.6 to uniquely determine classes $`R_{j,\mathrm{\Gamma }}A_{}^{^{}}(Q_\mathrm{\Gamma })_{[\frac{1}{t}]}`$ satisfying:

$$\iota _{}R_j=\iota _{}\underset{\mathrm{\Gamma }G_g(\mu )}{}R_{j,\mathrm{\Gamma }}.$$

The localization isomorphism implies:

$$\underset{j0}{}R_{j,\mathrm{\Gamma }}=C_\mathrm{\Gamma }$$

for all $`\mathrm{\Gamma }G_g(\mu )`$.

We may rewrite the desired equation (7.9) in the following form:

$$_{\overline{M}_g(L_k)}\iota _{}\underset{\mathrm{\Gamma }G_g(\mu )}{}R_{0,\mathrm{\Gamma }}br_k^{}(\xi )=_{\overline{M}_g(L_k)}\iota _{}\underset{j0}{}R_{j,\mathrm{\Gamma }_\mu }br_k^{}(\xi ).$$
(7.10)
It will therefore suffice to prove the following vanishing results:

1. $`_{\overline{M}_g(L_k)}\iota _{}R_{0,\mathrm{\Gamma }}br_k^{}(\xi )=0`$ for $`\mathrm{\Gamma }\mathrm{\Gamma }_\mu `$,
2. $`_{\overline{M}_g(L_k)}\iota _{}R_{j,\mathrm{\Gamma }_\mu }br_k^{}(\xi )=0`$ for $`j0`$.

A study of the component geometry of $`\overline{M}(L_k)`$ will be required to prove (i) and (ii).

Let $`\mathrm{\Gamma }G_g(\mu )`$ and let $`br(\overline{M}_\mathrm{\Gamma })=a_{\mathrm{\Gamma },0}[p_0]+a_{\mathrm{\Gamma },1}[p_1]`$. The inequality

$$a_{\mathrm{\Gamma },1}k$$

holds since $`br(\overline{M}_\mathrm{\Gamma })L_k`$. If $`a_{\mathrm{\Gamma },1}>k`$, then $`[Q_\mathrm{\Gamma }]br_k^{}(\xi )=0`$ as $`\xi `$ is the class corresponding to the $`^{}`$-fixed point $`r[p_0]+k[p_1]`$. Since $`R_{j,\mathrm{\Gamma }}A_r^{^{}}(Q_\mathrm{\Gamma })_{[\frac{1}{t}]}`$, we find the trivial vanishing:

1. $`R_{j,\mathrm{\Gamma }}br_k^{}(\xi )=0`$ if $`a_{\mathrm{\Gamma },1}>k`$.

As $`X_j`$ is a $`^{}`$-equivariant locus, we may apply the localization isomorphism to decompose $`R_j`$ on the $`^{}`$-fixed locus of $`X_j`$. By uniqueness, we conclude another trivial vanishing:

1. $`R_{j,\mathrm{\Gamma }}=0`$ if $`X_jQ_\mathrm{\Gamma }=\mathrm{}`$.

Proof of (i). The fixed locus $`Q_{\mathrm{\Gamma }_\mu }`$ meets $`X_0=\overline{M}_g(\mu )`$. In fact the limit

$$\text{Lim}_{t0}t[\pi ]$$

of every element of $`M_g(\mu )`$ lies in $`Q_{\mathrm{\Gamma }_\mu }`$ (see ).

Define a stable map $`\pi `$ to have nonsingular profile $`\mu `$ over $`p_1`$ if $`\pi ^1(\mu )`$ is a divisor of shape $`\mu `$ lying in the nonsingular locus of the domain. A limit $`[\pi ]`$ of elements in $`M_g(\mu )`$ must either have nonsingular profile $`\mu `$ or degenerate over $`p_1`$. Any degeneration is easily seen to increase the branching order of $`\pi `$ over $`p_1`$. As $`Q_{\mathrm{\Gamma }_\mu }`$ is the unique fixed locus with nonsingular profile $`\mu `$ over $`p_1`$, $`Q_{\mathrm{\Gamma }_\mu }`$ is the unique fixed locus meeting $`\overline{M}_g(\mu )`$ with branching order exactly $`k`$ over $`p_1`$. Vanishings (a) and (b) then imply (i).

Proof of (ii). Let $`j0`$. By vanishing (b), we may assume $`X_jQ_{\mathrm{\Gamma }_\mu }\mathrm{}`$. Since $`X_j\overline{M}_g(L_k)`$, every element $`[\pi ]X_j`$ corresponds to a map with branching order at least $`k`$ over $`p_1`$. Since $`X_jQ_{\mathrm{\Gamma }_\mu }\mathrm{}`$, the general map $`[\pi ]X_j`$ must have nonsingular profile $`\mu `$ over $`p_1`$.

As in the proof of (i), $`Q_{\mathrm{\Gamma }_\mu }`$ must be the unique fixed locus meeting $`\overline{M}_g(\mu )`$ with branching order exactly $`k`$ over $`p_1`$.

Maps $`\pi `$ with no contracted components and nonsingular profile $`\mu `$ over $`p_1`$ are easily shown to be limits of $`M_g(\mu )`$. As $`X_jX_0`$, the general map $`[\pi ]X_j`$ must contain a domain component collapsed away from $`p_1`$. By the definition of the branch morphism, $`br(\pi )`$ then lies in the singular sublocus $`L_k^{sing}L_k`$:

$$L_k^{sing}=\{D+k[p_1]|D=2[x_1]+[x_2]+\mathrm{}+[x_{r1}]\text{Sym}^r(𝐏^1)\}.$$

As $`L_k^{sing}`$ is a proper subvariety, the following integral vanishes:

$$_{\overline{M}_g(L_k)}\iota _{}R_jbr_k^{}(\xi )=0.$$
(7.11)
By the localization isomorphism, the integral (7.11) may be rewritten as

$$_{\overline{M}_g(L_k)}\iota _{}\underset{a_{\mathrm{\Gamma },1}=k}{}R_{j,\mathrm{\Gamma }}br_k^{}(\xi )+\iota _{}\underset{a_{\mathrm{\Gamma },1}>k}{}R_{j,\mathrm{\Gamma }}br_k^{}(\xi )=0.$$

The second sum vanishes completely by (a). As $`\mathrm{\Gamma }=\mathrm{\Gamma }_\mu `$ is the unique graph satisfying $`a_{\mathrm{\Gamma },1}=k`$ and $`X_jQ_\mathrm{\Gamma }\mathrm{}`$, all other term in the first sum vanish by (b). We conclude:

$$_{\overline{M}_g(L_k)}\iota _{}R_{j,\mathrm{\Gamma }_\mu }=0$$

for $`j0`$.

The proof of Proposition 7.5 is complete. ∎

## Part III Asymptotics of Hurwitz numbers

### 8 Random trees

#### 8.1 Overview

The analysis of the $`N\mathrm{}`$ asymptotics of the Hurwitz numbers $`H_{g,N\mu }`$ via the asymptotic enumeration of branching graphs will require a study of trees. Trees naturally arise via edge terms in the homotopy classification of branching graphs. The enumerative and probabilistic results for trees which will be required are discussed here. The asymptotic analysis of $`H_{g,N\mu }`$ is undertaken in Section 9.

Section 8.2 contains a minimal discussion of probabilistic terminology. Section 8.3 is a review of the basic enumeration formulas for trees. The required properties of random edge trees are discussed in Sections 8.4-8.6.

The literature on trees and random trees is very large. An excellent place to start is Chapter 5 of . An introduction from a more probabilistic perspective can be found in . Many asymptotic properties of random trees find a unified treatment in the theory of continuous random trees due to Aldous . Fortunately, all the properties of random trees that we shall need are quite basic. Instead of locating them in the literature, we will prove these properties from first principles.

The trees that we will consider naturally come with a choice of two distinguished vertices (a root and a top). Random trees are more often studied with one special vertex (rooted trees) or with no special vertices (plain trees). The properties we will require are simpler in the presence of a root and a top. The analogous results for rooted trees are less elementary both to state and to prove.

#### 8.2 Review of probabilistic terminology

A probability space is a triple $`(\mathrm{\Omega },𝔅,P)`$, where $`\mathrm{\Omega }`$ is any nonempty set, $`𝔅`$ is a $`\sigma `$-algebra of subsets of $`\mathrm{\Omega }`$ called the algebra of events, and

$$P:𝔅_0$$

is a measure such that $`P(\mathrm{\Omega })=1`$. We will primarily be concerned with finite sets $`\mathrm{\Omega }`$: $`𝔅`$ will then include all subsets of $`\mathrm{\Omega }`$, and $`P`$ will typically be the uniform probability measure. When the probability measure is understood, it will be denoted by the symbol $`\mathrm{Prob}`$.

Any measurable function

$$X:\mathrm{\Omega }^k$$

is called a vector-valued *random variable*. The push-forward measure $`X_{}P`$ on $`^k`$ is called the distribution of $`X`$. The integral

$$X=_\mathrm{\Omega }X(\omega )P(d\omega )=_^kxX_{}P(dx)$$

is called the expectation of $`X`$. Two random variables $`X`$ and $`Y`$ are said to be independent if the distribution of their direct sum $`XY`$, also known as the joint distribution of $`X`$ and $`Y`$, is a product-measure.

A sequence $`\{𝗆_n\}`$ of measures on $`^k`$ is said to converge weakly to a measure $`𝗆`$ if

$$_^kf(x)𝗆_n(dx)_^kf(x)𝗆(dx)$$

for any bounded continuous function $`f`$. A sequence of random variables $`X_n`$ on a sequence of probability spaces $`(\mathrm{\Omega }_n,𝔅_n,P_n)`$ is said to converge in distribution to a random variable $`X_{\mathrm{}}`$ if the measures $`𝗆_n=(X_n)_{}P_n`$ converge weakly to the distribution of $`X_{\mathrm{}}`$, or, equivalently, if

$$f(X_n)f(X_{\mathrm{}}),n\mathrm{},$$

for any bounded continuous function $`f`$.

In particular, $`X_n`$ converge in distribution to the variable identically equal to $`0`$ if

$$\mathrm{Prob}(X_nU)1$$

for any neighborhood of $`U`$ of $`0`$. A basic continuity property of convergence in distribution, which we will use often, is the following standard result (see, for example, ).

###### Lemma 8.1.

Let $`X_n`$ and $`Y_n`$, $`n=1,2,\mathrm{},\mathrm{}`$, be vector-valued random variables on a sequence $`(\mathrm{\Omega }_n,𝔅_n,P_n)`$ of probability spaces. If, as $`n\mathrm{}`$, we have

$$X_nX_{\mathrm{}},X_nY_n0,$$

in distribution, then also

$$Y_nX_{\mathrm{}}$$

in distribution.

###### Proof.

Let $`X`$ denote a vector norm of $`X`$ and consider the function

$$g_{AB}:_0[0,1]$$

such that $`g_{AB}(x)=0`$ for $`x>B`$, $`g_{AB}(x)=1`$ for $`x<A`$ and $`g_{AB}`$ linearly interpolates between $`1`$ and $`0`$ on $`[A,B]`$. Clearly, for any $`X`$,

$$\mathrm{Prob}\{XA\}g_{AB}(X)\mathrm{Prob}\{XB\}.$$

For any $`ϵ>0`$, we can find $`A`$ such that

$$\mathrm{Prob}\{X_{\mathrm{}}A\}>1ϵ.$$

By hypothesis, for any $`A`$ and $`B`$ we have

$$g_{AB}(X_n)g_{AB}(X_{\mathrm{}}),n\mathrm{}.$$

Therefore, for any $`B>A`$,

$$\mathrm{Prob}\{X_nB\}>12ϵ$$

for all sufficiently large $`n`$. For any $`C>B`$, we have

$$\mathrm{Prob}\{Y_nX_n>CB\}0,$$

and, therefore, for all sufficiently large $`n`$ we have

$$\mathrm{Prob}\{X_nK\}>12ϵ,\mathrm{Prob}\{Y_nK\}>13ϵ,$$

where $`K`$ denotes the compact set

$$K=\{X,XC\}.$$

Since $`f`$ is continuous and $`K`$ is compact, $`f`$ is uniformly continuous on $`K`$ and hence there exists $`\delta >0`$ such that

$$|f(X)f(Y)|<ϵ,$$

whenever $`X,YK`$ and $`XY<\delta `$. We can choose $`n`$ large enough so that

$$\mathrm{Prob}\{X_nY_n<\delta \}>1ϵ.$$

Collecting all estimates, we obtain

$$\left|f(X_n)f(Y_n)\right|ϵ(1+12\mathrm{max}|f|).$$

for all sufficiently large $`n`$. Since $`ϵ`$ is arbitrary, the Lemma follows. ∎

The above Lemma will often be used in the following situation. Suppose there exists a “good” subset

$$\mathrm{\Omega }_n^{}\mathrm{\Omega }_n$$

such that on this good subset we have

$$\underset{\omega \mathrm{\Omega }_n^{}}{sup}|X_n(\omega )Y_n(\omega )|0,n\mathrm{},$$

and also such that, asymptotically, most $`\omega `$ are good, that is,

$$\mathrm{Prob}\mathrm{\Omega }_n^{}1,n\mathrm{}.$$

In this case, Lemma 8.1 implies that if $`X_n`$ has a limit in distribution then $`Y_n`$ converges to the same limit.

#### 8.3 Enumeration of trees

##### 8.3.1 Definitions

A tree $`(V,E)`$ is a connected graph with no circuits. Let $`𝖳(n)`$ denote the set of trees with $`n`$ vertices. We will consider trees $`T`$ with additional structures: vertex and edge labels, and distinguished vertices.

Labelings of vertices and edges are bijections

$$\varphi _V:V\{1,2,3,\mathrm{},|V|\},$$

$$\varphi _E:E\{1,2,3,\mathrm{},|E|\}.$$

We will denote the set of vertex marked trees with $`n`$ vertices by $`𝖵(n)`$. Let $`𝖤(n)`$ denote the set of edge marked trees with $`n`$ vertices.

One of the vertices of a tree $`T`$ may be designated as a distinguished vertex, called the *root* of $`T`$. The tree $`T`$ is this case is called a *rooted tree*. Let $`𝖳^1(n)`$ denote the set of rooted trees with $`n`$ vertices. Similarly, let $`𝖵^1(n)`$ and $`𝖤^1(n)`$ denote the sets $`n`$ vertex rooted trees with marked vertices and marked edges respectively.

In addition to the root vertex, one may choose a *top* vertex of $`T`$. The top vertex may or may not be allowed to coincide with the root vertex. Let $`𝖵^{11}`$ denote vertex marked trees with distinct root and top vertices. $`𝖵^2`$ will denote the larger set in which root and top are allowed to coincide. Let $`𝖤^{11}`$ and $`𝖤^2`$ denote the corresponding sets for edge marked trees.

Of these flavors of trees, two will be particularly important for us and deserve special names. Edge marked trees will be also called *branching trees*, and the $`𝖤^{11}`$-trees will be called *edge trees*. Edge trees naturally arise in the study of the edge contributions in the asymptotic analysis of branching graphs (see Section 9), whence the name. The term branching tree is justified by the following:

###### Lemma 8.2.

A branching tree with $`n`$ vertices is isomorphic to the data of a branching graph on the sphere $`\mathrm{\Sigma }_0`$ with perimeter $`(n)`$, where $`(n)`$ denotes the length 1 partition of $`n`$.

Proof. First, we make a general remark. By definition, the edges of a branching graph are labeled by roots of unity, whereas the edges of an edge marked tree $`T𝖤(n)`$ are labeled by $`1,2,3,\mathrm{},n1`$. We will identify the two kinds of labeling using the bijection

$$\{1,\mathrm{},n1\}ke^{2\pi ik/(n1)}U_{n1}.$$

A branching tree $`T`$ can be canonically (up to homeomorphism) embedded in an oriented sphere $`\mathrm{\Sigma }_0`$. The embedding is uniquely determined by the following condition: the cyclic order induced on the edges incident to each vertex by the orientation of $`\mathrm{\Sigma }_0`$ must agree with the cyclic order of the markings of the edges. The tree $`T\mathrm{\Sigma }_0`$ then defines a branching graph on $`\mathrm{\Sigma }_0`$ (see Section 3.1).

Conversely, every branching graph on $`\mathrm{\Sigma }_0`$ must be a tree (as the complement determines 1 cell). The edge markings then determine a branching tree structure. ∎

##### 8.3.2 Automorphisms and counting

Trees $`TT(n)`$ may have non-trivial automorphism groups. However, labelled trees in the sets $`𝖵(n)`$ and $`𝖤(n)`$ admit no non-trivial automorphisms preserving their markings, the only exception being the unique element of $`𝖤(2)`$.

We will exclusively count labelled trees (with distinguished vertices). Therefore, by the number of trees, we will mean the actual number (except in the $`𝖤(2)`$ case where the number is set, by definition, to $`1/2`$ in order to account for the order 2 automorphism group). Similarly, when considering random labelled trees, we will always take the uniform probability measure on the corresponding set.

##### 8.3.3 Cayley’s formula and its consequences

We recall the following fundamental result about trees:

###### Proposition 8.3 (Cayley).

We have

$$\underset{T𝖵(n)}{}\underset{i=1}{\overset{n}{}}z_i^{\mathrm{val}(i)}=z_1\mathrm{}z_n(z_1+\mathrm{}+z_n)^{n2}$$
(8.1)
where the summation is over all trees $`T`$ with vertex set $`\{1,\mathrm{},n\}`$ and $`\mathrm{val}(i)`$ denotes the valence of the vertex $`i`$ in the tree $`T`$.

See, for example , Theorem 5.3.4, for a proof of this formula. The formula (8.1) has a large number of corollaries.

###### Corollary 8.4.

We have

$`|𝖵(n)|`$ $`=n^{n2},`$ $`|𝖤(n)|`$ $`=n^{n3},`$
$`|𝖵^1(n)|`$ $`=n^{n1},`$ $`|𝖤^1(n)|`$ $`=n^{n2},`$
$`|𝖵^{11}(n)|`$ $`=(n1)n^{n1},`$ $`|𝖤^{11}(n)|`$ $`=(n1)n^{n2},`$
$`|𝖵^2(n)|`$ $`=n^n,`$ $`|𝖤^2(n)|`$ $`=n^{n1},`$
Recall that $`|𝖤(2)|=1/2`$, by our convention, reflects the order 2 automorphism group of the unique element of $`𝖤(2)`$.

###### Proof.

The enumeration of $`𝖵(n)`$ is obtained by setting $`z_i=1`$, $`i=1\mathrm{}n`$, in Cayley’s formula (8.1).

Given a vertex marked tree $`T`$ with $`n`$ vertices, one can mark its edges in $`(n1)!`$ ways. The vertex marking can then be removed by dividing by $`n!`$ which gives $`|𝖤(n)|=n^{n3}`$. The remaining formulas are obvious. ∎

###### Corollary 8.5.

The number of trees in $`𝖵(n)`$ such that the valence $`\mathrm{val}(1)`$ of the vertex $`1`$ is $`k+1`$ equals $`(n1)^{nk2}\left(\genfrac{}{}{0pt}{}{n2}{k}\right)`$.

This is obtained by setting $`z_i=1`$, $`i=2\mathrm{}n`$, in (8.1) and extracting the coefficient of $`z_1^{k+1}`$.

Consider the probability that in a uniformly random vertex marked tree $`T𝖵(n)`$ the valence $`\mathrm{val}(1)`$ of the vertex marked by $`1`$ equals $`k+1`$. We have

$$\mathrm{Prob}\left\{\mathrm{val}(1)=k+1\right\}=\frac{(n1)^{nk2}\left(\genfrac{}{}{0pt}{}{n2}{k}\right)}{n^{n2}}\frac{e^1}{k!},n\mathrm{}.$$

In other words, the valence distribution of a given vertex in a large random tree converges in distribution to one plus a Poisson random variable with mean 1.

This observation has an immediate generalization for the joint distribution of valences of several vertices. Given a vertex $`vT`$, let us call the number $`\mathrm{val}(v)1`$ the *excess valence* of the vertex $`v`$.

###### Corollary 8.6.

As $`n\mathrm{}`$, the excess valences of vertices of a random tree $`T𝖵(n)`$ converge in distribution to independent Poisson random variables with mean $`1`$.

Recall that a forest is graph which is a disjoint union of trees. A forest is rooted if a distinguished vertex, called root, is specified in each connected component.

###### Corollary 8.7.

The number of rooted forests with with vertex set $`\{1,\mathrm{},n\}`$ and $`k`$ connected components is equal to $`k\left(\genfrac{}{}{0pt}{}{n}{k}\right)n^{nk1}`$.

###### Proof.

There exits a simple bijection between rooted forests that we want to enumerate and trees with vertex set $`\{0,1,\mathrm{},n\}`$ such that the vertex $`0`$ is $`k`$-valent. We just add new edges which join $`0`$ to the roots of the forests. Now we apply Corollary 8.5. ∎

##### 8.3.4 Factorization into transpositions and trees

By Definition 3.2, the Hurwitz number $`H_{0,(n)}`$ equals the automorphism weighted count of branching graphs on the sphere $`\mathrm{\Sigma }_0`$ with one cell of perimeter $`n`$. By Corollary 8.4, $`H_{0,(n)}=n^{n3}`$.

By Definition 3.3, $`H_{0,(n)}`$ is also equal to $`(1/n!)`$ times the number of $`(n1)`$-tuples of transpositions in $`S_n`$ with product in the conjugacy class of an $`n`$-cycle. Equivalently, $`nH_{0,(n)}`$ equals the number of solution to the equation:

$$\gamma _1\mathrm{}\gamma _{n1}=(123\mathrm{}n)S_n,$$

for $`2`$-cycles $`\gamma _iS_n`$.

We therefore obtain the following classical result (used in the proof of Lemma 7.4 in Section 7.3.3):

###### Corollary 8.8.

The number of factorization of an $`n`$ cycle into $`n1`$ transpositions in $`S_n`$ is $`n^{n2}`$.

Corollary 8.8 is a particular case of a formula due to Hurwitz  and was also discovered by Dénes .

#### 8.4 Trunk of a random edge tree

Given $`T𝖤^{11}(n)`$, denote by $`\mathrm{tk}T`$ the trunk of $`T`$, that is, the shortest path from then root to the top in $`T`$. Let $`|\mathrm{tk}T|`$ denote the number of vertices in the trunk of $`T`$. We are interested in the distribution of this quantity with respect to the uniform probability measure on $`𝖤^{11}(n)`$ as $`n\mathrm{}`$.

Recall that an exponential random variable $`\xi `$ with mean $`1`$ is, by definition, the variable with distribution density $`e^xdx`$ on $`[0,+\mathrm{})`$. The random variable $`\sqrt{2\xi }`$, which has the density $`xe^{x^2/2}dx`$ on the half-line $`(0,\mathrm{})`$, is called a *Rayleigh* random variable.

###### Proposition 8.9.

As $`n\mathrm{}`$, the random variable $`{\displaystyle \frac{1}{\sqrt{n}}}|\mathrm{tk}T|`$, where $`T`$ is a random edge tree with $`n`$ vertices, converges in distribution to a Rayleigh random variable.

###### Proof.

The same distribution of trunk heights is obtained if, instead of edge trees, we consider random elements of $`𝖵^{11}(n)`$. The notion of trunk and its height have an obvious analog for such trees.

Given a tree $`T𝖵^{11}(n)`$ with $`|\mathrm{tk}T|=k`$ and $`n`$ vertices, we can associate to it a forest with $`k`$ components by deleting the trunk path $`\mathrm{tk}T`$ from $`T`$. This forest comes with an additional structure, namely, an ordering on the components of the forest. Since there are $`k!`$ possible orderings, we conclude using Corollary 8.7 that the probability to have $`|\mathrm{tk}T|=k`$ equals

$$kk!\left(\genfrac{}{}{0pt}{}{n}{k}\right)n^{nk1}/(n1)n^{n1}=\frac{k}{n1}\underset{i=1}{\overset{k1}{}}\left(1\frac{i}{n}\right).$$
(8.2)
If $`k=x\sqrt{n}`$ then, as $`n\mathrm{}`$, we have

$$\mathrm{ln}\underset{i=1}{\overset{k1}{}}\left(1\frac{i}{n}\right)\frac{1}{n}\underset{i=1}{\overset{k1}{}}ix^2/2,$$

hence the probability (8.2) is asymptotic to $`{\displaystyle \frac{1}{\sqrt{n}}}xe^{x^2/2}`$, which completes the proof. ∎

###### Corollary 8.10.

For any $`ϵ>0`$, we have

$$\mathrm{Prob}\left\{|\mathrm{tk}T|>n^{1/2+ϵ}\right\}0,n\mathrm{},$$

with respect to the uniform probability measure on $`𝖤^{11}(n)`$.

The trunk of a tree $`T`$ appears in the literature under various names. See, for example, . In particular, our trunk is called the spine of $`T`$ in .

#### 8.5 Size of the root component of a random tree

Given $`T𝖤^{11}(r)`$, consider the edges incident to the root vertex. One of these edges belongs to the trunk $`\mathrm{tr}T`$, we will call it the *trunk edge*. One of the two components of $`T`$ that the trunk edge separates contains the root vertex, we call this component the root component of $`T`$. We define the *top component* of $`T`$ similarly and call the complement of the root and top components of $`T`$ the *trunk component* of $`T`$. These notions are illustrated in Figure 7

###### Proposition 8.11.

As $`n\mathrm{}`$, the probability that the root component of a random edge tree $`T𝖤^{11}(n)`$ contains $`k`$ vertices has limit $`{\displaystyle \frac{k^{k1}}{k!}}e^k`$.

###### Proof.

As in proof of Proposition 8.9, we can replace random edge trees by random elements of $`𝖵^{11}`$. We can construct elements of $`𝖵^{11}(n)`$ with given root component of size $`k`$ as follows: partition the $`n`$ vertices into sets of order $`k`$ and $`nk`$, take an element of $`𝖵^1(k)`$ and an element of $`𝖵^2(nk)`$, join their roots by an edge, and choose the root of the first tree to be the root of the union.

It follows that the probability that the root component has size $`k`$ equals

$$\left(\genfrac{}{}{0pt}{}{n}{k}\right)\frac{k^{k1}(nk)^{nk}}{(n1)n^{n1}}\frac{k^{k1}}{k!}e^k,k\mathrm{},$$

where the asymptotics follow immediately from the Stirling formula (8.5). ∎

The root component of an element of $`𝖵^{11}(n)`$ determines a rooted tree in $`𝖳^1`$ after forgetting the vertex labels. The argument for Lemma 8.11 proves more precise statements.

###### Corollary 8.12.

The probability that $`T𝖳^1(k)`$ corresponds to the root component of a random tree $`T𝖵^{11}(n)`$ is asymptotic to

$$\frac{e^k}{|\mathrm{Aut}(T)|}$$

as $`n\mathrm{}`$.

###### Corollary 8.13.

The top component of random tree $`𝖵^{11}(n)`$ has the same distribution as the root component. Moreover, in the $`n\mathrm{}`$ limit, the root and top component distributions are independent.

The asymptotic probabilities of Proposition 8.11 determine a probability measure.

###### Lemma 8.14.

The measure $`\mathrm{Prob}(k)={\displaystyle \frac{k^{k1}}{k!}}e^k`$ is a probability measure on natural numbers.

###### Proof.

This can be seen, for example, from the equation

$$w(z)=ze^{w(z)},$$

satisfied by the function

$$w(z)=\underset{k=1}{\overset{\mathrm{}}{}}\frac{k^{k1}}{k!}z^k,$$

which is the generating function for $`|𝖵^1(k)|`$ and is, essentially, the same as the Lambert W-function. The equation implies that

$$1=w(1/e)=\underset{k=1}{\overset{\mathrm{}}{}}\frac{k^{k1}}{k!}e^k.$$

In fact, the measure $`\mathrm{Prob}(k)={\displaystyle \frac{k^{k1}}{k!}}e^k`$ is the Borel distribution  and is well known to appear in the context of branching processes and random trees. See, for example, Section 7 in .

Informally, Proposition 8.11 and Lemma 8.14 imply that the size of the root component of a typical tree stays finite as the size of the tree goes to infinity. A more formal statement is the following:

###### Corollary 8.15.

For any $`ϵ>0`$ there exists $`M`$ such that for all $`n`$ the probability that a random tree $`T𝖤^{11}(n)`$ has the root component with more than $`M`$ vertices is less than $`ϵ`$.

Similarly, we have:

###### Corollary 8.16.

For any sequence $`\{c_n\}`$ such that $`c_n\mathrm{}`$, the probability that a random tree $`T𝖤^{11}(n)`$ has the trunk component of size $`nc_n`$ goes to $`1`$ as $`n\mathrm{}`$. In other words, all but finitely many vertices of a typical large edge tree $`T`$ lie in the trunk component.

#### 8.6 Semiperimeters

##### 8.6.1 Definitions

Let $`T𝖤^{11}(n)`$ be an edge tree. Make $`T`$ planar as in Lemma 8.2 and let $`\lambda `$ be a path with follows the perimeter of $`T`$ once clockwise. Formally, $`\lambda `$ is a function

$$k\lambda _kE$$

periodic with period $`2n2`$, which lists the edges in the order of their appearance along the boundary of $`\mathrm{\Sigma }_0T`$.

Let $`\varphi :E\{1,\mathrm{},n1\}`$ be the marking of the edges of $`T`$ which is, by definition, a part of the structure of an edge tree. Define the angle between two edges $`e,e^{}E`$ by

$$\mathrm{}(e,e^{})=\frac{2\pi (\varphi (e^{})\varphi (e))}{n1}mod2\pi ,\mathrm{}(e,e^{})(0,2\pi ].$$
(8.3)
Consider the *perimeter* of $`\lambda `$ which, by definition, equals

$$\mathrm{per}(\lambda )=\frac{1}{2\pi }\underset{k=1}{\overset{2n1}{}}\mathrm{}(\lambda _k,\lambda _{k+1}).$$

Of course, $`\mathrm{per}(\lambda )=n`$ because every vertex contributes $`1`$ to the above sum.

We now want to split the path $`\lambda `$, and its perimeter, into two parts: the *root perimeter path* $`\lambda _R`$ and the *top perimeter path* $`\lambda _T`$. We proceed as follows. Let $`e_r,e_tE`$ denote the trunk edges at the root and the top of $`T`$, respectively. As we follow the path $`\lambda `$, these edges appear in cycles of the form

$$(e_r,\underset{\lambda _R}{\underset{}{\mathrm{},e_r,\mathrm{},e_t}},\mathrm{},e_t,\mathrm{}),$$

where the dots stand for other edges of $`T`$. The root part $`\lambda _R`$ starts after the first appearance of $`e_r`$ and ends with the first appearance of $`e_t`$ as shown above. Similarly, we define the top part $`\lambda _T`$. We also define the two perimeters, $`P_R`$ and $`P_T`$ as the perimeters of two paths $`\lambda _R`$ and $`\lambda _T`$, respectively, and call them the *semiperimeters* of $`T`$. Since the paths $`\lambda _R`$ and $`\lambda _T`$ are not closed, these semiperimeters may be fractional. The definition of $`\lambda _R`$ and $`\lambda _T`$ is illustrated in Figure 8

We also define the canonical marking

$$\psi :V\{1,\mathrm{},n\}$$

of the vertices $`V`$ by the order of their appearance in the concatenated path $`\lambda _R+\lambda _T`$.

##### 8.6.2 Perimeter estimates

Let us denote the root and top vertices by $`v_r`$ and $`v_t`$, respectively.

A basic consequence of the definitions is:

###### Lemma 8.17.

For $`T𝖤^{11}(n)`$, $`|P_R+P_Tn|2.`$

Proof. The difference between $`P_R+P_T`$ and the vertex number $`n`$ occurs from losses at $`v_r`$ and $`v_t`$. ∎

###### Lemma 8.18.

$`|P_R\psi (v_t)||\mathrm{tk}T|.`$

Proof. As we follow $`\lambda _R`$, every vertex on the trunk contributes $`1`$ to $`\psi (v_t)`$ and between $`0`$ and $`1`$ to $`P_R`$. Every other vertex contributes $`1`$ to both $`\psi (v_t)`$ and $`P_R`$. ∎

##### 8.6.3 Semiperimeter distribution

###### Proposition 8.19.

As $`n\mathrm{}`$, the normalized semiperimeter $`{\displaystyle \frac{P_R}{n}}`$ converges in distribution to the uniform distribution on $`[0,1]`$.

###### Proof.

Since, by Lemma 8.18,

$$\left|\frac{P_R}{n}\frac{\psi (v_t)}{n}\right|\frac{|\mathrm{tk}T|}{n}$$

and the right-hand side converges to $`0`$ in distribution by Corollary 8.10, it suffices to prove that $`{\displaystyle \frac{\psi (v_t)}{n}}`$ converges to the $`[0,1]`$-uniform random variable.

Consider the subset of $`𝖤^{11}(n)`$ formed by trees with the root component of fixed cardinality $`k\{1,2,\mathrm{}\}`$. Clearly, on this subset, $`\psi (v_t)`$ is uniformly distributed on the interval $`\{k+1,\mathrm{},n\}`$ and, hence, on this subset, $`{\displaystyle \frac{\psi (v_t)}{n}}`$ converges, in distribution, to the $`[0,1]`$-uniform random variable. Now Corollary 8.15 concludes the proof. ∎

##### 8.6.4 Perimeter measure

Let $`A_0^2`$ be a compact polygonal region. Define the perimeter measure $`𝗆^P(A)`$ by:

$$𝗆^P(A)=\underset{N\mathrm{}}{lim}\frac{1}{\sqrt{N}}\underset{n1}{}\underset{\begin{array}{c}T𝖤^{11}(n)\\ \\ (P_R(T),P_T(T))NA\end{array}}{}\frac{1}{e^n(n1)!},$$
(8.4)
where $`P_R(T)`$ and $`P_T(T)`$ denote the root and top perimeters of an edge tree $`T`$ and $`NA`$ denotes the region $`A`$ scaled by a factor of $`N`$.

###### Proposition 8.20.

We have:

$$𝗆^P(A)=\frac{1}{\sqrt{2\pi }}_A\frac{dxdy}{(x+y)^{3/2}}$$

###### Proof.

It suffices to prove the Proposition for the sets $`A`$ of the form

$$A_{c,d}=\{(x,y),(x+y)c,\frac{x}{x+y}d\},d[0,1].$$

It is clear, that in (8.4) we can replace the summation over $`n1`$ by the summation over $`nM`$ for any $`M`$, because the contribution of any particular value of $`n`$ is suppressed by the factor $`{\displaystyle \frac{1}{\sqrt{N}}}`$. By Proposition 8.19, choosing $`M`$ sufficiently large, we can make the distribution of $`{\displaystyle \frac{P_R}{P_R+P_T}}`$ be arbitrarily close to the uniform distribution on $`[0,1]`$, whence

$$𝗆^P(A_{c,d})=d𝗆^P(A_{c,1}).$$

The measure $`𝗆^P(A_{c,1})`$, by Lemma 8.17, just counts the number of trees of size $`cN`$, or, more concretely,

$$\begin{array}{c}𝗆^P(A_{c,1})=\underset{N\mathrm{}}{lim}\frac{1}{\sqrt{N}}\underset{n=1}{\overset{cN}{}}\frac{(n1)n^{n2}}{e^n(n1)!}=\hfill \\ \hfill \underset{N\mathrm{}}{lim}\frac{1}{\sqrt{N}}\underset{n=1}{\overset{cN}{}}\frac{1}{\sqrt{2\pi n}}=\underset{N\mathrm{}}{lim}\frac{1}{N}\underset{n=1}{\overset{cN}{}}\frac{1}{\sqrt{2\pi (n/N)}}=\frac{1}{\sqrt{2\pi }}_0^c\frac{dt}{\sqrt{t}},\end{array}$$

where the second equality uses the Stirling formula (see e.g. )

$$n!=\sqrt{2\pi n}\frac{n^n}{e^n}\left(1+O\left(\frac{1}{n}\right)\right)$$
(8.5)
and the last equality is by the definition of the integral. This determines the measure $`𝗆^P`$ uniquely and concludes the proof. ∎

##### 8.6.5 Independence of semiperimeters and root/top components

The analysis in Section 8.6.3 can be repeated exactly to obtain the asymptotics of the normalized perimeter $`{\displaystyle \frac{P_R}{n}}`$ for trees with fixed root and top components. Concretely, suppose the fixed root and top components have $`k`$ and $`l`$ vertices respectively. Then, by moving the point where the top component is attached to the trunk component, one sees that on this set $`\psi (v_t)`$ is uniformly distributed on the interval $`\{k+1,\mathrm{},nl+1\}`$. Hence, $`{\displaystyle \frac{\psi (v_t)}{n}}`$ converges to the uniform distribution on $`[0,1]`$. Using Corollary 8.15 we conclude that:

###### Proposition 8.21.

In the limit $`n\mathrm{}`$, the normalized perimeter $`{\displaystyle \frac{P_R}{n}}`$ of a random tree $`T𝖤^{11}(n)`$ is independent of the root and top components of $`T`$ and, in particular, independent of the valences of the root and top vertices of $`T`$.

##### 8.6.6 Effect of relabeling the edges

Recall that, by definition, the edges of an edge tree $`T𝖤^{11}`$ come with a bijective labeling

$$\varphi :E\{1,2,\mathrm{},n1\}.$$

This labeling goes into the definition of the angle (8.3) between two adjacent edges of $`T`$.

Suppose we have a monotone injective map

$$\sigma :\{1,2,\mathrm{},n1\}\{1,2,\mathrm{},N\},Nn1,$$

using which we modify the definition (8.3) as follows:

$$\stackrel{~}{\mathrm{}}(e,e^{})=\frac{2\pi }{N}(\sigma (\varphi (e^{}))\sigma (\varphi (e)))mod2\pi ,\stackrel{~}{\mathrm{}}(e,e^{})(0,2\pi ],$$

and, accordingly, we introduce modified semiperimeters $`\stackrel{~}{P}_R`$ and $`\stackrel{~}{P}_T`$. Because the vertices which do not belong to the trunk still contribute $`1`$ to $`\stackrel{~}{P}_R`$ or $`\stackrel{~}{P}_T`$, respectively, we have

$$\left|\frac{\stackrel{~}{P}_R}{n}\frac{P_R}{n}\right|\frac{|\mathrm{tk}T|}{n}.$$

Recall that by Corollary 8.10 the right-hand side converges to $`0`$ in distribution as $`n\mathrm{}`$.

### 9 Asymptotics of the Hurwitz numbers

#### 9.1 Overview

Let $`\mu `$ be a partition with $`l`$ distinct parts. By Definition 3.2, the Hurwitz number $`H_{g,\mu }`$ is a weighted count of the branching graphs on $`\mathrm{\Sigma }_g`$ with perimeter $`\mu `$. By Proposition 3.4, the asymptotics of $`H_{g,N\mu }`$ as $`N\mathrm{}`$ recover the $`l`$-point function $`P_g(\mu _1,\mathrm{},\mu _l)`$ defined in (3.3). In the present section, we compute these asymptotics using results about random trees obtained in Section 8.

Instead of analyzing the asymptotics of $`H_{g,N\mu }`$ for particular partitions $`\mu `$, we will study the Hurwitz asymptotics averaged over a neighborhood $`U`$ of $`\mu `$ values, that is, the asymptotics of the number

$$\underset{\nu NU}{}H_{g,\nu }$$
(9.1)
as $`N\mathrm{}`$. Here, the sum is over integral points $`\nu `$ of $`NU`$ (the set $`U`$ scaled by a factor of $`N`$). After weighting by functions of $`\nu `$, these asymptotics will define a Hurwitz measure $`𝗆_g(U)`$ of $`U`$ (see Section 9.2). The Hurwitz measure $`𝗆_g`$ will uniquely determine the $`l`$-point function $`P_g`$. The averaged data (9.1) arises naturally in the Laplace transform of the Hurwitz asymptotics required to recover Kontsevich’s series $`K_g`$ (2.8). We will find that the averaging leads to simplifications in the asymptotic analysis.

The Hurwitz measure $`𝗆_g`$ is analyzed by studying the distribution of cell perimeters of a random branching graph with a large total perimeter. The following strategy will be used. The branching graphs of genus $`g`$ with $`l`$ cells are partitioned into finitely many homotopy classes indexed by maps $`G𝖦_{g,l}^3`$ with vertices of valence $`3`$ and higher. Accordingly, the Hurwitz measure $`𝗆_g`$ is decomposed into a finite sum of contributions $`𝗆_G`$ of homotopy classes.

In Section 9.4, $`𝗆_G`$ is proven to vanish unless $`G`$ is trivalent. For a trivalent $`G`$, $`𝗆_G`$ is shown to be a push-forward under a linear map of a product measures which is the product of the perimeter measures $`𝗆^P`$ (see Section 8.6.4) over the edges of $`G`$. After the Laplace transform, we recover precisely the contribution of $`G`$ to Kontsevich’s combinatorial model (2.11). This establishes Theorem 4 and completes the proof of Theorem 1.

#### 9.2 Hurwitz measure

Let $`A_0^l`$ be a compact polygonal region. Define the genus $`g`$ Hurwitz measure $`𝗆_g(A)`$ by:

$$𝗆_g(A)=\underset{N\mathrm{}}{lim}\frac{1}{N^{3g3+3l/2}}\underset{\mu NA}{}\frac{H_{g,\mu }}{e^{|\mu |}r(g,\mu )!}.$$
(9.2)
Here, the sum is over integral points $`\mu `$ in $`NA`$ (the set $`A`$ scaled by the factor of $`N`$), and

$$r(g,\mu )=2g2+|\mu |+\mathrm{}(\mu )$$

is a number of simple ramifications of a genus $`g`$ Hurwitz cover corresponding to the partition $`\mu `$.

###### Proposition 9.1.

The Hurwitz measure is determined by:

$$𝗆_g(A)=_AH_g(x)𝑑x_1\mathrm{}𝑑x_l.$$

Proof. $`H_g(x)`$ is defined on rational points $`x_{>0}^l`$ satisfying $`x_ix_j`$ by:

$$H_g(x_1,\mathrm{},x_l)=\underset{N\mathrm{}}{lim}\frac{1}{N^{3g3+l/2}}\frac{H_{g,Nx}}{e^{d(Nx)}r(g,Nx)!}.$$

$`H_g(x)`$ is a polynomial function by Theorem 2. The Proposition then follows directly from Stirling’s formula (8.5) and the definition of the Riemann integral. ∎

The Laplace transformed measure $`L𝗆_g`$ is then determined as a function of $`y_1,\mathrm{},y_l`$ by the equivalent formulas:

$`L𝗆_g(A)`$ $`=`$ $`\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N^{3g3+3l/2}}}{\displaystyle \underset{\mu NA}{}}e^{y\mu /N}{\displaystyle \frac{H_{g,\mu }}{e^{|\mu |}r(g,\mu )!}}`$
$`=`$ $`{\displaystyle _A}e^{yx}H_g(x)𝑑x_1\mathrm{}𝑑x_l`$
By construction,

$`LH_g(y_1,\mathrm{},y_l)`$ $`=`$ $`{\displaystyle _{_0^l}}e^{yx}H_g(x)𝑑x_1\mathrm{}𝑑x_l`$
$`=`$ $`L𝗆_g(_0^l).`$
Our strategy, introduced in Section 3.4, is to express $`L𝗆_g(A)`$ as a sum of contributions of the possible homotopy types $`G𝖦_{g,l}^3`$. We define

$$𝗆_G(A)=\underset{N\mathrm{}}{lim}\frac{1}{N^{3g3+3l/2}}\underset{\mu NA}{}\frac{H_{G,\mu }}{e^{|\mu |}r(g,\mu )!},$$
(9.3)
where the number $`H_{G,\mu }`$ is counting branching graphs with homotopy type $`G`$, see Section 3.4.

The limit $`𝗆_G(A)`$ will be shown to exist for all $`G𝖦_{g,l}^3`$ and, in fact, shown to vanish unless $`G`$ is trivalent.

#### 9.3 Assembling branching graphs from edge trees

Fix a homotopy type $`G𝖦_{g,l}^3`$ with $`|E|`$ edges. Denote by $`𝖧_{G,\mu }`$ the set of all branching graphs with homotopy type $`G`$ and perimeter $`\mu `$. We will use the following procedure for enumerating all elements of $`𝖧_{G,\mu }`$.

We will use the symbol $`\left({\displaystyle \genfrac{}{}{0pt}{}{r}{r_1,\mathrm{},r_k}}\right)`$ to denote both the multinomial coefficient and the corresponding set of $`k`$-tuples of subsets of an $`r`$-element set. Fix an arbitrary orientation of the edges of $`G`$. There exists a natural *assembly map*

$$\mathrm{Asm}_G:\underset{r_1,\mathrm{},r_{|E|}}{}\left(\genfrac{}{}{0pt}{}{r}{r_1,\mathrm{},r_{|E|}}\right)\times \underset{i=1}{\overset{|E|}{}}𝖤^{11}(r_i+1)\underset{|\mu |=r+22gl}{}𝖧_{G,\mu }\{\mathbf{}\},$$
(9.4)
which is defined as follows.

Let $`e_1,\mathrm{},e_{|E|}`$ be the edges of $`G`$ and let

$$T_1,\mathrm{},T_{|E|}$$

be an $`|E|`$-tuple of edge trees. First, we replace, preserving the order, the edge markings of each tree by a subset of the set $`U_r`$ of $`r`$th roots of unity according to the given element of $`\left({\displaystyle \genfrac{}{}{0pt}{}{r}{r_1,\mathrm{},r_{|E|}}}\right)`$.

After that, we replace each oriented edge $`e_i`$ of $`G`$ by the corresponding edge tree $`T_i𝖤^{11}(r_i+1)`$ in such a way that the root vertex of $`T_i`$ is identified with the initial vertex of $`e_i`$ and the top vertex of $`T_i`$ is identified with the final vertex of $`e_i`$.

This replacement is done so that at the vertices $`v`$ of $`G`$ the edges coming from the same tree $`T_i`$ have consecutive places in the clockwise order around $`v`$ with the trunk edge being the last one.

This procedure is illustrated in Figure 9 where it is shown how the tree from Figures 7 and 8 may be used in the assembly of a branching graph.

In Figure 9, the vertices of different trees are shown in different color and those vertices which are shared by several trees (the ones which correspond to the vertices of the graph $`G`$) are painted accordingly. Also observe how the trunks of the trees in Figure 9 form the edges of the homotopy type graph $`G`$.

The resulting graph $`H`$ is a branching graph if the edge labels of $`H`$ at each vertex $`v`$ respect the cyclic order of the roots of unity. If $`H`$ is a branching graph, then define $`\mathrm{Asm}_G=H`$. Otherwise, the assembly result is declared a failure, indicated by the formal symbol $`\mathrm{Asm}_G=\mathbf{}`$.

The group $`\mathrm{Aut}(G)`$ acts<sup>1</sup><sup>1</sup>1 This action is always free, whereas the action on just edges of $`G`$ may not be as the $`(g,n)=(1,1)`$ example shows. on the oriented edges of $`G`$. This action makes $`\mathrm{Aut}(G)`$ act on the domain of the assembly map by permutation of factors in the Cartesian product and reversal of the root/top choice in individual factors. The following property of the assembly map is obvious from its construction:

###### Proposition 9.2.

The assembly map is surjective and for any $`H\mathbf{}`$ the preimage $`\mathrm{Asm}_G^1(H)`$ is a single $`\mathrm{Aut}(G)`$-orbit.

We will call the edge trees in $`\mathrm{Asm}_G^1(H)`$ the *edge parts* of a branching graph $`H`$, ignoring the minor ambiguity coming from the action of $`\mathrm{Aut}(G)`$.

#### 9.4 Vanishing for non-trivalent graphs

Fix a homotopy type $`G`$ and let $`|E|`$ be the number of edges in $`G`$. From the equation

$$r=2g2+|\mu |+l$$

and Corollary 8.4 we have

$$\begin{array}{c}\frac{1}{e^{|\mu |}r!}\left(\genfrac{}{}{0pt}{}{r}{r_1,\mathrm{},r_{|E|}}\right)\times \underset{i=1}{\overset{|E|}{}}\left|𝖤^{11}(r_i+1)\right|=\hfill \\ \hfill e^{|E|+l+2g2}\underset{i=1}{\overset{|E|}{}}\frac{\left|𝖤^{11}(r_i+1)\right|}{e^{r_i+1}r_i!}\frac{e^{|E|+l+2g2}}{(2\pi )^{|E|}}\frac{1}{\sqrt{r_i}},\end{array}$$
(9.5)
as $`r_i\mathrm{}`$. By Proposition 9.2, this implies that

$$\underset{|\mu |N}{}\frac{1}{e^{|\mu |}r!}H_{G,\mu }=O\left(\underset{i=1}{\overset{|E|}{}}\underset{r_i=1}{\overset{N}{}}\frac{1}{\sqrt{r_i}}\right)=O\left(N^{|E|/2}\right),N\mathrm{}.$$

It follows that the limit (9.3) vanishes unless

$$|E|=6g6+3l,$$

which is equivalent to $`G`$ being trivalent. Thus, we have established the following:

###### Proposition 9.3.

If the homotopy type $`G`$ is not trivalent, then $`𝗆_G=0`$.

Further, for a trivalent graph $`G`$ we can assume the edge trees which participate in the assembly map to be arbitrarily large. This is because the contribution of edge trees of any fixed size to $`𝗆_G`$ obviously vanishes for the same reason as above.

This puts us in the asymptotic regime of large random edge trees, which was considered in Section 8. In particular, in this regime

$$\left|\mathrm{Asm}_G^1(H)\right|=|\mathrm{Aut}(G)|,$$

for a typical branching graph $`H`$. This is because the probability of having two isomorphic edge parts or an edge part which has an automorphism permuting root and top clearly goes to zero as the size of the edge parts goes to infinity.

#### 9.5 Probability of assembly failure

In particular, let us compute the probability that for large random edge trees the assembly (9.4) will end in failure $`\mathbf{}`$. In other words, we want to compute the probability that the cyclic order condition will be violated at one of the vertices $`v`$ of a trivalent graph $`G`$.

Suppose we have three random disjoint sequences $`X_i`$, $`i=1,2,3`$ of elements of a some cyclically ordered set. The conditional probability that the concatenation

$$X_1,X_2,X_3$$

is cyclically ordered, given that each $`X_i`$ is cyclically ordered and $`|X_i|=k_i`$, $`i=1,2,3`$, is easily seen to be equal to

$$\frac{(k_11)!(k_21)!(k_31)!}{(k_1+k_2+k_31)!}.$$

In our case, the cyclically ordered set is the set $`U_r`$ of $`r`$th roots of unity and the sequences $`X_i`$ are the labels of the edges incident to the 3 root/top vertices $`v_1`$, $`v_2`$, $`v_3`$ that are glued together at $`v`$.

The probability that the valence if $`v_i`$ in the corresponding tree equals $`k_i`$ approaches, by Corollary 8.6, the limit $`e^1/(k_i1)!`$ as the size of tree goes to infinity. Therefore, the probability of failure at a given vertex $`v`$ converges to

$$\begin{array}{c}e^3\underset{k_1,k_2,k_3=1}{\overset{\mathrm{}}{}}\frac{1}{(k_1+k_2+k_31)!}=\hfill \\ \hfill e^3\underset{k=3}{\overset{\mathrm{}}{}}\underset{k_1+k_2+k_3=k}{}\frac{1}{(k1)!}=\frac{e^3}{2}\underset{k=3}{\overset{\mathrm{}}{}}\frac{(k1)(k2)}{(k1)!}=\frac{e^2}{2}.\end{array}$$
(9.6)
Also, we see that at each vertex $`v`$, the probability to fail depends only on the three valences $`k_1`$, $`k_2`$, $`k_3`$ involved, and hence, in the limit of large random edge trees, failures at vertices of $`G`$ become independent events by Corollary 8.12.

Since a trivalent graph $`G`$ has $`4g4+2l`$ vertices, we obtain the following conclusion (the second assertion follows from Proposition 8.21)

###### Proposition 9.4.

For any trivalent homotopy type $`G`$, the probability of assembly failure goes to

$$e^{8g+84l}\mathrm{\hspace{0.17em}2}^{4g+42l}$$

as the sizes of all edge trees go to infinity. Further, assembly failure is asymptotically independent of the normalized semiperimeters of the edge trees involved.

#### 9.6 Computation of the Hurwitz measure

By definition (9.3), the Hurwitz measure $`𝗆_G(A)`$ involves the asymptotics of the weighted number of branching graphs $`H`$ of homotopy type $`G`$ such that

$$\frac{\mu }{N}A,$$

where $`\mu `$ is the perimeter of $`H`$.

Let $`D`$ be a cell of $`H`$. The boundary $`D`$, followed in the clockwise direction, is a sequences of edges

$$e_1,e_2,\mathrm{},e_s,e_iE(H).$$

The perimeter of $`D`$ is, by definition, the following sum

$$\mathrm{per}(D)=\frac{1}{2\pi }\underset{k=1}{\overset{s}{}}\mathrm{arg}\left(\frac{\gamma (e_k)}{\gamma (e_{k+1})}\right).$$
(9.7)
where $`\gamma :E(H)U_r`$ is the labeling of the edges of $`H`$ by roots of unity, the argument takes values in $`(0,2\pi ]`$, and $`e_{s+1}=e_1`$.

For most terms in (9.7) both $`e_k`$ and $`e_{k+1}`$ belong to the same edge part of $`H`$. The only exception are the terms corresponding to the vertices of $`G`$ on the boundary of $`D`$. The contribution of these exceptional terms to $`\mathrm{per}(D)`$ is bounded by $`4g4+2l`$ because the contribution of each of the $`4g4+2l`$ vertices of $`G`$ to $`\mathrm{per}(D)`$ is bounded by $`1`$. Since we are interested in the distribution of $`{\displaystyle \frac{\mathrm{per}(D)}{N}}`$ as $`N\mathrm{}`$, this contribution may be ignored.

Further, we can substitute the contribution of each edge part of $`H`$ by the semiperimeter of the corresponding edge tree $`T`$. The difference between these two numbers is that the first is computed using the labeling $`\gamma `$ of $`E(T)`$ by the $`r`$th roots of unity, whereas the second uses the labeling

$$\varphi :E(T)\{1,2,\mathrm{},|E(T)|\}$$

which is a part of the structure of an edge tree. By the results of Section 8.6.6 the difference between these two numbers is of the order of magnitude $`\sqrt{N}`$. In particular, the probability of having a difference of size $`N^{1/2+ϵ}`$ goes to zero for any $`ϵ>0`$. This means that the effect of this difference on $`{\displaystyle \frac{\mathrm{per}(D)}{N}}`$ is negligible in the $`N\mathrm{}`$ limit.

It follows that, asymptotically, $`{\displaystyle \frac{\mathrm{per}(D)}{N}}`$ is a sum of independent random variables which are the normalized semiperimeters of the edge parts of $`H`$ along the boundary of $`D`$. Recall that the distribution of the normalized semiperimeters of a random edge tree is governed by the perimeter measure $`𝗆^P`$, which was studied in Section 8.6.4. Together with (9.5) and Proposition 9.4, we conclude the following:

###### Proposition 9.5.

For any $`G𝖦_{g,l}^3`$, we have

$$𝗆_G=\frac{2^{4g+42l}}{|\mathrm{Aut}(G)|}\left(\mathrm{asm}_G\right)_{}\left(\underset{E(G)}{}𝗆^P\right)$$

where the product of perimeter measures is over all edges of $`G`$ and $`\mathrm{asm}_G`$ is the linear map which takes the normalized semiperimeters to their sums along the boundaries of the cells of $`G`$.

This result can be more conveniently stated in terms of the Laplace transform

$$L𝗆_G(y_1,\mathrm{},y_l)=_{_{>0}^l}e^{yx}𝗆_G(dx),$$

for which it implies the following factorization

$$L𝗆_G(y)=\frac{2^{4g+42l}}{|\mathrm{Aut}(G)|}\underset{eE(G)}{}L𝗆^P(y_{i(e)},y_{j(e)}),$$

where $`i(e)`$ and $`j(e)`$ are the numbers of the cells of $`G`$ that the edge $`e`$ separates and $`L𝗆^P`$ is the Laplace transform of the perimeter measure $`𝗆^P`$.

It remains, therefore, to compute $`L𝗆^P`$ which by Proposition 8.20 equals the following integral

$$L𝗆^P(y_1,y_2)=\frac{1}{\sqrt{2\pi }}_0^{\mathrm{}}\frac{e^{x_1y_1x_2y_2}}{(x_1+x_2)^{3/2}}𝑑x_1𝑑x_2,$$

where $`y_1,y_2>0`$.

Making a change of variables

$$x_1+x_2=u,x_1x_2=v,$$

and integrating out $`v`$, we obtain

$$L𝗆^P(y_1,y_2)=\frac{1}{\sqrt{2\pi }}\frac{1}{y_1y_2}_0^{\mathrm{}}\left(e^{y_1u}e^{y_2u}\right)\frac{du}{u^{3/2}}.$$

For $`\mathrm{}\alpha >1`$ we have

$$_0^{\mathrm{}}\left(e^{y_1u}e^{y_2u}\right)u^{\alpha 1}𝑑u=\mathrm{\Gamma }(\alpha )\left(\frac{1}{y_1^\alpha }\frac{1}{y_2^\alpha }\right)$$

which for $`\mathrm{}\alpha >0`$ follows from the definition of the $`\mathrm{\Gamma }`$-function and can be extended to $`\mathrm{}\alpha >1`$ by analytic continuation because the integral remains absolutely convergent. Since

$$\mathrm{\Gamma }(1/2)=2\sqrt{\pi },$$

plugging in $`\alpha =1/2`$, we obtain

$$L𝗆^P(y_1,y_2)=\frac{\sqrt{2}}{\sqrt{y_1}+\sqrt{y_2}}.$$

Since a trivalent graph $`G`$ has $`6g6+3l`$ vertices, it follows that

$$L𝗆_G(y)=\frac{2^{2g2+l}}{|\mathrm{Aut}(G)|}\underset{eE(G)}{}\frac{1}{\sqrt{2y_{i(e)}}+\sqrt{2y_{j(e)}}}.$$

Finally, summing over all homotopy types $`G`$ and using the vanishing for nontrivalent homotopy types established in Proposition 9.3, we obtain the following:

###### Proposition 9.6.

We have

$$LH_g(y_1,\mathrm{},y_l)=\underset{G𝖦_{g,l}^3}{}\frac{2^{2g2+l}}{|\mathrm{Aut}(G)|}\underset{eE(G)}{}\frac{1}{\sqrt{2y_{i(e)}}+\sqrt{2y_{j(e)}}},$$

where the product is over all edges of a trivalent map $`G`$ and $`i(e)`$ and $`j(e)`$ are the numbers of the edge $`e`$ separates.

This Proposition completes the proof of Theorem 4. Theorems 3 and 4 imply Theorem 1 which, therefore, is established.

#### 9.7 Connection with the edge-of-the-spectrum matrix model

After studying the asymptotic enumeration of branching graphs on $`\mathrm{\Sigma }_g`$ with $`l`$ cells, we see that the problem is exactly parallel to the asymptotic enumeration of simple maps on $`\mathrm{\Sigma }_g`$ with $`l`$ cells carried out in .

As in the case of branching graphs, there exist only finitely many homotopy types of simple maps, of which only the trivalent homotopy types make a nonvanishing contribution to the asymptotics. The cell perimeters of a map are now exactly equal to the sums of semiperimeters of edge parts along the cell boundaries. An edge part of map is an unmarked planar tree with a choice of a root and top vertex (the semiperimeter distribution is easily seen to be asymptotically uniform).

This complete parallelism explains the equality (4.6) and therefore explains the connection between intersection theory of $`\overline{M}_{g,n}`$ and the matrix model (4.4).

#### 9.8 Lower order asymptotics

The lower order terms (in $`N`$) of the asymptotics of $`H_{g,N\mu }`$ govern Hodge integrals on $`\overline{M}_{g,l}`$ with integrand linear in the $`\lambda `$ classes. It appears quite difficult to extract lower order asymptotics from the random tree analysis. However, the lowest order term, related to the $`\lambda _g`$ integrals

$$\tau _{k_1}\mathrm{}\tau _{k_l}\lambda _g_g=_{\overline{M}_{g,l}}\psi _1^{k_1}\mathrm{}\psi _l^{k_l}\lambda _g,$$

is well-understood from a different perspective.

The $`\lambda _g`$ integrals arise in the degree 0 sector of the Virasoro conjecture for an elliptic target curve. In , the Virasoro conjecture for this degree 0 sector was shown to be equivalent to the following equation:

$$\tau _{k_1}\mathrm{}\tau _{k_l}\lambda _g_g=\left(\genfrac{}{}{0pt}{}{2g3+l}{k_1,\mathrm{},k_l}\right)\tau _{2g2}\lambda _g_g,$$
(9.8)
where $`\tau _2\lambda _0_0=1`$. The $`\lambda _g`$ conjecture (9.8) was later proven in  via virtual localization techniques (independent of the Hurwitz connection developed here). The integrals $`\tau _{2g2}\lambda _g_g`$ are determined by:

$$\underset{g0}{}t^{2g}\tau _{2g2}\lambda _g_g=\left(\frac{t/2}{\mathrm{sin}(t/2)}\right),$$

proven in .

Hodge integrals over the moduli space of curves are intimately related to Gromov-Witten theory via virtual localization, Virasoro constraints, Toda equations, and Mirror symmetry. Additional Hodge integral formulas and predictions may be found in .

### Appendix A Degeneration formulas for Hurwitz numbers

Classical recursive formulas for $`H_{g,\mu }`$ are obtained by studying the degenerations of covers as a finite branch point is moved to $`\mathrm{}`$. The recursions provide an elementary (though combinatorially complex) method of calculating $`H_{g,\mu }`$. We derive the degeneration formulas here from Definition 2 of the Hurwitz numbers following a suggestion of R. Vakil. There are very many different proofs of these formulas (see, for example, ).

A Hurwitz cover $`\pi :C𝐏^1`$ together with a marking of the fiber $`\pi ^1(\mathrm{})`$ is a marked Hurwitz cover. Let $`H_{g,\mu }^{}`$ denote the automorphism weighted count of marked Hurwitz covers with ramification $`m_i`$ at the $`i^{th}`$ marked point. We find:

$$H_{g,\mu }^{}=|\mathrm{Aut}(\mu )|H_{g,\mu }.$$

By Definition 2, $`H_{g,\mu }^{}`$ equals a count of distinct $`\mu `$-graphs $`H^{}`$ with marked cells on $`\mathrm{\Sigma }_g`$ (weighted by $`1/|\mathrm{Aut}(H^{})|`$). The Hurwitz numbers $`H_{g,\mu }^{}`$ are more convenient for the degeneration formulas.

Let $`\mu =(m_1,\mathrm{},m_l)`$ be a partition with positive parts. The following partition terminology will be needed:

1. $`\mu m_i`$ equals the partition (possibly empty) of length $`l1`$ obtained by deleting $`m_i`$.
2. $`\mu (m_i+m_j)`$ equals the partition of length $`l1`$ obtained by combining $`m_i`$ and $`m_j`$.
3. $`\mu (a_1+a_2=m_i)`$ equals the partition of length $`l+1`$ obtained by splitting $`m_i`$ into positive parts $`a_1`$ and $`a_2`$.
4. $`\mu +a`$ equals the partition of length $`l+1`$ obtained adding a positive part $`a`$.

Finally, let $`\mu _1+\mu _2`$ denote the union of the partitions $`\mu _1`$ and $`\mu _2`$.

As in Section 3.1, let $`r(g,\mu )=2g2+|\mu |+\mathrm{}(\mu )`$ be the number of finite branch points of the Hurwitz covers counted by $`H_{g,\mu }^{}`$. If $`r(g,\mu )`$ vanishes, then $`g=0`$ and $`\mu =(1)`$. In this case, $`H_{0,(1)}^{}=1`$. The Hurwitz numbers $`H_{g,\mu }^{}`$ are determined recursively by the following Theorem.

###### Theorem 7.

Let $`r(g,\mu )>0`$. The degeneration relation holds:

$`H_{g,\mu }^{}`$ $`=`$ $`{\displaystyle \underset{ij}{}}{\displaystyle \frac{m_i+m_j}{2}}H_{g,\mu (m_i+m_j)}^{}`$
$`+{\displaystyle \underset{i}{}}{\displaystyle \underset{a_1+a_2=m_i}{}}{\displaystyle \frac{a_1a_2}{2}}H_{g1,\mu (a_1+a_2=m_i)}^{}`$
$`+{\displaystyle \underset{i}{}}{\displaystyle \underset{a_1+a_2=m_i}{}}{\displaystyle \underset{g_1+g_2=g}{}}{\displaystyle \underset{\mu _1+\mu _2=\mu m_i}{}}ϵ{\displaystyle \frac{a_1a_2}{2}}H_{g_1,\mu _1+a_1}^{}H_{g_2,\mu _2+a_2}^{},`$
where $`ϵ`$ denotes a binomial coefficient in the last sum:

$$ϵ=\left(\genfrac{}{}{0pt}{}{r(g,\mu )1}{r(g_1,\mu _1+a_1)}\right).$$

Proof. The degeneration of a Hurwitz cover as a branch point is moved to $`\mathrm{}`$ corresponds simply to edge removal for the associated $`\mu `$-graphs.

Let $`H^{}`$ be a $`\mu `$-graph with marked cells on $`\mathrm{\Sigma }_g`$. Let $`r=r(g,\mu )`$. Let $`U_r`$ be the set of $`r^{th}`$ roots of unity marking the edges. There are three possibilities for the graph $`X`$ obtained after removal of the edge $`e`$ marked by the unit $`1U_r`$.

Case I. The edge $`e`$ separates two distinct cells of $`H^{}`$ with markings $`ij`$. Then, $`X`$ is canonically a $`\mu (m_i+m_j)`$-graph with marked cells on $`\mathrm{\Sigma }_g`$. The edge markings of $`X`$ lie in $`U_r\{1\}`$.

Conversely, let $`X`$ be a $`\mu (m_i+m_j)`$-graph with marked cells on $`\mathrm{\Sigma }_g`$. Let the edge markings of $`X`$ lie in set $`U_r\{1\}`$. Let $`D`$ be the cell corresponding to the part $`(m_i+m_j)`$. There are $`m_i+m_j`$ distinct ways an edge $`e`$ with marking $`1`$ may be added which separates $`D`$ into two cells of perimeters $`m_i`$ and $`m_j`$ and respects the edge orientation conditions.

Case II. The two sides of $`e`$ bound the same cell of $`H^{}`$ and $`e`$ is not a disconnecting edge. Then, $`X`$ is canonically a $`\mu (a_1+a_2=m_i)`$-graph with marked cells on $`\mathrm{\Sigma }_{g1}`$. Conversely, there are $`a_1a_2`$ ways to add $`e`$ to $`X`$ to recover a $`\mu `$-graph with marked cells on $`\mathrm{\Sigma }_g`$.

Case III. The two sides of $`e`$ bound the same cell $`H^{}`$ and $`e`$ is a disconnecting edge. Then, $`X=X_1X_2`$ is the union where $`X_i`$ is a $`\mu _i+a_i`$-graph with marked cells on $`\mathrm{\Sigma }_{g_i}`$. Conversely, there are $`a_1a_2`$ ways to add $`e`$ to $`X`$ to recover a $`\mu `$-graph with marked cells on $`\mathrm{\Sigma }_g`$.

The degeneration formula follows from counting these three cases (weighted by the possible locations of $`e`$). ∎

The degeneration formulas may be viewed as a first geometric approach to the Hurwitz numbers. Unfortunately, a direct analysis of $`H_{g,\mu }`$ via Theorem 7 appears combinatorially difficult. More efficient recursive strategies for the Hurwitz have been found (see ), but these formulas are genus dependent.

### Appendix B Integral tables

Hodge integrals on $`\overline{M}_{g,n}`$ are primitive if neither the string or dilaton equation may be applied. With the exception of $`\tau _0^3_0`$ and $`\tau _1_1`$, the primitive condition is equivalent to the absence of $`\tau _0`$ and $`\tau _1`$ factors in the integrand. The first table contains all primitive Hodge integrals with a single $`\lambda `$ class for $`g2`$.

$$\begin{array}{cc}& \\ g=0& \tau _0^3_0=1\\ & \\ g=1& \tau _1_1=1/24,\lambda _1_1=1/24\\ & \\ g=2& \tau _4_2=1/1152,\tau _3\tau _2_2=29/5760,\tau _2^3_2=7/240\\ & \\ & \tau _3\lambda _1_2=1/480,\tau _2^2\lambda _1_2=5/576\\ & \\ & \tau _2\lambda _2_2=7/5760\end{array}$$

The second table contains Hurwitz numbers $`H_{g,\mu }`$ for $`g2`$ and partitions $`\mu `$ satisfying $`|\mu |4`$.

$$\begin{array}{cccccccc}& & & & & & & \\ H_{g,\mu }& (1)& (2)& (1,1)& (3)& (2,1)& (1,1,1)& \\ & & & & & & & \\ g=0& 1& 1/2& 1/2& 1& 4& 4& \\ & & & & & & & \\ g=1& 0& 1/2& 1/2& 9& 40& 40& \\ & & & & & & & \\ g=2& 0& 1/2& 1/2& 81& 364& 364& \end{array}$$

$$\begin{array}{cccccccc}& & & & & & & \\ H_{g,\mu }& (4)& (3,1)& (2,2)& (2,1,1)& (1,1,1,1)& & \\ & & & & & & & \\ g=0& 4& 27& 12& 120& 120& & \\ & & & & & & & \\ g=1& 160& 1215& 480& 5460& 5460& & \\ & & & & & & & \\ g=2& 5824& 45927& 17472& 206640& 206640& & \end{array}$$

Department of Mathematics
UC Berkeley
Berkeley, CA 94720
okounkov@math.berkeley.edu

Department of Mathematics
California Institute of Technology
Pasadena, CA 91125
rahulp@cco.caltech.edu