QMULPH1421
Permutation combinatorics of
worldsheet moduli space
Laurent Freidel, ^{1}^{1}1 David Garner, ^{2}^{2}2 and Sanjaye Ramgoolam ^{3}^{3}3
Perimeter Institute for Theoretical Physics,
31 Caroline Street North, Waterloo, Ontario N2L 2Y5, Canada
Centre for Research in String Theory,
School of Physics and Astronomy,
Queen Mary University of London,
Mile End Road, London E1 4NS, UK
ABSTRACT
Lightcone string diagrams have been used to reproduce the orbifold Euler characteristic of moduli spaces of punctured Riemann surfaces at low genus and with few punctures. Nakamura studied the meromorphic differential introduced by Giddings and Wolpert to characterise lightcone diagrams and introduced a class of graphs related to this differential. These Nakamura graphs were used to parametrise the cells in a lightcone cell decomposition of moduli space. We develop links between Nakamura graphs and realisations of the worldsheet as branched covers. This leads to a development of the combinatorics of Nakamura graphs in terms of permutation tuples. For certain classes of cells, including those of top dimension, there is a simple relation to Belyi maps, which allows us to use results from Hermitian and complex matrix models to give analytic formulae for the counting of cells at arbitrarily high genus. For the most general cells, we develop a new equivalence relation on Hurwitz classes which organises the cells and allows efficient enumeration of Nakamura graphs using the group theory software GAP.
Contents
1 Introduction
The lightcone gauge in string theory involves only physical degrees of freedom and leads to a manifestly unitary matrix, while Lorentz invariance appears nontrivially [1, 2]. The computation of string amplitudes uses lightcone diagrams, parametrised by string length and twist parameters along with interaction times, where the lengths of the strings are proportional to the lightcone momenta. The covariant gauge has manifest Lorentz invariance but unitarity is nontrivial. String amplitudes are calculated by integration over the moduli space of Riemann surfaces , for surfaces of genus and punctures.
In the paper [3], Giddings and Wolpert showed that each closed string lightcone diagram determines a worldsheet equipped with a meromorphic oneform with purely imaginary periods and residues that sum up to zero. The meromorphic oneform (or GiddingsWolpert differential) was constructed by disassembling the lightcone diagram into a number of strips on each of which the meromorphic oneform is trivial, and then making identifications on the boundaries of the strips. It was explained there that lightcone string diagrams lead to a single cover of moduli space, which is important for an equivalence of the lightcone formulation to the covariant formulation.
In the paper [4], Nakamura developed the work of [3] and showed how to compute the orbifold Euler characteristic of using the cell decomposition coming from lightcone diagrams. The key step was the introduction of graphs, embedded on the worldsheet, whose vertices are the zeroes and poles of the GW differential, and whose real trajectories form the edges of the graph. The embedded graph (or ribbon graph) inherits a cyclic order at the vertices  a familiar property which also arises in large expansions of gauge theories. Each such graph  which we call a Nakamura graph  corresponds to a cell in the space of GW differentials on a surface of genus with punctures. These cells are quotiented by the symmetry group of the graph to obtain cells in . The dimension of each cell in this lightcone cell decomposition can easily be read off from the structure of the Nakamura graph. The graphs were counted for low values of and , and the dimensions and symmetries of the graphs were used to calculate the orbifold Euler characteristic of the moduli space . These results agreed with the result for general and computed by Harer and Zagier [5].
There is, as yet, no proof that the lightcone approach reproduces the orbifold Euler characteristic in general. However the evidence that this is true is highly nontrivial: a large number of graphs were counted to verify this in [4]. This is a very important result, since it implies that the Nakamura graphs contain all the information needed to describe precisely how lightcone diagrams can be used to give a single cover of moduli space. This approach implicitly resolves the technical issue [3, 6] of giving a precise specification of the region in the space of lightcone (LC) string parameters which covers every point in precisely once. A naive integration without restrictions would lead to an overcounting problem discussed in [3] and, as anticipated there, its solution should involve systematics similar to those encountered in Feynman graphs. The work of [4] associates a cell of moduli space to each Nakamura graph. The use of graphs in the LC cell decomposition is analogous to the graphs in the KontsevichPenner (KP) cell decomposition of decorated moduli space [7, 8]. Indeed, the KP cell decomposition has been used to compute homology groups and intersection numbers of MumfordMorita classes on moduli space. The LC and KP cell decompositions both involve graphs with cyclic orientation at the vertices (ribbon graphs). However, the Nakamura graphs are much more restricted because of certain causality relations controlling the connectivity of the vertices. As a result the LC cell decomposition requires fewer cells, and so is much more economical [4].
Moreover the GiddingsWolpert differential and the Nakamura decomposition of Riemann surfaces into strips is an essential ingredient of the newly formulated metastring [9]. Since the metastring is chiral, it is necessary for its formulation to provide a parametrisation of the moduli space of Riemann surfaces that includes a notion of worldsheet time while preserving modular invariance. The Nakamura graphs and their implied strip decomposition do exactly this.
A detailed understanding of the topology of is fundamental both to mathematics and string theory. The KP cell decomposition is well studied in mathematics and has also been used recently in describing the link between string theory integrals and Feynman integrals [10]. In another line of development, the systematics of a variety of Feynman graph counting problems of quantum field theory and ribbon graphs of large matrix theories have found a unifying description in terms of permutations in [11, 12], with group theoretic structures such as double cosets playing a central role. The present paper initiates a systematic study of Nakamura’s cell decomposition. We develop a general description of the combinatorics of Nakamura graphs in terms of tuples (finite sequences) of permutations. We present three descriptions of the graphs in terms of permutations in this paper. Two of them involve triples of permutations, and are closely related to the known fact that ribbon graphs can be described in terms of triples [13, 14]. Since a Nakamura graph is not a generic ribbon graph, but rather a ribbon graph subject to nontrivial causality conditions, the associated permutation triples satisfy some nontrivial constraints. The third description of a Nakamura graph involves a tuple of up to permutations, where is the number of interaction vertices in the lightcone diagram. This description requires more permutations in general to describe the graph than in the other two descriptions, but has the advantages that the permutations live in a permutation group of smaller degree, and also that the causality conditions are much simpler. The permutations in this description are elements of , where is the number of faces of a Nakamura graph, or equivalently the number of edges of the graph connecting to poles of the GW differential with positive residues. We call this description the description.
For Nakamura graphs corresponding to the topdimensional cells of moduli space, the description can be simplified further. In this case, has to be even and the tuple has exactly three permutations. The counting of Nakamura graphs for these cells is a counting of permutation triples, where one of the permutations consists of cycles of length . This permutation counting is exactly the one that arises in correlators of the Hermitian matrix model, which have been related to branched covers of the sphere [15, 16, 17]. This allows us to draw upon exact results on generating functions for Matrix model correlators [5] to give analytic expressions for the contribution to the Euler characteristic from the topdimensional cells, for any and . The combinatorics of nonzero codimension cells is more nontrivial. A precise permutation description is nevertheless possible. We expect it to lead to analytic results in the future. For the current paper, we have developed a computer algorithm based on this description, which reproduces all the tables from Nakamura and extends them to higher and .
We now describe the content of the paper in more detail. In Section 2, we start by recalling the properties of the GiddingsWolpert differential [3] and explaining how Nakamura associated a graph to each differential [4]. The parameters describing the cells in lightcone cell decompositions are introduced. For fixed and , the integer gives the total number of edges incident on the poles of the GW differential with positive residue (which we call incoming poles). It is also the number of strips which can be glued together to produce the worldsheet; each strip is incident on one incoming pole and one outgoing pole. The branching constant is an integer describing the combined orders of all the zeroes and their departure from simplicity; when all the zeroes are simple, then . The number of internal edges is denoted by ; these are the edges of the Nakamura graph which connect zeroes of the GW differential directly to zeroes. The top dimensional cells of the LC cell decomposition only involve simple zeroes of the GW differential and their associated Nakamura graphs have no internal lines, so for cells at top dimension. Lower dimensional cells can involve higher order zeroes as well as real trajectories connecting the zeroes.
In Section 3 we relate Nakamura graphs to dessins d’enfants and Belyi maps. A dessin d’enfant is a bipartite graph embedded on a surface with a cyclic ordering of the edges at each vertex. Bipartite graphs have two types of vertices, which can be coloured in black or white, in which each edge connects to two vertices of different colours. We can convert a Nakamura graph to a dessin by introducing auxiliary vertices along the edges of the graph in such a way that the graph becomes bipartite. The structure of these graphs can then be described by a triple of permutations, which also allow the graphs to be related to branched covers of the Riemann sphere known as Belyi maps [18, 13, 14]. The simplest way to convert a Nakamura graph to a bipartite graph is to subdivide every edge; this graph has edges, so can be described by a triple of permutations in the symmetric group . There is also another general way to convert a Nakamura graph into a bipartite graph which requires fewer subdivisions of edges, which allows a description in terms of a triple of permutations. While every Nakamura graph has a description in terms of these triples of permutations, not all permutation triples give Nakamura graphs; in Section 3.4, we state the required properties that a permutation triple must satisfy to give a Nakamura graph.
In Section 4, we develop a new permutation description of Nakamura graphs by considering branched covering maps from the worldsheet onto the infinite cylinder  equivalently, by composing with a conformal map, branched covering maps to the Riemann sphere. The section starts with a review of branched covers, and their description in terms of equivalence classes of tuples of permutations which we call Hurwitz classes. The branched covers can be constructed by a gluing construction on the faces (strips) of the Nakamura graph. The degree of the branched cover of the sphere associated to a graph is . The branch points of the cover are related to the vertices of the Nakamura graph. Each Hurwitz class determines a unique Nakamura graph, but there can be multiple Hurwitz classes corresponding to a given Nakamura graph. To solve this redundancy, we introduce an equivalence relation on the space of Hurwitz classes which we call slideequivalence. This equivalence relation is related to the fact that the connectivity of a Nakamura graph does not determine the relative timeordering of the zeroes (interaction vertices) of the GW differential. There is a onetoone correspondence between slideequivalence classes and Nakamura graphs.
In Section 5 we explore some links between the counting of cells in the moduli space and the correlators of matrix models. Cells of top dimension in the LC decomposition are specified by Nakamura graphs with simple zeroes and no internal edges. Within the slideequivalence class of a topdimensional graph, there is a unique Hurwitz class consisting of a tuple of three permutations. This permutation triple naturally corresponds to a Belyi map (a covering of the sphere branched at three points), without the need to introduce new vertices or subdivide edges of the Nakamura graph. The counting of Belyi maps is known to be related to correlators of the Hermitian matrix model [15, 16, 17]. This allows us to use known exact results from Hermitian matrix models [5] to obtain all orders analytic formulae for the contribution to the Euler characteristic from the topdimensional cells of the LC cell decomposition. These results agree with the tables given by Nakamura for small and . We can also consider cells with lower dimension with branching constant and no internal edges (). In this case, we can use complex matrix models to derive analytic formulae for the contributions to the Euler characteristic from lowerdimension cells. (At the present stage, we have no map to matrix models for the counting of the most general cells involving .)
Finally, in Section 6, we test computationally the validity of the LC cell decomposition and its description in terms of slideequivalences of Hurwitz classes. Using the group theory software GAP [19], we use the description to enumerate the cells and their dimensions in terms of Nakamura graphs, reproducing and extending the tables found in [4]. The computation is significantly facilitated by the introduction of the concept of an structure, which contains some coarse information about the internal edges of a Nakamura graph. It is an invariant of the slideequivalence classes of Hurwitzclasses. Double cosets of also play a role in the computation. We conclude with some discussion of our results and possible future directions.
2 Review: Giddings, Wolpert and Nakamura
2.1 The GiddingsWolpert differential
Let be a Riemann surface with marked points and genus , where . Associate a set of real numbers respectively to the marked points, which satisfy . Giddings and Wolpert proved in [3] that there exists a unique abelian differential on the Riemann surface such that has simple poles at the points with respective residues , and pure imaginary periods on any closed integral on the surface.
The GiddingsWolpert differential yields a global time coordinate on the surface, up to an overall constant representing the time translation symmetry. If we fix a point on the surface which is not a pole of , then we can define the global time coordinate of a generic point on the surface to be . This expression does not depend on the choice of integration contour from to , since any two paths from to differ only by a closed contour, and the integral of the differential along any closed contour is imaginary. The global time coordinate tends to positive infinity as we approach the poles with negative residues, and to negative infinity as we approach the poles with positive residue. We call the poles with positive residue the incoming poles, and the poles with negative residue the outgoing poles.
For the cases of the sphere and the torus, it is straightforward to construct the GW differential of a given marked surface and its time coordinate explicitly. Take a sphere with marked points and associated reals , where . We can choose coordinates on the sphere such that the marked points are located at for some . In this chart, the GW differential can be explicitly written as
(1) 
It is clear that this differential has residues at the points , and that the integral of the differential along any closed contour is , which is purely imaginary. The global time coordinate is
(2) 
where is an arbitrary constant.
Now consider a torus with marked points , associated real values with , and modular parameter with . This torus can be realised as the quotient of the complex plane by the equivalence relation , where and are integers. In these coordinates, the marked points are located respectively at for some , where . To define the GW differential on this surface, we introduce the Jacobi theta function , which is a holomorphic quasiperiodic function on the complex plane satisfying
(3)  
(4) 
and behaves like for small values of . The GW differential on this surface is
(5) 
and the associated global time coordinate on the surface is
(6) 
where is an arbitrary constant. It can be shown from the above properties and relations of the Jacobi theta function that and are welldefined on the torus, i.e. these definitions are invariant under the coordinate shifts and under the modular transformations , . It can also be seen that the integrals of the differential along the cycles and are imaginary, and that each pole has residue , so that all the periods are pure imaginary. Formulae for GiddingsWolpert differentials in terms of theta functions at genus one and higher can be found in recent work [20].
2.2 Nakamura graphs
The GiddingsWolpert differential associated to a marked Riemann surface naturally gives rise to an embedded ribbon graph on the surface. This construction was developed by Nakamura in [4], and leads to a cell decomposition of the moduli space of Riemann surfaces in which each cell is specified by a graph. In this section we review the basic properties of these graphs, which we call Nakamura graphs.
Consider a marked Riemann surface with GW differential . The GW differential has poles at the marked points with residues . For any unmarked point on , we can choose local complex coordinates around that point such that for some . A zero of order of the GW differential is a point at which . For each point on the surface, there exists a set of directions in which is real  these are the real trajectories that extend out from the point. A zero of order has real trajectories extending out from the zero. If , the zero is called simple. Real trajectories extending out from the zeroes of the GW differential will only meet at poles and zeroes of the differential.
The set of real trajectories that extend out from all the zeroes of the GW differential define a ribbon graph embedded onto the surface, with the vertices of the graph corresponding to the poles and zeroes of , and the edges of the graph corresponding to the real trajectories. The edges also inherit an orientation from the GW differential: they are oriented in the direction along which the global time coordinate increases. Some examples of Nakamura graphs are shown in Figure 1.
The Nakamura graph associated to a marked Riemann surface is uniquely determined by its GiddingsWolpert differential. It was shown by Nakamura in [4] that such a graph always has the following properties:

The graph is connected, oriented, and cyclically ordered at the vertices.

The edges connecting to a pole are either all oriented towards the pole or all oriented away from the pole.

A zero connects to cyclically alternating incoming and outgoing edges, and has a valency of at least four.

No edge connects to the same end point twice, and no edge has only poles as its end points.

Every face of the ribbon graph contains on its boundary exactly two poles, one incoming and one outgoing.
Each face of the graph is bounded by two extended real trajectories of the GW differential. It is possible to choose local coordinates on each face such that within the face, and where lies in the range for some . This means that each face of the graph is holomorphic to a strip in the complex plane, and each strip has a width which is determined by the GW differential. The combination of the Nakamura graph, the widths of the strips, the time coordinates of the zeroes, and the residues around the poles, is enough to reconstruct the GiddingsWolpert differential on a surface, and hence to specify its complex structure.
An example of the gluing of strips to give a surface with an embedded Nakamura graph is shown in Figure 2. A Riemann sphere with three punctures is conformally equivalent to a ‘pants’ diagram, with the boundaries extended out to infinity. The GW differential on this surface traces out a Nakamura graph, given on the right of the figure, which partitions the pants diagram into two infinite strips. The poles of the GW differential are represented by black vertices of the Nakamura graph, and correspond to the boundaries of the strips located at positive and negative infinity. In this case, the widths of the strips are determined by the residues of the marked points.
If we take some Nakamura graph arising from a GiddingsWolpert differential and consider all possible strip widths that are consistent with the specified residues at the poles, and all possible time coordinates of the zeroes that are consistent with the causal ordering of the zeroes, then we will in general find a family of inequivalent GW differentials that can arise from a single Nakamura graph. As each GW differential corresponds to a unique Riemann surface, this means that each Nakamura graph specifies a cell in , the moduli space of inequivalent Riemann surfaces of genus with marked points.It was shown in [4] that counting all such possible graphs can give information about the moduli space of Riemann surfaces. Nakamura successfully found all the graphs corresponding to surfaces with Euler characteristic , and used this to calculate the orbifold Euler characteristic of moduli space in many different cases.
2.3 Parameters of Nakamura graphs and moduli space
We conclude this section by presenting some relevant relations between the parameters of Nakamura graphs and their associated cells in moduli space.
A Nakamura graph consists of vertices, edges, and faces. The vertices are separated into zeroes and poles. All edges connect to zeroes, and no edge connects two poles together. There are exactly two poles on the boundary of each of the faces of the graph, one incoming and one outgoing. Hence, there are external edges of the graph connecting incoming poles to zeroes, external edges connecting outgoing poles to zeroes, and internal edges that connect only to zeroes. Summarising, we have
The Euler characteristic of a surface with an embedded graph is , which gives the relation
(7) 
Next, we consider the valencies of the vertices. As all faces have on their boundary exactly one incoming pole, the valencies of the incoming poles sum up to , and similarly for the outgoing poles. As the zeroes always border an equal number of incoming and outgoing edges, the valencies of the zeroes are always even. The zeroes correspond to the points where at least two real trajectories meet, and so the valency of a zero is always greater than four. We define the branching number to be
(8) 
where the are the valencies of each of the zeroes. The branching number is a nonnegative integer for every Nakamura graph. This sum rearranges to
(9) 
Now, adding the sum of the valencies of the poles to this equation give us the sum over the valencies of all vertices, which must equal twice the number of edges. We thus have
(10) 
and hence we have the relation
(11) 
We can use (7) and (11) to find a bound on the number of faces for Nakamura graphs of any genus and number of poles . Using the equations to eliminate , we write
(12) 
The constants and are always nonnegative integers, so is bounded from above by , where
(13) 
This is the maximum number of faces of a Nakamura graph of genus with fixed points. To find Nakamura graphs computationally, it is helpful to first fix and then to find all the graphs of genus such that .
We can eliminate the number of internal edges from (7) and (11) to find a relation between the branching number , the number of zeros , and the Euler characteristic :
(14) 
As , this equation gives us a bound on the number of zeroes of a Nakamura graph. Since a Nakamura graph always has at least one zero, we have the bounds on the number of zeros of a Nakamura graph,
(15) 
The dimension of a cell associated to a Nakamura graph was derived in [4]. For a given graph with zeroes, faces and poles, we have width parameters. The widths of the faces bordering a given pole satisfy a relation . These residue relations specify independent constraints on the strip widths (since we have the total conservation equation ). There are real parameters corresponding to the independent time coordinates labelling the positions of the zeroes, modulo the overall time translation symmetry. So we can see that the dimension of the cell in moduli space corresponding to a Nakamura graph is . The above equations can be rearranged to show that the real dimension of a cell is
(16) 
This means that for a given genus and number of points , the top dimension of the moduli space of graphs is , and the codimension of a given cell is
(17) 
3 Nakamura graphs as dessins d’enfants
In Section 2, it was discussed that for a given , , and set of real numbers that sum to zero, there is a cell decomposition of , the moduli space of inequivalent Riemann surfaces, in which each cell is specified by a Nakamura graph . Different points in the same cell in moduli space correspond to inequivalent Riemann surfaces with the same Nakamura graph but different GiddingsWolpert differentials.
In this section we introduce a method to categorise the cells in moduli space by classifying the possible Nakamura graphs using permutation groups and dessins d’enfants. We first review the notion of a dessin and discuss two distinct prescriptions for converting graphs into dessins. In each prescription, we show that there is a unique equivalence class of permutation triples corresponding to each Nakamura graph. We show that the necessary defining properties of Nakamura graphs can be encapsulated in the language of permutation groups, and hence equivalence classes of permutation triples can be used to catalogue the cells in moduli space.
3.1 Review: dessins d’enfants
A dessin d’enfant is a cyclicallyordered graph (a ribbon graph) that is also bipartite: each graph vertex is coloured in black or white in such a way that black vertices only connect directly to white vertices, and white vertices only connect to black vertices. Given a bipartite graph with edges, we can assign an arbitrary labelling of objects to each edge, such as the integers . Each vertex can be associated to a permutation cycle in , representing the cyclic ordering of the edges connecting to the vertex. As each edge connects to exactly one black and one white vertex, each integer in appears in exactly one cycle corresponding to a black vertex and in exactly one cycle corresponding to a white vertex. We can collate all the cycles corresponding to the black vertices to a single permutation , and likewise collate all the cycles corresponding to the white vertices to a permutation . The pair of permutations is enough to completely reconstruct the original dessin. In addition, we can introduce a third permutation , defined by the relation
(18) 
This third permutation describes the structure of the faces of the dessin.
A triple of permutations determines a unique dessin, but there will be other triples in that specify the same graph, due to the arbitrariness of our original choice of labelling of the edges. This relabelling symmetry is described by an equivalence relation of conjugation on the permutation triples: two triples and are equivalent if there exists some permutation acting on the edge labels of the graph such that
(19) 
This means that each dessin d’enfant with edges corresponds to an equivalence class of permutations under conjugation by .
An automorphism of a dessin d’enfant is a mapping of the edges and vertices of the graph into itself such that the connections of the edges to the vertices, the colours of the vertices, and the cyclic ordering of the edges at the vertices are all preserved. For a dessin described by a triple, these mappings are precisely the subgroup of consisting of elements that satisfy
(20) 
A dessin d’enfant is said to be clean if each white vertex is bivalent (has valency two). Any ribbon graph can be converted into a clean bipartite graph by colouring all the vertices in black and introducing a new white vertex on each edge. The new graph has twice as many edges as the original graph. This means that it is always possible to associate a dessin, and hence an equivalence class of permutation triples, to a ribbon graph. An example of a clean dessin d’enfant is included below on the right of Figure 3.
3.2 Nakamura graphs as triples
Nakamura graphs are oriented ribbon graphs satisfying a list of properties given in Section 2.2. Every graph has edges connecting to positive poles, edges connecting to negative poles, and edges connecting only to zeroes, and so each graph has edges in general. As Nakamura graphs are not bipartite in general, they can only be described by permutation triples after cleaning (introducing new vertices). Cleaning a graph doubles the number of edges of a graph, so a Nakamura graph dessin has edges in general. This means that every Nakamura graph can be described as a triple of permutations with overall conjugation equivalence by . The poles and zeroes of the Nakamura graph all correspond to the black vertices.
We can fix some of the conjugation symmetry of Nakamura graphs by taking a canonical choice of the labelling of the edges. The number of edges of a dessin originating from cleaning a Nakamura graph is always even, so we can choose to label the edges by . Each edge of a Nakamura graph has an orientation, and so each edge of the cleaned Nakamura graph has an orientation. There are edges connected to the incoming poles, and edges connected to outgoing poles, so we can label the edges connecting to incoming poles with the integers , and the edges going into the outgoing poles by . These edges connect to bivalent white vertices: we can label the other connecting edges with the labels and such that each white vertex connects to edges labelled with the same integer but with different superscripts. We label the edges connecting between the zeroes by integers from to , assigning integers with a superscript to the edges oriented from a black vertex to a white vertex, and a superscript to the edges oriented from white to black, such that each white vertex connects to edges labelled with the same integer but with different superscripts.
Each of the zeroes of a Nakamura graph connects to edges with cyclically alternating orientation. This is reflected in the structure of their corresponding cycles; each cycle associated to a zero consists of a string of alternating and superscripted labels. These cycles appear in the permutation . Also, all cycles in the permutation are 2cycles of the form for some . The permutation consists of cycles, corresponding to the faces of the ribbon graph. Each cycle in consists of a string of consecutive superscripted integers, followed by a string of superscripted integers, which reflects the fact that each face is holomorphic to a strip. An example of a dessin with this kind of labelling arising from a Nakamura graph is given above in Figure 3.
With this choice of labelling, we can always uniquely decompose the permutation into
(21) 
where describes the incoming poles and acts on the set , describes the outgoing poles and acts on the set , and describes the zeroes of the graph and acts on the remaining edges. The permutation can be written
(22) 
and, schematically, is of the form
(23) 
Our choice of labelling ‘breaks’ the conjugation symmetry down to a smaller subgroup. Two permutation descriptions of a graph and with the above conventions for labellings are equivalent if there is some satisfying
(24) 
If we wish to find which conventionallylabelled permutation triples are equivalent, we need only consider equivalence of the triples under those permutations in an subgroup that preserve the required forms of , , , and separately. We can thus just consider conjugation of conventionallylabelled permutation tuples under
(25) 
where is the wreath product.
The automorphisms of a Nakamura graph are the ribbon graph automorphisms which also preserve the orientation of the edges. In particular, this means that Nakamura graph automorphisms map positive poles to positive poles, negative poles to negative poles, and zeroes to zeroes. Automorphisms are allowed to permute poles of the same sign. In the picture, we can decompose the permutation . For the orientations of the graph to be preserved, the automorphisms must preserve these three constituent permutations separately. Hence the automorphism group of a Nakamura graph in the picture is a subgroup Aut such that if
(26) 
(The condition is automatically satisfied by the fact that .)
An example of a conventionallylabelled dessin d’enfant in the description is given in Figure 4. This graph is described by a triple of permutations acting on the set of 16 elements :
(27) 
The black vertices correspond to , the white vertices correspond to , and the faces of the graph correspond to . The automorphism group of this graph is isomorphic to , and is generated by
(28) 
3.3 Nakamura graphs as triples
The description of a general Nakamura graph in terms of a triple of permutations is possible because the graph can be made into a clean bipartite graph by adding extra vertices. Without the addition of extra vertices, Nakamura graphs are not bipartite in general. However, the property that no pole connects to another pole allows us to find a permutation tuple description requiring fewer labelled edges, and hence requiring permutation groups of smaller degree.
Starting from a Nakamura graph, colour the poles in black and the zeroes in white. Subdivide only the internal edges connecting zeroes to zeros by adding in extra vertices. As there are no edges connecting poles to poles, this graph must be bipartite. Label the edges going out of the incoming poles by , and the edges going into the outgoing poles by . Label the edges bordering each zero with integers from to , such that the edges oriented towards a zero are assigned a superscripted integer, and the edges oriented away from a zero are assigned the corresponding superscripted integer.
As in the description, this bipartite graph can be described by a triple of permutations , , and satisfying . The permutation describes the structure of the graph at the poles and at the new vertices added in the internal edges, describes the graph at the zeroes, and describes the faces of the graph. We can decompose into three permutations with , where acts on and describes the incoming poles, acts on and describes the outgoing poles, and describes the internal edges. The permutation now describes the zeroes, and so each of the cycles consists of a string of alternating , superscripted labels. As in the description, is of the form
(29) 
This new descriptions requires only labelled edges for each graph. The choice of labelling of the edges allows us to state that two tuples of permutations and are equivalent if they are conjugate by a permutation , where
(30) 
An example of a dessin described by an triple is given in Figure 5.
The automorphisms of a Nakamura graph in the picture are the automorphisms of the dessin that preserve the orientation of the edges in the dessin. The permutation decomposes as , and so the automorphisms of the graph in this picture are the subgroup such that if
(31) 
The example of a Nakamura graph with automorphism group of order four given in the previous section can be described in the picture. The graph drawn in Figure 6 is described by a triple of permutations acting on the set of 8 elements :
(32) 
The automorphism group of the dessin is necessarily isomorphic to the automorphism group of the dessin, as they are both descriptions of the same Nakamura graph. In this case, the automorphism group is generated by
(33) 
3.4 From permutation triples to cells in moduli space
Given a Nakamura graph with faces and internal edges, it is always possible to construct a triple of permutations from the group or that describes the graph. Not every triple of permutations in these groups corresponds to a Nakamura graph, though. For a given triple of permutations to describe a Nakamura graph, it must satisfy a particular set of conditions.
A triple of permutations specifies a conventionallylabelled Nakamura graph if it satisfies the following properties:

The subgroup generated from and acts transitively on , where
(34) (35) (This is the condition that a Nakamura graph is connected.)

The permutation can be written as
(36) where , and are disjoint, and:

acts on and fixes all other elements,

acts on and fixes all other elements,

has no cycle of length less than 4, , and .
(This is the condition that a Nakamura graph decomposes into positive poles, negative poles, and zeroes, and that the orientations of the connecting edges are outgoing, incoming and alternating respectively.)


(This is the condition that the dessin is clean.)

The permutation decomposes into disjoint cycles as , where for each
(37) (This is the condition that each disjoint cycle in corresponding to a face of the graph is of the form , and so corresponds to a strip.)

For any sequence of nonnegative integers and some , if all the elements of the sequence
(38) are contained in , then this sequence has no repeated element. (This condition forbids closed oriented loops on the graph, and permits time orderings to be assigned to the zeroes of the graph.)
Similarly, a triple of permutations specifies a conventionallylabelled Nakamura graph if it satisfies the following properties:

The edges can be assigned labels from the set , where
(39) (40) 
The subgroup generated from and acts transitively on .

The permutation can be written as
(41) where , and are disjoint, and:

acts on and fixes all other elements,

acts on and fixes all other elements,

.


The permutation has no cycle of length less than 4, , and .

The permutation decomposes into disjoint cycles as , where for each
(42) 
For any sequence of nonnegative integers and some , where , if all the elements of the sequence
(43) are contained in , then this sequence must not have a repeated element.
4 Nakamura graphs as Hurwitz classes
In the previous section we introduced two methods of describing Nakamura graphs with triples of permutations which multiply to the identity by converting the Nakamura graphs to bipartite graphs with extra vertices. These triples of permutations are elements of either or , where is the number of strips (faces) of a graph and is the number of internal edges in the graph connecting zeroes to zeroes. However, in this description, the conditions that a general permutation triple must satisfy to be a Nakamura graph are rather cumbersome, and can be tricky to check computationally.
In this section we present a new description of a Nakamura graph in terms of a tuple of permutations in which multiply to the identity, where , and is the number of zeroes of the graph. This approach has two main advantages over the triples description: the necessary permutation group is smaller than or , and the set of conditions that a generic tuple must satisfy to give a Nakamura graph is much simpler. Both conditions mean that it is easier to implement Nakamura graphs computationally with the group than with the groups or .
We begin this section with a review of Hurwitz theory, which describes how equivalence classes of branched covers of Riemann surfaces correspond to equivalence classes of permutation tuples multiplying to the identity. We will call such an equivalence class of permutations a Hurwitz class. More on this standard subject of algebraic topology can be found, for example, in [21, 22, 23] or in a physics context in [24, 25]. The equivalence classes of permutations triples discussed in Section 3 are examples of Hurwitz classes. We then discuss how to construct branched covers from a Riemann surface with a GiddingsWolpert differential to an infinite cylinder, with the ramification points of the surface being exactly the poles and zeroes of the GW differential. The Hurwitz class corresponding to this cover is an equivalence class of a tuple of permutations in , and contains enough information to reconstruct the Nakamura graph associated to the domain Riemann surface.
Each Hurwitz class corresponds to a single Nakamura graph, but a Nakamura graph may correspond to many distinct Hurwitz classes. This makes it difficult to find the automorphism group of a Nakamura graph from a generic Hurwitz class associated to the graph. To solve this issue, we introduce a new equivalence relation on the set of Hurwitz classes  which we call slideequivalence  such that the equivalence classes of this relation are in onetoone correspondence with the Nakamura graphs. Within the slideequivalence class of any Nakamura graph, there is a unique canonical choice of a Hurwitz class  whose elements we call reduced tuples  that yields in a simple way the automorphism group of the associated graph. This description gives a computationally powerful method of finding the Nakamura graphs and their automorphism groups.
4.1 Review: Branched covers, Hurwitz classes, and Belyi maps
A continuous surjective map is a branched cover of the Riemann sphere if every point on has some open neighbourhood such that is a collection of disjoint open sets, and on each set is topologically equivalent to the complex map for some positive integer . For most points on the sphere, there are preimages on the surface , where is the degree of the map. There is a finite set of points on the target space which each have fewer than preimages. These are the branch points of the map . Consider a point on the surface . If is not a branch point, then for each of its preimages on , there exist complex coordinate patches about and about such that maps . However, if is a branch point, then for at least one of its preimages there exist coordinate patches about and about where maps for . Such a point is called a ramification point of the map . For a given branch point , each preimage of the branch point has an associated unique positive integer such that maps about that point. The tuple of integers is the ramification profile of the branch point .
The neighbourhoods of ramification points can be described in terms of a gluing construction. Take a disc around a branch point with coordinates , and cut the disc along the real interval . The preimages of the cut disc on the surface are identical copies of the cut disc. The cuts along the intervals can be identified to recover the neighbourhoods on around the ramification points. If we choose a labelling of the cut discs with the integers , then the gluing of the cut discs corresponds to a mapping from the set to itself: the lower edge of the cut on disc is glued to the upper edge of the cut on disc . This gluing is shown on the left of Figure 7. Each cut disc is biholomorphic to a ‘wedge’ of a disc subtending an angle for some , as can be seen on the right of Figure 7.
There is another way of arriving at the permutation description of branch points by considering the preimages of loops on the target space . Choose a marked unbranched point on the sphere, and label its preimages with integers from to . For each of the branch points on the sphere, draw a directed closed path starting and ending on the marked point, which can be contracted to a neighbourhood of the branch point without passing through a branch point. The preimages of each of the directed loops on the sphere are directed closed paths on the Riemann surface which connect the distinct labelled preimages of the marked point. Each branch point gives a bijective mapping from the set to itself which we obtain by following the paths of the preimages of the loops. We associate a permutation , to each branch point of the map . On the sphere, the path constructed by following all loops around is contractible. Hence, the permutations multiply together to give the identity,
(44) 
The permutation tuple describes the branching profile of a branched cover from a Riemann surface on to the sphere . This is demonstrated in Figure 8.
There is an arbitrariness in the way we label the preimages of the marked point from to : any relabelling of these points yields the same branching profile. Hence, we consider two permutation tuples to be equivalent if there is a permutation which conjugates one sequence to the other. That is, the tuples and are equivalent if
(45) 
We call an equivalence class of tuples under conjugation a Hurwitz class.
There is also a notion of equivalence of branched coverings in terms of bijective maps. Two branched covers of the sphere and are equivalent if there exists some homeomorphism such that . In other words, and are equivalent if the following diagram commutes:
(46)  
(47)  
(48) 
This definition of equivalence coincides with the conjugation equivalence: two branched covers of a Riemann surface are equivalent if they have the same Hurwitz class.
The genus of the covering surface can be expressed, according to the RiemannHurwitz relation, in terms of the branching numbers of the branch points as
(49) 
Dessins d’enfants can be realised as branched coverings of the sphere. If we take a branched cover of the sphere with branch points located at , and consider the real interval on the target sphere, then the preimage of this interval on the Riemann surface is an embedded ribbon graph. Colouring the preimages of the point on the sphere in black and the preimages of in white, it can be seen that the embedded ribbon is bipartite and is therefore a dessin. An example of a branched covering of the sphere generating a dessin d’enfant is shown in Figure 9. If we choose a labelling of the preimages of the real interval, then we can find a Hurwitz class associated to the branched covering. This Hurwitz class coincides exactly with the defining equivalence class of a dessin d’enfant. A branched covering of the sphere with three branch points is called a Belyi map, and we call a representative element of its associated Hurwitz class a Belyi triple. The Nakamura graph descriptions from Section 3 are examples of Belyi triples which correspond to Belyi maps of degree or .
4.2 Nakamura graphs and branched coverings
Consider a Riemann surface with a GiddingsWolpert differential and embedded Nakamura graph. The Nakamura graph partitions the surface into faces, each of which is holomorphic to an infinite complex strip, such as in Figure 2. The zeroes of the differential lie on the boundaries of the strips, and the poles are located at the negative and positive infinities of the strips. The surface can be reconstructed from the strips by a gluing of the edges determined by the Nakamura graph.
First, let us consider a Riemann surface with a GW differential in which the strips are of equal width . The strips can then be viewed as copies of a single template strip of width . There is a trivial map from each of the worldsheet strips on to the target strip, in which all the preimages of a point on the target strip have the same time coordinate. On identifying the upper and lower edges of the target space strip, the map extends to a branched covering from the surface onto the cylinder. All the real trajectories of the Nakamura graph are mapped on to a single infinite line on the cylinder, and all the zeroes are mapped on to this line. The positive (incoming) poles of the graph are mapped on to negative infinity, and the negative (outgoing) poles of the graph are mapped on to positive infinity. The map has branch points, where is the number of distinct time coordinates of the zeroes. If the time coordinates of all the zeroes are distinct, then .
An infinite cylinder of circumference can be mapped bijectively to the Riemann sphere with the exponential map . This means that the composition of the cylinder covering and the exponential map is a holomorphic branched covering of the Riemann sphere with branch points. The positive poles of the Nakamura graph map on to 0, the negative poles of the graph map on to , and the remaining zeroes map on to branch points along the real axis on the sphere. The GiddingsWolpert differential on the worldsheet is .
Now consider a more general GW differential where the strips are no longer of equal width. We can construct a bijective mapping from each strip onto a single template strip of width in such a way that the preimages of a point on the template strip have the same time coordinate. However, this mapping will not be holomorphic in general. Applying the exponential map to this template strip, we have a map from a general Riemann surface onto the sphere. The GW differential cannot be written in the form in this more general case, but the map is still a branched cover of the sphere, with ramification points at the poles and zeros of the differential.
This branched cover of the sphere has an associated permutation tuple describing the branching. We mark an unbranched point on the sphere and label the preimages of this point with the integers from to . The preimage of a small loop starting and ending on this marked point that encloses a branch point on the Riemann sphere is a collection of closed paths connecting the labelled preimages of the unbranched point. Each branch point determines a permutation , and so the branched covering determines a tuple consisting of permutations
(50) 
that describes the gluing of the different strips. Here, the permutation describes the branching about 0, describes the branching around , and describes the branching around the th branch point on the real line. As this is a branched covering of the sphere, this set of permutations multiplies to one,
(51) 
There is also an overall conjugacy equivalence of the tuple due to the arbitrary choice of labelling of the inverse images of the marked point,
(52) 
where . This construction is shown in Figure 10, where the marked point is chosen to lie on the real axis of the Riemann sphere, and the preimages of this point lie on the boundaries of the strips. For the case , the RiemannHurwitz relation (49) can be written as
(53) 
This also follows from the previous discussion of Nakamura graph parameters in Section 2.3, in particular by eliminating from equations (7) and (11).
The boundaries of the strips are the real trajectories of the GW differential, which form the Nakamura graph of the surface. We can choose to label the real trajectories bounding the upper edge of each strip with the same integer that was assigned to the marked point lying on the upper edge of this strip. This gives us a labelling of the Nakamura graph associated to the surface, in which all the edges corresponding to the upper boundary of the same strip have the same label. We call this labelling of a Nakamura graph the description, or the Hurwitz class description, as the Nakamura graph associated to this surface can be reconstructed from the Hurwitz class of the branched covering and vice versa.
The labelling of the edges glued to the lower boundary of a strip are determined by the Hurwitz tuple. On a strip in which the upper boundary is labelled by some integer , the edge preceding the preimage of the first branch point is labelled by , where . The edge proceeding the next branch point is labelled , where