Rooted Maps, Functional Equations and Continued Fractions

Jean-François Béraud

Université de Marne la Vallée, Institut Gaspard Monge

Algorithms Seminar

February 1, 1999

[summary by Dominique Gouyou-Beauchamps]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
The enumeration of rooted maps has been first studied by W. T. Tutte in the early 1960's, with planar maps. New results have been obtained since for rooted maps on more general surfaces (torus with 1, 2, 3 holes, projective plane,...). I present the enumeration of rooted maps on the Klein bottle as a first step to the general case. Then I give an other approach of the enumeration of rooted maps, the rooted maps regardless to the genus of their associated surface. This leads to Riccati equations whose solutions are expressed as continued fractions. I obtain also a new equation generalizing the Dyck equation for rooted planar maps.



Details may be found in the recent works of D. Arquès and J. F. Béraud [2, 3]. Good introductions to maps and hypermaps can be found in [4, 1, 6, 5].

1   Definitions

There are two kinds of closed surfaces, orientable and nonorientable. The sphere, the torus, the double torus, the triple torus, and so on, are orientable. They are commonly denoted S0, S1, S2, S3,... It is proved that every closed connected orientable surface is homeomorphic to one of them.

The Möbius band is a surface that is neither closed nor orientable. What makes it nonorientable is that if a 2× 2 coordinate system specifying a forward direction and a right direction is translated in the forward direction once around the center of the band, then the orientation of the right direction is reversed. The Möbius band has a boundary which is homeomorphic to the circle. For k=0,1,..., the surface obtained by cutting k holes in a sphere and closing them off with k Möbius bands is denoted Nk. It is proved that every closed, connected nonorientable surface can be obtained in such a way. The surface N0 (resp. N1, N2) is called the sphere (resp. the projective plane, the Klein bottle). The projective plane, or its unclosed version the Möbius band [5], is also called a crosscap.

We define an embedding i:G® S of a graph G into a closed surface S to be a continuous one-to-one function from a topological representation of the graph into the surface (i.e. the edges do not intersect and the cells (vertices, edges and faces) are preserved). The Euler characteristic of a cellular embedding G® S of a connected graph G into a closed surface S is the value of the Euler formula #V-#E+#F (where V, E and F are the sets of vertices, edges and faces of G), and is denoted c (G® S). The invariance of Euler characteristic claims that for any cellular embedding G® Sg (resp. G® Nk), then c (G® Sg)=2-2g (resp. c (G® Nk)=2-k). The genus of a compact surface is given by the relation g=1/2(2-c ) (resp. g=2-c) in the orientable (resp. nonorientable) case.

The genus range (resp. crosscap range) of a graph G is defined to be the set of number g such that the graph G can be cellularly embedded in the surface Sg (resp. Ng). Of course, the minimum genus range (resp. crosscap range) is the genus (resp. crosscap number) g (G) (resp. g_(G)) of the graph.

A topological map C on an orientable surface S of R 3 is a partition of S in three finite set of cells:
  1. the set of the vertices of C, that is a finite set of points;
  2. the set of the edges of C, that is a finite set of simple open Jordan arcs, disjoint in pairs, whose extremities are vertices;
  3. the set of the faces of C. Each face is homomorphic to an open disc, and its border is an union of vertices and edges.
The genus of the map is the genus of the surface S. A cell is called incident to another cell if one of them is in the border of the other. An isthmus is an edge incident on both sides to the same face. We call half-edge an oriented edge of the map. A map is called a rooted map if a half-edge h~ is chosen. The half-edge h~ is called the root half-edge of the map, and its initial vertex the root vertex of the map. We call external face (or root face), the face generated by the root half-edge h~.

Two rooted maps with the same genus are isomorphic if there exists an homeomorphism of the associated surface, preserving its orientation, mapping the vertices, edges, faces and the root half-edge on the first map respectively on those of the second one. An isomorphic class of oriented (resp. nonoriented) rooted maps of genus g will simply be called an orientable (resp. non orientable) rooted map.

2   Series of Rooted Maps on the Klein Bottle

We denote by Pi(u,z)=å ai,n,munzm, i=1,2,3, the generating series where ai,n,m is the number of nonorientable rooted maps of genus i having its rooted face of degree n and having m edges. The generating series P0(u1,u2,z) is the generating series of 2-rooted planar maps (two half-edges are chosen).

Theorem 1   The generating series Pi(u,z), i=1,2,3, of nonorientable rooted maps with respect to the degree of the rooted face and the number of edges verify the following equations:
P0(u,z)
=1+u2zP0(u,z)2+uz
uP0(u,z)-P0(1,z)
u-1
,
    (1)
P1(u,z)
=u2z æ
ç
ç
è		 2P1(u,z)P0(u,z)+
u
[ uP0(u,z) ] ö
÷
÷
ø		 +uz
uP1(u,z)-P1(1,z)
u-1
,
    (2)
P2(u,z)
= u2z æ
ç
ç
è		 2P2(u,z)P0(u,z)+P1(u,z)2+P0(u,u,z)+
u
[ uP1(u,z) ] ö
÷
÷
ø
    (3)
 
    +uz
uP2(u,z)-P2(1,z)
u-1
.
The proof is based on the topological operation of deleting the root half-edge h~ as introduced by W. Tutte [7]. If we introduce the formal power series V(z)=1/(1-zV(z)P0(V(z),z)), in [1] we find a very simple proof that A(V(z),z)=0 and that z=(V(z)-1)(3-2V(z))/V(z)2 where A(u,z)=1-u+u2z-2(1-u)u2zP0(u,z). Now, we remark that:
P2(u,z)A(u,z)=uzP2(1,z)+(1-u)u2z æ
ç
ç
è
u
[ uP1(u,z) ] +P1(u,z)2+P0(u,u,z) ö
÷
÷
ø		 .
Then the generating series P0(u1,u2,z) verifies the functional equation:
P0(u1,u2,z) = 2u12zP0(u1,u2,z)P0(u1,z) +u1z
u1P0(u1,u2,z)-P0(1,u2,z)
u1-1
+u1u2z
u2
é
ê
ê
ë		 u2
u1P0(u1,z)-u2P0(u2,z)
u1-u2
ù
ú
ú
û		 .
If we define the series p by the relation z=p(1-3p), we obtain:
Theorem 2   The generating series P2(1,z) counting rooted maps on the Klein bottle with respect to the number of edges is the solution of the following parameterized system of equations:
ì
ï
í
ï
î
z =p(1-3p),
P2(1,z)
=
(1-3p) ( 1-4p+((1-6p)(1-2p))1/2 )
(1-6p)2(1-2p)
.
    (4)

3   Series of Orientable Rooted Maps

We present here the first topological equation for the generating series of orientable rooted maps regardless to genus, with respect to vertices and edges. We denote by M(y,z)=å an,mynzm the generating series where an,m is the number of orientable rooted maps of any genus having n vertices and m edges.

Theorem 3   The generating series M(y,z) of orientable rooted maps is the solution of the Riccati equation:
M(y,z))=y+zM(y,z)2+zM(y,z)+2z2
z
M(y,z).     (5)

The proof is based on the topological operation of deleting the root half-edge h~ as introduced by W. Tutte [7]

4   Orientable Rooted Maps and Trees

Equation (5) is a Riccati differential equation. We present in Theorem 4 an iterative solution of (5), which leads to a very nice continued fraction form of the generating series of orientable rooted maps.
Theorem 4   The generating series M(y,z) of orientable rooted maps with respect to the number of vertices and edges is:
M(y,z)=
y
1-
(y+1)z
1-
(y+2)z
1-
(y+3)z
1-···
In Theorem 4 a new relation on maps appears:
Corollary 1   The generating series M(y,z) of orientable rooted maps with respect to the number of vertices and edges is the solution of the following generalized Dyck equation:
M(y,z)=y+zM(y,z)M(y+1,z).

A tree (of any genus) is a map with only one face. We denote by T(z) the generating series of orientable rooted trees with respect to the number of edges. By duality there exists a one-to-one correspondence between rooted trees and rooted maps with only one vertex. Thus the series of trees is the coefficient of y in the series of maps and:
T(z)= é
ê
ê
ë
M(y,z)
y
ù
ú
ú
û
 



|y=0
.

Then we obtain the following results:
Corollary 2   The generating series T(z) of orientable rooted trees is the solution of the following differential equation:
T(z))=1+zT(z)+2z2
z
T(z).
The generating series T(z) of orientable rooted trees is:
T(z)=
1
1-
z
1-
2z
1-
3z
1-
4z
1-···
.
Both generating series of orientable rooted trees and orientable rooted maps are linked by the relation:
T(z)=
1
1-zM(1,z)
.

From the previous expressions, we deduce an explicit formula enumerating orientable rooted trees with a given number of edges:
Corollary 3   The number of orientable rooted trees with n edges is equal to the number of fixed-point-free involutions on [2n], namely the odd factorial: (2n-1)(2n-3)··· 1 = (2n)!2-n/n!.

References

[1]
Arquès (Didier). -- Une relation fonctionnelle nouvelle sur les cartes planaires pointées. Journal of Combinatorial Theory. Series B, vol. 39, n°1, 1985, pp. 27--42.

[2]
Arquès (Didier) and Béraud (Jean-François). -- Énumération des cartes pointées sur la bouteille de Klein. RAIRO Informatique Théorique et Applications. Theoretical Informatics and Applications, vol. 31, n°4, 1997, pp. 385--409.

[3]
Arquès (Didier) and Béraud (Jean-François). -- Rooted maps and hypermaps on surfaces. In Proceedings Formal Power Series and Algebraic Combinatorics (FPSAC'99), pp. 18--29. -- Universitat Politèchnica de Catalunya, Barcelona, 1999.

[4]
Cori (Robert). -- Un code pour les graphes planaires et ses applications. Astérisque, vol. 27, 1975.

[5]
Gross (Jonathan L.) and Tucker (Thomas W.). -- Topological graph theory. -- John Wiley & Sons Inc., New York, 1987. A Wiley-Interscience Publication.

[6]
Massey (William S.). -- Algebraic topology: an introduction. -- Springer-Verlag, New York, 1977. Reprint of the 1967 edition, Graduate Texts in Mathematics, Vol. 56.

[7]
Tutte (W. T.). -- On the enumeration of planar maps. Bulletin of the American Mathematical Society, vol. 74, 1968, pp. 64--74.
This document was translated from LATEX by HEVEA.