Printer Friendly

Are even maps on surfaces likely to be bipartite?

It is well known that a planar map is bipartite if and only if all its faces have even degree (what we call an even map). In this paper, we show that rooted even maps of positive genus g chosen uniformly at random are bipartite with probability tending to [4.sup.-g] when their size goes to infinity. Loosely speaking, we show that each of the 2g fondamental cycles of the surface of genus g contributes a factor 1/2 to this probability.

We actually do more than that: we obtain the explicit asymptotic behaviour of the number of even maps and bipartite maps of given genus with any finite set of allowed face degrees. This uses a generalisation of the Bouttier-Di Francesco-Guitter bijection to the case of positive genus, a decomposition inspired by previous works of Marcus, Schaeffer and the author, and some involved manipulations of generating series counting paths. A special case of our results implies former conjectures of Gao.

Keywords: graphs on surfaces, labelled trees, algebraic series, lattice walks.

1 Introduction.

Maps are combinatorial objects which describe the embedding of a graph in a surface. The enumeration of maps began in the sixties with the works of Tutte (for example the paper [Tut63]). By analytic techniques, involving recursive decompositions and non trivial manipulations of power series, Tutte obtained beautiful and simple enumerative formulas for several families of planar maps. His techniques were extended in the late eighties by several authors to more sophisticated families of maps or to the case of maps of higher genus. Bender and Canfield ([BC86]) obtained the asymptotic number of maps on a given orientable surface. Gao ([Gao93]) obtained formulas for the asymptotic number of 21-angulations on orientable surfaces, and conjectured a formula for more general families (namely maps where the degrees of the faces are restricted to lie in a given finite subset of 2N).

A few years later, Schaeffer ([S699]), following the work of Cori and Vauquelin ([CV81]), gave in his thesis a bijection between planar maps and certain labeled trees which enables to recover the formulas of Tutte, and explains combinatorially their remarquable simplicity. This bijection has suscited a lot of interest in probability and physics, since it also enables to study geometrical aspects of large random maps ([CS04, LG07, LGP, BG, Mie]). It has been generalized in two directions. First, Bouttier, Di Francesco, and Guitter ([BDFG04]) gave a construction that generalizes Schaeffer's bijection to the large class of Euleriayy maps, which includes for example maps with restricted face degrees, or constellations. Secondly, Marcus and Schaeffer ([MS]) generalized Schaeffer's construction to the case of maps drawn on orientable surfaces of any genus, opening the way to a bijective derivation ([CMS07]) of the asymptotic results of Bender and Canfield.

The first purpose of this work is to unify the two generalisations of Schaeffer's bijection: we show that the construction of Bouttier, Di Francesco, and Guitter stays valid in any genus, and involves the same kind of objects as developped in [MS]. Our second (and main) task is then to use this bijection to perform the asymptotic enumeration of several families of maps of genus g, namely bipartite maps and maps with even face degrees (recall that these two families coincide only in the planar case). Our first tool is the reduction of the combinatorial objects inherited from the bijection to a finite number of schemes, from which all the objects can be reconstructed by an involved arrangement of some families of paths. The asymptotics estimates are then obtained by a precise study of the generating series of these paths, by algebraic methods. The link between even maps and bipartite maps is made thanks to an unexpected incursion of elementary algebraic graph theory, and the introduction of the cycle space of some minimal maps of genus g.

Remark: this paper is a shorten version of [Cha], and a certain number of things had to be dropped. First, in [Cha], the bijection is presented in the general case of Eulerian maps, and all the enumerative results are proved in the general setting of m -constellations and m-hypermaps (this paper corresponds to the case m = 2). Moreover, the size of the paper is not sufficient to contain proofs, for which we refer the reader to [Cha].

2 Definitions and main results.

Let [S.sub.g] be the torus with g-handles. A map on [S.sub.g] (or map of genus g) is a proper embedding of a finite graph G in [S.sub.g] such that the maximal connected components of [S.sub.g] \ G are simply connected regions. Multiple edges an loops are allowed. The maximal simply connected components are called the faces of the map. The degree of a face is the number of edges incident to it, counted with multiplicity.

We consider maps up to homeomorphism, i.e. we identify two maps such that there exists an orientation preserving homeorphism that sends one to the other. In this setting, maps become purely combinatorial objects (see [MT01] for a detailed discussion on this fact). In particular, there are only a finite number of maps with a given number of edges, opening the way to enumeration problems.

All the families of maps considered in this article will eventually be rooted (which means that an edge has been distinguished and oriented), pointed (when only a vertex has been distinguished), or both rooted and pointed. In every case, the notion of oriented homeomorphism involved in the definition of a map is adapted in order to keep trace of the pointed vertex or edge.

An even map is a map whose all faces have even degree. A bipartite map is a map whose vertices can be coloured in two colors, such that only vertices of different colors are linked by an edge. All bipartite maps are even maps, but the reverse implication is not true (it is, however, in the planar case). In the rest of the paper, D [subset] [N.sub.>0] will be a finite subset of the positive integers whose maximum is at least 2. A map with degree set 2D is a map whose all faces have a degree in 2D. Our main results are the two theorems:

Theorem 1 The number [b.sub.g,D](n) of rooted bipartite maps of genus g and degree set 2D, with n edges, satisfies:


Are even maps on surfaces likely to be bipartite?

when n tends to infinity along multiples of gcd(D), and where the constants [[beta].sub.D], [[gamma].sub.D] and [z.sup.(c).sub.D] are defined by: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [t.sup.(c).sub.D] is the smallest positive root of. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the constant [t.sub.g] is defined in [BC861.

Theorem 2 The number [c.sub.g,D] (n) of rooted maps of genus g and degree set 2D, with n edges, satisfies:


when n tends to infinity along multiples of gcd(D).

Observe that the second theorem says that large even maps of fixed degree set are bipartite with probability [4.sup.-g] + o(1). This was, to our knowledge, only known in the case of quadrangulations (see [Ben91] and references therein). Putting Theorems 1 and 2 together gives an asymptotic formula for the number of maps with degree set 2D, which Gao already proved when D is a singleton, and conjectured for general D in the paper [Gao93]. All the other cases were, as far as we know, unknown.

3 Bijective decompositions.

3.1 The Bouttier, Di Francesco and Guitter construction.

We describe the Bouttier, Di Francesco and Guitter bijection on [S.sub.g], by unifying it with the construction of [MS]. All constructions are similar to the planar case. The key point is to replace the notion of tree by the one of map with one face (as it was already the case in [MS]).

Given a rooted and pointed map m on [S.sub.g], we procede to the following construction. First, we label each vertex of m by the minimum number of edges needed to reach it from the pointed vertex. Observe that if two vertices are connected by an edge, then by the triangle inequality, their label differ at most by 1. Then, we add a new vertex inside each face F of m, and for every edge c adjacent to F, we procede to the following construction (see Figure 1): if the label decreases by 1 along e when turning clockwise around F, we add a new edge between the central vertex of F and the extremity of e of maximum label. Else, if the label is constant along e, we add a new edge that links the central vertices of the two faces separated by e. Moreover, we equip this edge with a flag, that remembers the label of the extremities of e. In the third case (if the label increases along e) we do nothing.


Once we have applied the construction above to all faces and edges, we remove all the original edges of m, and we also remove the pointed vertex. We let m be the map obtained at this step. We use the root of m to define in a unique way a root in m, with the convention of Figure 1. We have:

Lemma 1 [??] is a connected map on [S.sub.g], which has only one face.

We now define what a mobile is (again, this is a copy of the planar case).

Definition 1 A g-mobile is a map of genus g, with one face, and with two types of vertices: labelled ones, which carry integer labels, and unlabelled ones, such that:

i. each edge is adjacent to at least one unlabelled vertex. Edges linking two unlabelled vertices carry an additional flag, which is itself labelled by an integer

ii. around each unlabelled vertex, consider the sequence of its ajaceyyt vertices and flags, read in counter-clockwise order. Then a labelled vertex of label n is followed by a label [greater than or equal to] n - 1 (vertex or flag), whereas a flag of label n is followed by a label [greater than or equal to] n (vertex or flag).

iii. the label carried by the root edge (flag or vertex) equals 0.

In a mobile, the effective degree of an unlabelled vertex adjacent to f flagged edges and l labelled vertices is by definition the quantity f + 2l. A mobile with degree set 2D is a mobile in which all unlabelled vertices have an effective degree which belongs to 2D.

Observe that in the definition above, we do not ask the labels to be positive: they are elements of Z. We let Mob(m) be the map obtained from m by translating all its labels by the same integer in order that it satifies condition iii. Then we have:

Proposition 1 The application Mob is a bijectiony between the set of rooted and pointed maps with n edges and genus g, and the set of g-mobiles with n edges. This application induces a correspondance between the faces of m and the unlabelled vertices of Mob(m)which sends the degree to the effective degree.

Remark a: Observe that an even map is bipartite if and only if the labels by the distance of any two adjacent vertices differ by [+ or -] 1 (to see that, observe that a map is bipartite if and only if the distance from the pointed vertex, taken modulo 2, realizes a bipartite coloration). Hence, an even map m is bipartite if and only M ob(m) has no flagged edge: this will be of great importance in this paper.

Remark b: Only the proof that the construction is well-defined, and gives indeed a mobile, is different from the planar case (see [Cha]). After that, to prove that M ob is a bijection, one can copy the proof of [BDFG04].

3.2 The superchains of a mobile.

We follow the technique introduced in [CMS07], that enables to reduce the mobiles to a finite number of objects. Let us start with a mobile t. We erase recursively all the vertices of t of degree 1, until there are no more such vertices left. We are left with a map whose all vertices have degree at least 2. In that map, the vertices of degree 2 are organised into maximal chains, connected together at vertices of degree at least 3. We call these chains the superchaiyys of t. The vertices of degree [greater than or equal to] 3 that are at the extremities of the superchains are the nodes of t: they can be labelled or unlabelled. This step is illustrated on Figure 2 (b). We now need a simple observation: in a sequence of an even number of elements of {-1, 0, 1} that sum to 0, there has to be an even number of 0's. Consequently, if m is an even map, the unlabelled vertices of its mobile M ob(m) are all linked to an even number of flagged edges. This implies that all the flagged edges of of M ob(m) lie on the superchains (and not in the planar parts that are recursively removed in the construction above ; otherwise, one of the trees forming these removed parts should contain either an infinite sequence of distinct flagged edges, or a cycle, which is impossible). One can go further and observe the following:


Lemma 2 The superchains of t can be of two types:

* superchains that contain no flagged edges (which we call superchains of type 0)

* superchains that contain only flagged edges (which we call superchains of type 1).

We now explain how to decompose superchains into elementary bricks. An elementary star is a star formed by a central unlabelled vertex, joined to a certain number of labelled vertices and flags, that satisfy condition ii of Definition 1 (see Figure 3). We consider elementary stars up to translation of the labels. We now define what will be the building blocks of the superchains:

Definition 2 A cell of type 0 is an elementary star which carries two distinguished labelled vertices (the in one and the out one), and has no flagged edge.

A cell of type 1 is an elementary star which carries exactly two flagged edges, one of them being distinguished as the in one and the other as the out one.

The increment of the cell is the difference between the labels of its out and in vertices or flags.


Let us fix a superchain c. In the original mobile t (before we started deleting things), each unlabelled vertex lying on c was at the center of an elementary star. We now re-draw all these stars around the unlabelled vertices of c, as in Figure 4. If the extremities of c are unlabelled vertices, we say that the associated stars are nodal stars of t ; observe that a nodal star necessarily belongs to several superchains. Between the nodal stars, the superchain reduces to a sequence of cells of the same type (as in Figure 4). The in (resp. out) vertex or flag of a superchain is the in (resp. out) vertex or flag of its first cell (resp. last cell). Observe that that definition depends on a choice of an orientation of c, which will be precised later. The increment of a superchain is the difference [l.sub.out] - [], of the labels of its in and out vertices or flags. All those definitions are illustrated on Figure 4.


We now explain what happens at the nodes of t. It can happen that k [greater than or equal to] 3 superchains meet together at a labelled vertex: in this case, they are all of type 0. The other case is that they meet at an unlabelled vertex, or, speaking in terms of stars, at a nodal star [upsilon]. Each flagged edge of v is attached to the in (or out) flag of a superchain of type 1. Moreover, since we started with an even map, the number of such flagged edges has to be even. This implies a very important fact: the number of superchains of type 1 meeting at a given nodal star is always even. Here, superchains are counted with multiplicity, i.e. a superchain which is adjacent twice to the same nodal star is counted twice.

3.3 Schemes and their typing space.

Definition 3 A scheme of genus g is a rooted map of genus g, which has only one face, and whose all vertices have degree [greater than or equal to] 3.

The typing space of a scheme is the set of applications [tau] : {edges of s} [right arrow] {0, 1}, that satisfy the Kirchoff law around each vertex v: [summation over e~v] [tau](e) = 0 mod 2, where the sum is taken over all edges adjacent to v, with multiplicities.

A typed scheme a pair (s, [tau]) formed by a scheme and an element of its typing space.

Observe that the typing space is a [Z.sub.2] vector space. Actually, it coincides with the cycle space of s in the classical sense of algebraic graph theory. Now it is classical (and easy to see by induction) that the dimension of the cycle space of a connected graph equals its number of edges minus its number of vertices, plus 1. Since s has one face, Euler characteristic formula precisely says that:

Proposition 2 The dimension of the typing space of a scheme of genus g is 2g.

Let (s, [tau]) be a typed scheme. We say that (s, [tau]) is decorated if each vertex v of x is associated with an elementary star [F.sub.v] and a "gluing" application that maps the half-edges of x adjacent to v to the labelled vertices and flags of [F.sub.v]; this application must respect the clockwise order, and associate only edges of type 1 with flags, and edges of type 0 with labelled vertices. In few words, a scheme is decorated once we have chosen some elementary stars to put on its vertices, in a way which is compatible with the typing (see Figure 2(c)). By convention, if only edges of type 0 meet at a vertex, we allow a single labelled vertex o as a possible nodal star.

We now build the decorated scheme of t. We first replace each superchain by an edge: by construction, we obtain a scheme s, which we call the scheme of t (we choose the root of x to be the edge corresponding to the superchain that was carrying the original root of t on its right). This is illustrated in Figure 2(c). The typed scheme of t is the pair (s, [tau]) where [tau] is the application that maps each edge to the type of the corresponding superchain (which is a valid element of the typing space, from the remarks above). Finally, the decorated scheme of t is the triple (s, [tau], F), where for each vertex v of s, [F.sub.v] is the nodal star corresponding to v in t ; if v corresponds to a labelled vertex in t, we just put [F.sub.v] = o (we are quite unprecise here: our notation should keep track of the gluing application, which is implicit there, to keep things lighter).

We assume that for each decorated scheme, and for each vertex v, the star [F.sub.v] carries an arbitrary labelled vertex or flag, fixed once and for all, which we call the canonical element of v. If (s, [tau], F) is the decorated scheme of t, we let [l.sub.v] be the label in t of the canonical element of v. We now normalize the [l.sub.v] 's, so that they form an integer interval of the form [0, M] : precisely, we let M + 1 be the number of different [l.sub.v] 's, and [lambda] be the unique increasing surjective application from {[l.sub.v], v [member of] s} to [0, M]. We say that the quadruple (s, [tau], F, [lambda]) is the full scheme of t. To sum up, the full scheme of t contains four informations: the combinatorial arrangement of superchains, given by s ; the types of the superchains, given by [tau] ; the nodal stars that lie at the intersection of the superchains, given by F; the relative order of the labels in t of the canonical elements, given by [lambda]. One can prove that for fixed g and D the number of distinct full schemes is finite.

4 Re-constructing all mobiles from the full schemes.

In what precedes, we identified what are the building blocks of a mobile. We now compute the corresponding generating series.

4.1 Some generating series.

Observe that elementary stars are in bijection with circular Motzkin walks (i.e. walks on a cycle with steps in {-1, 0, 1}). Flagged edges correspond to steps 0, and labelled vertices to steps -1. Since all the objects we are interested in are related to those elementary stars, and since, once they are rooted somewhere, Motzkin walks are roughly speaking counted by binomial numbers, this will enable us to perform the exact computation of the generating series we are looking for.

First, we let [T.sub.D] = [T.sub.D] (z) be the generating series of planar mobiles of degree set 2D by the number of edges. One easily sees by decomposing a mobile at its root star that: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We let [P.sub.D] (X, t) be the generating polynomial of elementary cells of type 0, where t counts the number of labelled vertices, and X counts the increment. The subscript D stresses that we allow only stars with effective degree in 2D. [P.sub.D] is therefore a polynomial in t and a Laurent polynomial in X, which is symmetric under the exchange X [left and right arrow] [X.sup.-1]. We let SD (X, t) be the generating series of sequences of cells of type 0 by the total number of labelled vertices (counted with multiplicity) and the total increment; [S.sub.D] is a formal power series in t with coefficients that are Laurent polynomials in X. We have by classical symbolic combinatorics: [S.sub.D] (X, t) = 1 / 1 - [P.sub.D](X,t). The kernel is the polynomial 1 - [P.sub.D] (X, t). As a Laurent polynomial in X, it has 2r roots, where r = max(D) - 1. r of these roots, say [[alpha].sub.1] (t),... [[alpha].sub.r] (t), are finite at t = 0. By symmetry, the other r roots are then [[alpha].sup.-1.sub.1],... [[alpha].sup.-1.sub.1]. One of the finite roots, say [[alpha].sub.1] (t), is a positive increasing function for t [member of] [0, [t.sup(c).sub.D]]; on this interval [[alpha].sub.1] dominates in modulus all the other [[alpha].sub.i]'s. Moreover, one has [[alpha].sub.1] ([t.sub.(c).sub.D]) = 1. We say that [[alpha].sub.1] is the principal branch.

The generating series [M.sub.D,l](t) = [[X.sup.l]]S(X,t) of sequences of cells of type 0 of total increment l is easily obtained by a partial fraction expansion of [S.sub.D]. We obtain:


The substitution t [left arrow] z[T.sub.D] (z) corresponds to attaching a (eventually trivial) planar mobile to each labelled vertex of the sequence of cells. Hence, the series [H.sup.0.sub.D,l](z):= [M.sub.D,l](z)) is the generating series of sequences of cells of type 0, of total increment l, carrying planar mobiles attached on their labelled vertices, by the total number of edges. We let [H.sup.1.sub.D,l](z) be the corresponding quantity for type 1: [H.sup.1.sub.D,l](z) is the generating series of sequences of cells of type 1 and total increment l, where planar mobiles are attached on the labelled vertices, by the total number of edges. One can prove, thanks to the close relation between the Motzkin walks corresponding to cells of type 0 and 1:

Lemma 4 We have: [H.sup.1.sub.D,l](z) = [T.sub.D](z)[H.sup.0.sub.D,l](z)

4.2 Re-constructing mobiles.

Let us fix a full scheme f = (s, [tau], F, [lambda]). We say that an integer vector [([l.sub.v]).sub.v[member of]s] is compatible with [lambda] if normalizing it to an integer interval as we did above yields the vector [lambda]. If we consider these vectors up to translation, then all the vectors ([l.sub.v]) compatible with [lambda] are of the form:

[l.sub.v] = [[lambda](v).summation over i=1] [[delta].sub.i] for some [delta] [member of] [([N.sub.>0]).sup.M].

Assume that such a labelling has been fixed. To reconstruct a mobile, we have to do the inverse of what precedes, and substitute a sequence of cells of the good type along each edge of s. Observe that, for each edge e, the increment [DELTA] (e) of the superchain to be substituted to e is fixed by the choice of ([l.sub.v]). Precisely, if [e.sub.+] and [e.sub.-] are the extremities of e, with the convention [lambda]([e.sub.+]) [greater than or equal to] [lambda]([e.sub.-]), then we have [DELTA](e) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where aF(e) is a correction term that does not depends on the [l.sub.v]'s, and that accounts for the fact that superchains do not necessarily begin and end at the canonical vertices. Putting it in terms of the [[delta].sub.i]'s, we can write: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where for each edge e and j [member of] [1, M] we put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If we denote by [e.sub.F] (resp. []) the total number of edges (resp. labelled vertices) appearing in the decoration F, we have to compute the following sum:


where we noted [T.sub.D], [[alpha].sub.i] and [C.sub.i] for [T.sub.D](z), [[alpha].sub.i](z[T.sub.D](z)) and [C.sub.i] (z[T.sub.D](z)), respectively. Observe that [R.sub.f] is not precisely the generating series of mobiles of scheme f, because we have not yet chosen a root in our mobile. It is possible to distinguish an arbitrary edge by a derivation of the series: one obtains a rooted mobile, whose scheme is equal to s as an unrooted map, but may have a different rooting. Precisely, if [absolute value s] denotes the number of edges of s, each rooted mobile of scheme s can be obtained in [absolute value of s] different ways as above, which leads to:

Lemma 5 Let [R.sub.D](z) be the series of all rooted mobiles of genus g and degree set 2D, and [R.sup.bip.sub.D](z) the series of such mobiles that carry no flagged edges. We have:

[R.sub.D](z) = zd / dz [summation over (s,[lambda],[tau],F)] 1 / [absolute value of s] [R.sub.(s,[lambda],[tau],F)](z), where the sum is taken over all the full schemes of genus g.

Moreover: [R.sup.bip.sub.D](z) = zd / dz [summation over (s,[lambda],[??],F)] 1 / [absolute value of s] [R.sub.(s,[lambda],[??],F)](z), where the sum is restricted to the full schemes of genus g whose typing associates 0 to all edges.

It is therefore sufficient to compute the [R.sub.f]'s. Now, observe that when the [[delta].sub.i]'s are large enough (say [greater than or equal to] some number K), we can remove the absolute value in the exponent in Equation 1. Hence there exists a polynomial p in the [[alpha].sub.i]'s (that depends on the full scheme f and on K) such that:


where passing from the second to the third line is only a geometric summation. We now look for the radius of convergence and singular behaviour of the series [R.sub.f]. First, we are in a critical situation: the radius of convergence [t.sup(c).sub.D] of the [[alpha].sub.i]'s is exactly the value of the series z[T.sub.D](z) at its radius of convergence [z.sup.(c).sub.D]. Hence the combinatorial exponents of the series, which are both of the half-integer type, will combine and give birth to combinatorial exponents that are multiples of 1/4. Moreover, this critical point [z.sup.(c).sub.D] is also the first point where the principal branch a1 reaches the value 1, hence the first point where the denominator of the last equation can cancel. The next lemma can be proved thanks to a study of the derivatives of the kernel at the critical point (that can be computed combinatorially as the generating functions of certains Motzkin walks with distinguished steps). We let [delta]z = 1 - z / [z.sup.(c).sub.D].

Lemma 6 When z tends to [z.sup.(c).sub.D] we have:


There is a last phenomenon that could induce a singularity for [R.sub.f]: the fact that two (or more) of the [[alpha].sub.i]'s collapse (if the kernel has a multiple root). First, one can show that this does not happen for z < [z.sup.(c).sub.D]: this would imply a growth constant for the coefficients bigger that 1 / [z.sup.(c).sub.D], which is easily contradicted combinatorially. Second, if it happens at [z.sup.(c).sub.D], it induces a divergence of the series [C.sub.i], but due to the symmetry of the expression of [R.sub.f], this divergence compensates between conjugated roots. Precisely, one can show that Equation 2 is dominated by the term corresponding to [i.sub.e] = 1 for all e. This leads to the singular expansion of [R.sub.f] at its radius of convergence:


where the constant [c.sub.s,[lambda]] := [([[PI].sub.j] [summation.sub.e] [A.sub.e,j].sup.-1] depends only on s and [lambda], and where [T.sup.(c).sub.D] = [T.sub.D]([z.sup.(c).sub.D]). In particular, the contribution to [R.sub.D] is dominated by the full schemes that maximises the quantity [absolute value of s] + M. Euler characteristic formula enables to show:

Lemma 7 The maximum value of [absolute value of s] + M is 10g - 6. It is achieved when the scheme s has 4g - 2 vertices of degree 3, and 6g - 3 edges, and when the application [lambda] is injective. Such a pair (s, [lambda]) is called a dominant pair, and the finite set of dominant pairs of genus g is denoted [P.sub.g].

At this point, we have determined the growth constant and the combinatorial exponent of mobiles of degree set 2D. We now investigate the multiplicative factors induced by the decorations.

4.3 The multiplicative contributions of decorations.

Observe that Equation 3 has a remarquable multiplicative form: the contributions of the pair (s, [lambda]), the typing [tau], and the decoration F are clearly separated. In particular, we will be able to perform a summation on F.

Let us fix a triple (s, [tau], [lambda]) such that (s, [lambda]) is dominant. Observe that the vertices of s can be of two types: vertices that are adjacent to three edges of type 0, and vertices that are adjacent to two edges of type 1 and one of type 0. Vertices of the first type can be decorated either by a single vertex [??], either by an elementary star with 3 marked labelled vertices and no flags. The corresponding generating series is:


The analoguous quantity for vertices of the second type can be computed as well:



where the sum is taken over all the decorations F compatible with (s, [lambda], [tau]), and where no (resp. [n.sub.1]) denotes the number of vertices of the first (resp. second) type of (s, [tau]). Now, the number of vertices of the second type is clearly equal to the number of edges of type 1. Hence, the factor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] simplifies with the factor [T.sup.(c)#edges of type 1.sub.D] in Equation 3. Precisely, if we set [R.sub.s,[lambda],[tau]] = [summation.sub.F] [R.sub.(s,[tau],[lambda],F)], then the first term in the asymptotic expansion of [R.sub.s,[lambda],[tau]] does not depend of [tau]. We obtain:

Lemma 8 For each (s, [lambda]) [member of] [P.sub.g], and for each typing [tau] of s, one has when z tends to [z.sup.(c).sub.D]:


Now, from the expression of Equation 2, [R.sub.s,[lambda],[tau]](z) is an algebraic series, and is therefore amenable to singularity analysis, in the classical sense of [FO90]. Observe that, for combinatorial reasons, [R.sub.s,[lambda],[tau]](z) is in fact a power series in [z.sup.gcd(D)]. It can moreover be checked that the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are its only dominant singularities. Using Lemma 5, Proposition 1, and the classical transfer theorems of [FO90], it follows that the number [b.sup.*.sub.g,D](n) of rooted and pointed bipartite maps of genus g, degree set 2D, and n edges satifies, when n tends to infinity along multiples of gcd(D):


where [A.sub.g] = [summation over ((s,[lambda])[member of][P.sub.g] [c.sub.s,[lambda]]. Moreover, since the expression of Lemma 8 does not depend on [tau], and since from Proposition 2, each scheme has [2.sup.2g] valid typings, it follows from Lemma 5 again that the number [c.sup*.sub.g,D](n) of rooted and pointed maps of degree set 2D satisfies: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4.4 Our last step: an "un-pointing lemma".

The last thing to do to prove Theorems 1 and 2 is to relate maps which are both rooted and pointed to maps which are only rooted. First, each rooted map with v vertices corresponds to exactly v distinct rooted and pointed maps. Second, observe that the vertices of a map correspond (except the root) to the labelled vertices of its mobile. Now, in a mobile, a small proportion of those vertices (actually O([n.sup.-l/2])) is located on the superchains, whereas the rest is located on the "planar parts" which are attached to the superchains. These planar parts form a forest of rooted planar mobiles. According to the famous theorem of Drmota [Drm97] on the repartition of terminals in a context-free grammar, and due to the tree-like structure of mobiles, the number of labelled vertices in a forest of rooted planar mobiles has linear growth and is concentrated around its expectation when the number of edges tends to infinity. Precisely, we obtain that the ratio between the number of edges and the number of labelled vertices in a large forest of planar mobiles converges in probability to [[beta].sub.D], which leads to:

Lemma 9 The numbers [c.sub.g,D](n) and [c.sup.*.sub.g,D](n) of rooted maps and rooted and pointed maps, with genus g, degree set 2D, and n edges are asymptotically related by: [c.sup.*.sub.g,D](n) ~ n / [[beta].sub.D][c.sub.g,D](n). The same holds for bipartite maps: [b.sup.*.sub.g,D](n) ~ n / [[beta].sub.D][b.sub.g,D](n).

This concludes the proof of Theorems 1 and 2, with [t.sub.g] = [A.sub.g][3.sup.g][2.sup.7-11g] / (6g - 3)[GAMMA](5g - 3 / 2). The case D = {2} of rooted bipartite quadrangulations (which are in bijection with general rooted maps, from a famous construction of Tutte) shows that the constant [t.sub.g] is indeed the same as in [BC86], as claimed in the theorem.


[BC86] Edward A. Bender and E. Rodney Canfield. The asymptotic number of rooted maps on a surface. J. Combin. Theory Ser. A, 43(2):244-257, 1986.

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

[Ben91] Edward Bender. Some unsolved problems in map enumeration. Bull. Inst. Combin. Appl., 3:51-56, 1991.

[BG] Jeremie Bouttier and Emmanuel Guitter. Statistics of geodesics in large quadrangulations. arXiv:0712.2160v1 [math-ph].

[Cha] Guillaume Chapuy. The asymptotic number of constellations and related families of maps on orientable surfaces. see

[CMS07] Guillaume Chapuy, Michel Marcus, and Gilles Schaeffer. On the number of rooted maps on orientable surfaces. arXiv:0712.3649v1 [math.C0], 2007.

[CS04] Philippe Chassaing and Gilles Schaeffer. Random planar lattices and integrated superBrownian excursion. Probab. Theory Related Fields, 128(2):161-212, 2004.

[CV81] Robert Cori and Bernard Vauquelin. Planar maps are well labeled trees. Canad. J. Math., 33(5):1023-1042, 1981.

[Drm97] Michael Drmota. Systems of functional equations. Random Structures Algorithms, 10(1-2) :103-124, 1997. Average-case analysis of algorithms (Dagstuhl, 1995).

[FO90] Philippe Flajolet and Andrew Odlyzko. Singularity analysis of generating functions. SIAM J. Discrete Math., 3(2):216-240, 1990.

[Gao93] Zhicheng Gao. The number of degree restricted maps on general surfaces. Discrete Math., 123(1-3):47-63, 1993.

[LG07] Jean-Francois Le Gall. The topological structure of scaling limits of large planar maps. Inventiones Mathematica, 169:621-670, 2007.

[LGP] Jean-Francois Le Gall and Frederic Paulin. Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere. preprint (see

[Mie] Gregory Miermont. Tessellations of random maps of arbitrary genus. arXiv:0712.3688v1.

[MS] Michel Marcus and Gilles Schaeffer. Une bijection simple pour les cartes orientables. manuscript (see

[MT01] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.

[Sch99] Gilles Schaeffer. Conjugaison d'arbres et cartes combinatoires aleatoires,PhD thesis. 1999.

[Tut63] W. T. Tutte. A census of planar maps. Canad. J. Math., 15:249-271, 1963.

Guillaume Chapuy

LIX, Ecole Polytechnique, 91128 Palaiseau, France
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Chapuy, Guillaume
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUFR
Date:Jan 1, 2008
Previous Article:Hopcroft's automaton minimization algorithm and Sturmian words.
Next Article:Branching processes in random environment die slowly.

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