Printer Friendly

A generalization of the quadrangulation relation to constellations and hypermaps.

1 Introduction

Maps are combinatorial structures describing an embedding of a graph in a surface. They can be encoded as factorizations of identity in the symmetric group. Enormous efforts have been devoted to the enumeration of these combinatorial objects and their variants, see e.g. [LZ04] and references therein. In [JV99], the following strikingly simple enumerative relation was established:

[E.sup.(g).sub.n,D] = [g.summation over (i=0)][4.sup.g-i] [B.sup.(g- i,2i).sub.n,D] = [4.sup.g][B.sup.(g,0).sub.n,D] + [4.sup.g-1][B.sup.(g-1,2).sub.n,D] + ...

Here, for D [subset or equal to] [N.sup.+], we define [B.sup.(g,k).sub.n,D] as the number of rooted bipartite maps with every face degree of the form 2d and d [member of] D, whose vertices are colored black and white, of genus g with n edges such that k black vertices are marked. The number [E.sup.(g).sub.n,D] is the counterpart for rooted (non necessarily bipartite) maps with the same restriction on face degrees, without the marking part. In the planar case, we have [E.sup.(0).sub.n,D] = [B.sup.(0,0).sub.n,D], meaning that every planar map of all faces with even degree is always bipartite. This is not true for higher genera. Consider a rectangular grid of size m x n on a torus. It is a map of all faces with even degree, but it is bipartite if and only if m, n are both even, which is not always true.

The special case on D = {2} had been proved in [JV90a], and the maps in concern are quadrangulations, which gives this special case the name quadrangulation relation. It had been then extended to D = {p} in [JV90b]. Despite its nice form, the combinatorial meaning of the quadrangulation relation remains unclear, though some effort is done in [JV99] to explore properties of the possible hinted bijection.

In enumeration of maps, there is a recurrent phenomenon: results on bipartite maps can often be generalized to constellations (see e.g. [BMS00, BDFG04, PS02]). In the same spirit, we will generalize the quadrangulation relation to m-constellations and m-hypermaps. As an example, our result in the case m = 3 gives rise to the following relation (c.f. Corollary 4.3):

[H.sup.(g).sub.n,3,D] = [g.summation over (i=0)][3.sup.2g-2i] [2i.summation over (l=0)] [[2.sup.l+1] - [(- 1).sup.l+1]/3] [C.sup.(g-i,l,2i-l).sub.n,3,D].

Here, [C.sup.(g,a,b).sub.n,3,D] is the number of rooted 3-constellations with n hyperedges, and hyperface degree restricted by the set D, with a vertices of color 1 and b vertices of color 2 marked. The number [H.sup.(g).sub.n,3,D] is the counterpart for rooted 3-hypermaps without markings. See Section 2.1 for the definitions of these notions. This simple relation suggests a more general bijection for constellations and hypermaps than the one implied by the quadrangulation relation. Finally, we recover a relation between the asymptotic behavior of m-constellations and m-hypermaps in [Cha09], which can be seen as an asymptotic version of our relation.

Given a partition [mu] [??] n, we note m[mu] the partition obtained by multiplying every part in [mu] by m. In [JV90a], the quadrangulation relation was obtained using a factorization of irreducible characters of the symmetric group on partitions of the form [[(mk).sup.n]] using a notion called m-balanced partition. A generalization to partitions of the form 2[lambda] is stated in [JV99]. In this paper, we will present a generalization of this character factorization to partitions of the form m[lambda] (Theorem 3.1). This result can be derived from two different perspectives, algebraic or combinatorial. We then give our generalization of the quadrangulation relation in Corollaries 4.2, 4.3 and 4.4 using our generalized character factorization.

2 Preliminaries

2.1 Constellations and hypermaps

A map M is an embedding of a connected graph G, with possibly multi-edges or loops, into a closed, connected and orientable surface S such that all faces, i.e. components of S\M, are topological disks. Maps are defined up to orientation-preserving homeomorphisms. We define the genus g of a map to be that of the surface it is embedded into. We thus have the Euler relation [absolute value of V] - [absolute value of E] + [absolute value of F] = 2 - 2g.

We now define two special kinds of maps following [LZ04, Cha09]. An m-hypermap is a map with two types of faces, hyperedges with degree m and hyperfaces with degree divisible by m, such that every edge is located between a hyperedge and a hyperface. Each edge then is naturally oriented with the hyperedge on its right. Conventionally hyperedges are colored black and hyperfaces white. An m-constellation is an m-hypermap with additional condition that all vertices are colored with an integer between 1 and m in a fashion that every hyperedge has its vertices colored by 1,2, ..., m in clockwise order. A map with faces of even degree can be considered as a 2-hypermap by replacing every edge with a 2-hyperedge, and a bipartite map can be considered as a 2-constellation in the same way. A rooted m-hypermap is an m-hypermap with a distinguished edge. Rooted m-constellations are similarly defined, with the convention that the starting vertex of the root in natural orientation has color 1. We consider only rooted m-hypermaps and rooted m-constellations hereinafter.

Figure 1 provides an example of planar 3-hypermap. It can also be considered as a planar 3-constellation. More generally, every planar m-hypermap can have its vertices colored to meet the additional condition to be an m-constellation, that is to say, every planar m-hypermaps can be considered as an m-constellation. However, this is not necessarily true for higher genera, in which m-hypermaps do not necessarily have a coloring that conforms with the additional condition to be an m-constellations.

We use x to denote a sequence of variables [x.sub.1], ..., [x.sub.m], and [[x.sub.i] [left arrow] f(i)] to denote the substitution of [x.bar] by [x.sub.i] = f(i). We define H(x, y, z, u) to be the ordinary generating series of rooted m-hypermaps, with x marking the number of vertices, y the number of hyperfaces, z the number of hyperedges and u twice the genus. Similarly, we define C([x.bar], y, z, u) to be the ordinary generating series of rooted m-constellations, except that with [x.sub.i] we mark the number of vertices with color i.

A k-factorization of identity (or simply k-factorization) in [S.sub.n] is a family of k permutations ([[sigma].sub.1], ..., [[sigma].sub.k]) in [S.sub.n] such that [[sigma].sub.1] ... [[sigma].sub.k] = id. Such a factorization is transitive if the family acts transitively on {1, ..., n}. There is a 1-to-(n - 1)![m.sup.n-1] correspondence between rooted m-hypermaps with n hyperedges and transitive 3-factorizations in [S.sub.mn] with cycle lengths in [[sigma].sub.1] all divisible by m. Similarly, rooted m-constellations with n hyperedges are in 1-to-(n - 1)! correspondence with transitive (m + 1)-factorizations in [S.sub.n] (c.f. [LZ04]). By noting [C.sub.[lambda]] the set of permutations with cycle type [lambda] and l([pi]) the number of cycles in a permutation [pi], we define the following generating series:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By taking the logarithm of the corresponding generating series, we can pass from general k-factorizations to transitive ones. We can now easily verify the following relations concerning generating series H, C of m-hypermaps and m-constellations, and [R.sub.H], [R.sub.C] defined above:

H(x,y,z,u) = [mu.sup.2] (z [[partial derivative]/[partial derivative]z](log[R.sub.H])) ([xu.sup.-1], [yu.sup.-1], [1/m] [zu.sup.m-1]), (1)

C([x.bar], y, z, u) = [u.sup.2] (z [[partial derivative]/[partial derivative]z] (log [R.sub.C])) ([[x.sub.i] [left arrow] [x.sub.i][u.sup.-1]], [yu.sup.-1], [zu.sup.m-1]). (2)

In an algebraic point of view, the series [R.sub.H] and [R.sub.C] are much easier to manipulate than H and C. To investigate the link between m-hypermaps and m-constellations, we will start by analyzing [R.sub.H] and [R.sub.C] using the group algebra of the symmetric group.

2.2 Characters and group algebra of the symmetric group

The group algebra C[S.sub.n] of the symmetric group [S.sub.n] is a complex vector space with a canonical basis indexed by elements of [S.sub.n] and a multiplication of elements extending distributively the group law of [S.sub.n]. For [theta] a partition of n (noted as [theta] [??] n), we define [K.sub.[theta]] to be the formal sum of elements in [S.sub.n] with cycle type [theta]. The elements [([K.sub.[theta]]).sub.[theta][??]n] form a basis of the center of C[S.sub.n]. According to the classic representation theory (c.f. [Ser77]), the center of C[S.sub.n] has another basis [(F[theta]).sub.[theta][??]n] formed by orthogonal idempotents.

For a partition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in which i appears [m.sub.i] times, we note [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and we know that n![z.sup.-1.sub.[lambda]] is the number of permutations of cycle type [lambda]. The change of basis between [([K.sub.[theta]]).sub.[theta][??]n] and [([F.sub.[theta]]).sub.[theta][??]n] is thus given by [F.sub.[lambda]] = [f.sup.[lambda]][(n!).sup.-1] [[summation].sub.[theta][??]n][[chi].sup.[lambda].sub.[theta]][K.sub.[theta]] and [K.sub.[lambda]] = n![z.sup.- 1.sub.[lambda]][[summation].sub.[theta][??]n][[chi].sup.[theta].sub.[lambda]][([ f.sup.[theta]]).sup.-1][F.sub.[theta]], where [[chi].sup.[lambda].sub.[theta]] is the irreducible character indexed by [lambda] evaluated on the conjugacy class of cycle type [theta], and [f.sup.[lambda]] the dimension of the irreducible representation indexed by [lambda] (c.f. [Sta99]).

We now consider the coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for arbitrary partitions [theta], [alpha], [[beta].sup.(1)], ..., [[beta].sup.(k)] of n. This coefficient, noted as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], can be interpreted as the number of factorizations [pi][[tau].sub.1] ... [[tau].sub.k][sigma] = id with [pi] and [[tau].sub.i] of cycle type [alpha] and [[beta].sup.(i)] respectively, and [sigma] a fixed permutation of cycle type [theta]. With this interpretation, using the change of basis between [([K.sub.[theta]]).sub.[theta][??]n] and [([F.sub.[theta]]).sub.[theta][??]n] given above and the fact that [(F[theta]).sub.[theta][??]n] are orthogonal idempotents, we can rewrite [R.sub.H] and [R.sub.C] as following.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

To further simplify the expressions above, we define the rising factorial function [[chi].sup.(n)] = x(x + 1) ... (x + n - 1) for n [member of] N. For a partition [theta], we define the polynomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Using this notation, we give the following expressions of [R.sub.H] and [R.sub.C].

Proposition 2.1 We can rewrite [R.sub.H] and [R.sub.C] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

This proposition comes from direct application of the following lemma (Lemma 3.4 in [JV90a]) to (3) and (4). We omit the proof of this lemma here. Readers can refer to the original paper for a proof.

Lemma 2.1 We have the following equality:

n![summation over ([alpha][??]n)][z.sup.-1.sub.[alpha]][[chi].sup.l([alpha])] - [f.sup.[theta]][H.sub.[theta]](x).

We can see that the characters in [R.sub.H] in Proposition 2.1 are all evaluated at the partition [[m.sup.n]] and partitions of the form m[mu] with [mu] [??] n. In [JV90a], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is proved to have an expression as a product of smaller characters, which is a crucial step towards the quadrangulation relation. This factorization is also presented in [JK81] (Section 2.7) under the framework of p-core and abacus display of a partition. By extending this approach in the next section to all partitions of the form m[mu], we will give a similar relation between m-hypermaps and m-constellations in Section 4.

3 Factorization of characters evaluated at m[lambda]

In this section we give a result on factorizing [[chi].sup.[theta].sub.[m[lambda]]] into smaller characters. Our result can be viewed in both algebraic and combinatorial perspectives.

* Algebraic approach

This approach exploits algebraic relations between symmetric functions and characters [[chi].sup.[theta].sub.[lambda]] (c.f. [Sta99]). More specifically, to evaluate [[chi].sup.[theta].sub.[m[lambda]]], we want to use the Jacobi-Trudi identity to express Schur function [s.sub.[theta]] as a determinant D in homogeneous functions, then extract the coefficient of power sum function [p.sub.m[lambda]] from D. Due to properties of symmetric functions, many terms in the determinant are irrelevant in extraction of coefficient, and thus we only need to evaluate a simpler determinant D' that has a block structure which can be revealed by the m- decomposition of [theta] introduced in [JV90a]. Since each block has a similar structure to D itself, we obtain the factorization desired. Though the basic ingredients already exist in [JV90a, JV99], our presentation here stresses more on the block structure of the reduced Jacobi-Trudi determinant, rendering our proof much more conceptual and accessible.

* Combinatorial approach

This approach gives a purely combinatorial interpretation of our factorization of characters using ribbon tableaux and the boson-fermion correspondence. With the Murnaghan- Nakayama rule (c.f. [Sta99]), character evaluation can be expressed using enumeration of signed ribbon tableaux. By coding partitions as infinite lattice paths, we define a notion of m-split for partitions [theta] with an empty m-core, and we establish a bijection between ribbon tableaux of shape [theta] and of content m[lambda] to tuples of smaller ribbon tableaux whose shapes are exactly components in the m-split of [theta]. With the boson-fermion correspondence and

the infinite wedge space (c.f. [Oko01]), we also verify that the sign incorporates well in our bijection for the desired factorization. This approach is also related to the notion of p-core and p-quotient (c.f. [JK81]).

These two approaches are essentially two sides of the same coin, since we can show that the notions of m-decomposition and m-split coincide. For consistency of style, we only present the algebraic approach here. For details on the combinatorial approach, readers can refer to a future full version of this paper.

Before proceeding to our algebraic approach, we try to convey our idea about character factorization via an example. Consider the partition [theta] = (6, 6, 4, 4, 4, 3, 3). To evaluate [[chi].sup.[theta].sub.3[lambda]] for arbitrary [lambda], we want to extract the coefficient of the power sum function [p.sub.3[lambda]] in det(D) for D below provided by the Jacobi-Trudi identity for the Schur function [s.sub.[theta]]. Terms in D are all homogeneous symmetric functions [([h.sub.k]).sub.k[member of]N].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since the power sum functions [([p.sub.k]).sub.k>0] are algebraically independent, when extracting the coefficient of [p.sub.3[lambda]] in D, we only need to consider [h.sub.k] with k divisible by 3. We can thus ignore a lot of terms in D, leading to evaluating det([D.sub.1]) on a simpler matrix [D.sub.1], which can be arranged with permutation of rows and columns to be a block matrix [D.sub.2] as below.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can see that each block of [D.sub.2] has a similar form to the matrix in Jacobi-Trudi identity, up to some variable substitutions. From the block structure we can clearly observe a factorization of [[chi].sup.[theta].sub.3[lambda]] in 3 parts.

To achieve a rigorous description of the phenomenon presented in the example above, we start with the following definition of the m-decomposition of a partition and of m-balanced partitions, first introduced in [JV90a]. Though apparently artificial and technical at first sight, the notion of m-balanced partition can arise from the boson-fermion correspondence in a very natural way in our combinatorial perspective, which will be discussed in a future full version of this paper.

Definition 3.1 (m-decomposition of a partition, m-balanced partition) Given m, n [member of] N, let [alpha] be a partition of mn. For j from 1 to m, we define the following objects:

* the set [P.sub.j] = {i|[[alpha].sub.i] - i + j [equivalent to] 0 mod m},

* [m.sub.j] the cardinality of [P.sub.j],

* [p.sub.j,1], ..., [p.sub.j],[m.sub.j] as a list of elements of [P.sub.j] with increasing order,[right arrow]

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all j, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all i from 1 to [m.sub.j].

We can see that the sets [P.sub.j] form a set partition of {1,2, ..., l([alpha])}. We note [[[alpha].bar].sub.m] = ([[alpha].sup.(1)], ..., [[alpha].sup.(m)]) the m-decomposition of [alpha], and we define two permutations [[pi].sub.[alpha]], [[pi]'.sub.[alpha]] defined explicitly as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If for all j we have [m.sub.j] = [(l([alpha]) - j + 1)/m], we say that [alpha] is m-balanced.

In our running example, we verify that the partition [theta] = (6, 6, 4, 4, 4, 3, 3) is 3-balanced, and its 3- decomposition is ((2,1,1), (2,2), (1,1)). The permutations [[pi].sub.[theta]] and [[pi]'.sub.[theta]] are respectively row and column permutation used to go from matrix [D.sub.1] to [D.sub.2].

Given a partition [lambda] [??] n, we note [absolute value of [lambda]] = n the weight of [lambda]. For an m-balanced partition [alpha] [??] mn with [[[alpha].bar].sub.m] = ([[alpha].sup.(1)], ..., [[alpha].sup.(m)]), we have [[summation].sup.m.sub.i=1] [absolute value of [[alpha].sup.(i)]] = n. Conversely, given a list of partitions ([[alpha].sup.(1)], ..., [[alpha].sup.(m)]) with [[summation].sup.m.sub.i=1] [absolute value of [[alpha].sup.(i)]] = n, we can recover an m-balanced partition [alpha] [??] mn. There is a bijection between m-balanced partitions of mn and lists of m partitions that sums in total to n (c.f. Proposition 4.2, 4.3, 4.5 and Lemma 4.6 in [JV90a]).

The m-decomposition of a partition introduces the following factorization of the polynomial [H.sub.[theta]](x).

Lemma 3.1 For [theta] [??] n, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: We define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By direct computation, we easily verify that [H.sup.[theta].sub.m](x) = [m.sup.mn][[PI].sup.m-1.sub.j=0][H.sub.[theta]] (x+j/m). We then obtain our result by applying Lemma 4.11 of [JV90a], which states that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], to the equality we just verified.

For an alternative proof that is purely combinatorial, readers can refer to the combinatorial perspective of character factorization in a future full version of this paper.

In [JV90a], the notion of m-decomposition is used to give a factorization of irreducible characters of the symmetric group evaluated at "semiregular" partitions, i.e. partitions of the form [[(mk).sup.n]], into characters in smaller symmetric groups. We now extend this result to partitions of the form m[lambda]. The theorem and its proof we are giving below stress more on the block structure of the reduced Jacobi-Trudi determinant. As a result, not only is our result more general, but our proof is also more conceptual.

Theorem 3.1 (Main result on character factorization) Let m, n be two natural numbers, and [lambda] [??] n, [theta] [??] mn be two partitions. We consider partitions as multisets and we denote multiset sum by [??]. If [theta] is m-balanced, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [theta] is not m-balanced, [[chi].sup.[theta].sub.m[lambda]] = 0.

Proof: According to the Jacobi-Trudi identity, we can express [[chi].sup.[theta].sub.[lambda]] as a determinant.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In the case of [[chi].sup.[theta].sub.m[lambda]], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We notice that [[p.sub.[lambda]]][h.sub.k] [not equal to] 0 implies [lambda] [??] k. Consider the matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the Jacobi-Trudi identity. Since we always take the coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] when computing the determinant of M, we can ignore entries [h.sub.k] in M when k is not a multiple of m. As the entry at (i, j) is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we consider only the entries [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a multiple of m, which is equivalent to i [member of] [P.sub.j] in the m-decomposition of [theta]. If we permute the columns of M with [[pi].sub.[theta]] and the rows of M with [[pi]'.sub.[theta]], we obtain a block diagonal matrix M'. For M' to have full rank, we need [theta] to be m- balanced. As a result, when [theta] is not m-balanced, M' does not have full rank, and we have [[chi].sup.[theta].sub.m[lambda]] = 0 since the determinant is zero.

We now analyze the case where [theta] is m-balanced. We can see that, in the sum over [sigma], only those [sigma] with i [member of] [P.sub.[sigma](i) mod m] for every i have a non-zero contribution. In the perspective of the block diagonal matrix M', they are exactly permutations compatible with its blocks. It is now natural to see [sigma] as a list of permutations over each [P.sub.i], and to decompose the sum as a product of sums over permutations of each [P.sub.i], which is equivalent to evaluating det(M') as the product of determinants of blocks in M'.

We notice that, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have [[p.sub.[lambda]]][h.sub.n] = [z.sup.- 1.sub.[lambda]], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. With the equality above, we now conclude our proof by the promised decomposition.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4 Generalization of the quadrangulation relation

In this section, using Theorem 3.1, we establish a relation between m-hypermaps and m-constellations in arbitrary genus that generalizes the quadrangulation relation. We then recover a result in [Cha09] on asymptotic behavior of m-hypermaps related to that of m-constellations. We start by showing a link between the series [R.sub.H] and [R.sub.C], using Theorem 3.1.

Proposition 4.1 The generating series [R.sub.H] and [R.sub.C] are related by the following equation.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: We take the expressions of [R.sub.H] and [R.sub.C] from Proposition 2.1. We observe that, in the expression of [R.sub.H], we only need to consider those [theta] which are m-balanced. For [theta] m-balanced, let ([[theta].sup.(1)], ..., [[theta].sup.(m)]) be the m-decomposition of [theta], and we have the following equality derived from Theorem 3.1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We then substitute the equality above and Lemma 3.1 into the expression of [R.sub.H] in Corollary 2.1 to factorize [R.sub.H] into a product of [R.sub.C] evaluated on different points as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This link between [R.sub.H] and [R.sub.C] can be translated directly into a link between the series H(x, y, z, u) of m-hypermaps and the series C([x.bar], y, z, u) of m-constellations, resulting in our main result as follows.

Theorem 4.1 The generating series of m-constellations and m-hypermaps are related by the following formula:

H(x, y, z, u) = m [m.summation over (j=1)]C ([[x.sub.i] [left arrow] [x + (i - j)u/m]], y/m, [m.sup.m-1]z, u).

Proof: This comes directly from a substitution of the equality in Proposition 4.1 into (1) and (2).

We note [H.sup.(g)](x,y,z) = [[u.sup.2g]]H(x,y,z,u) and [C.sup.(g)](x,y,z) = [[u.sup.2g]]C(x, y, z, u) the generating functions of m-hypermaps and m-constellations of genus g respectively. We can now express the following corollary concerning the link between m-hypermaps and m-constellations with respect to the genus.

Corollary 4.1 We have the following relation between the generating series [H.sup.(g)] and [C.sup.(g)]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: We want to compute [H.sup.(g)](x, y, z) = [[u.sup.2g]]H(x, y, z, u).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To obtain the final result, we then simplify the formula above with the fact that each term in [C.sup.(g)] has the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], according to the Euler relation.

We can further generalize these results. Let D be a subset of [N.sup.*]. We define (m, D)-hypermaps and (m, D)-constellations as m-hypermaps and m-constellations with the restriction that every hyperface has its degree in mD. We note respectively [H.sub.D] (x, y, z, u) and [C.sub.D] (x, y, z, u) their generating functions. We 22have the following corollary. We omit its proof here, but we can see that the whole proof mechanism for Theorem 4.1 transfers directly onto [H.sub.D] (x, y, z, u) and [C.sub.D] (x, y, z, u) with the observation that, in the proof of Theorem 3.1, if all parts of [lambda] are in mD, then all parts of every [[lambda].sup.(i)] are in D.

Corollary 4.2 (Main result in the form of series) We have the following equations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By taking m = 2 and D = {2}, {p} or D arbitrary, we recover the quadrangulation relation and its extensions in [JV90b] and [JV99] respectively. Though the relation seems to be a bit monstrous at first glance, it actually has an elegant combinatorial interpretation. We define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to be the number of rooted m-constellations with n hyperedges, and hyperface degree restricted by the set D, with [a.sub.i] marked vertices of color i for i from 1 to m - 1. The number [H.sup.(g).sub.n,m,D] is the counterpart for rooted m-hypermaps without the marking part. For m = 3 and m = 4, we have the following elegant relations.

Corollary 4.3 (Generalization of the quadrangulation relation, special case m = 3, 4) For m = 3, 4, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We notice that the coefficients are always positive integers. This is not a coincidence. In fact, by carefully rearranging terms, we can obtain the following more general relation.

Corollary 4.4 (Generalization of the quadrangulation relation, for arbitrary m) With certain coefficients [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] all integral and positive, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A detailed proof can be found in a future full version of this paper. This relation might hint an unknown combinatorial bijection between m-hypermaps with given genus and some families of decorated m-constellations with lower genus. It is thus interesting to try to understand the combinatorial meaning of these coefficients.

According to Theorem 3.1 in [Cha09], the number [C.sup.(g).sub.n,m,D] = [C.sup.(g,0, ..., 0).sub.n,m,D] of (m, D)- constellations with n hyperedges without marking grows asymptotically in [THETA]([n.sup.[5/2](g- 1)][[rho].sup.n.sub.m,D]) when n tends to infinity in multiples of gcd(D). Using Corollary 4.2, we now give a new proof of Theorem 3.2 of [Cha09] about the asymptotic behavior of the number of (m, D)-hypermaps.

Corollary 4.5 (Asymptotic behavior of (m, D)-hypermaps) We have the following asymptotic behavior of (m, D)-hypermaps when n tends to infinity in multiples of gcd(D):

[H.sup.(g).sub.n,m,D] ~ [m.sup.2g][C.sup.(g).sub.n,m,D].

Proof: We observe that, in the second part of Corollary 4.2, for a fixed k, the number of differential operators applied to [C.sup.(g-k).sub.D] does not depend on n, and they are all of order 2k. Since in an m-hypermap, the number of vertices with a fixed color i is bounded by the number of hyperedges n, the contribution of the term with k = t is O([n.sup.[5/2](g-t-1)+2t] [[rho].sup.n.sub.m,D]) = O([n.sup.[5/2](g-1)- [1/2]t][[rho].sup.n.sub.m,D]). The dominant term is therefore given by the case k = 0, with [C.sup.(g).sub.n,m,D] = [THETA]([n.sup.[5/2](g- 1)][[rho].sup.n.sub.m,D]), and we can easily verify the multiplicative constant.

This corollary, alongside with its proof, is a refinement of the asymptotic enumerative results established in [Cha09] on the link between m-hypermaps and m-constellations.

Acknowledgement

I would like to thank my supervisors, Guillaume Chapuy and Sylvie Corteel from LIAFA, for proofreading and inspiring discussion on both the form and the content of this article. I would also like to thank anonymous reviewers for their precious comments.

References

[BDFG04] J. Bouttier, P. Di Francesco, and E. Guitter. Planar maps as labeled mobiles. Electron. J. Combin., 11(1):Research Paper 69, 27, 2004.

[BMS00] Mireille Bousquet-Melou and Gilles Schaeffer. Enumeration of planar constellations. Adv. in Appl. Math., 24(4):337-368, 2000.

[Cha09] Guillaume Chapuy. Asymptotic enumeration of constellations and related families of maps on orientable surfaces. Combin. Probab. Comput., 18(4):477-516, 2009.

[JK81] Gordon James and Adalbert Kerber. The representation theory of the symmetric group, volume 16 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn, With an introduction by Gilbert de B. Robinson.

[JV90a] D. M. Jackson and T. I. Visentin. A character-theoretic approach to embeddings of rooted maps in an orientable surface of given genus. Trans. Amer. Math. Soc., 322(1):343-363, 1990.

[JV90b] D. M. Jackson and T. I. Visentin. Character theory and rooted maps in an orientable surface of given genus: face-colored maps. Trans. Amer. Math. Soc., 322(1):365-376, 1990.

[JV99] D. M. Jackson and T. I. Visentin. A combinatorial relationship between Eulerian maps and hypermaps in orientable surfaces. J. Combin. Theory Ser. A, 87(1):120-150, 1999.

[LZ04] Sergei K. Lando and Alexander K. Zvonkin. Graphs on surfaces and their applications, volume 141 of Encyclopaedia of Mathematical Sciences. Springer-Verlag, Berlin, 2004. With an appendix by Don B. Zagier, Low-Dimensional Topology, II.

[Oko01] Andrei Okounkov. Infinite wedge and random partitions. Selecta Math. (N.S.), 7(1):57-81, 2001.

[PS02] Dominique Poulalhon and Gilles Schaeffer. Factorizations of large cycles in the symmetric group. Discrete Math., 254(1-3):433-458, 2002.

[Ser77] Jean-Pierre Serre. Linear representations of finite groups. Springer- Verlag, New York, 1977. Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42.

[Sta99] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

Wenjie Fang ([dagger])

Ecole normale superieure, 45 rue d'Ulm, F-75230 Paris Cedex 05, France

([dagger]) This work is partially supported by ANR IComb (ANR-08-JCJC-0011).
COPYRIGHT 2013 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Fang, Wenjie
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUFR
Date:Jan 1, 2013
Words:5319
Previous Article:A combinatorial method to find sharp lower bounds on flip distances.
Next Article:A uniform model for Kirillov-Reshetikhin crystals.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters