Character Theory and Rooted Maps in an Orientable Surface of Given Genus: Face-Colored Maps

Abstract

The character theoretic approach [5] to the enumeration of rooted maps in an orientable surface of arbitrary genus is extended to 2-face-colorable rooted maps.In particular, we show that there exists, for each genus, a correspondence between the set of 2-colored triangulations and a set of 2-colored rooted maps of all lower genera with a distinguished subset of vertices. INTRODUCTIONA previous paper [5] was concerned exclusively with the combinatorial interpretation of products of pairs of permutations, one of which is a fixed point free involution, in which information has been retained about their number of cycles.It was seen that an appropriate context is the embedding of rooted graphs in orientable surfaces.It is therefore natural to seek an analogous combinatorial interpretation of products of pairs of permutations with no such restriction and, more generally still, products of a finite number of them, with a similar retention of information about the number of cycles in each.In §2 we define a permutation system, an extension of the rotation systems used in [5] to a product of a finite number of prescribed conjugacy classes, and give their connection with embeddings of 2-face-colorable maps.Throughout this paper, all surfaces are oriented and without boundaries.Generating functions for certain subclasses of these maps are derived in §3.Factorizations for permutation systems are given in §4 and are used in §5 to obtain two bijections.These are between rooted 2-colored maps with all root-colored faces having degree rand 2r-face-regular maps and between 2-colored rooted triangulations and 2-colored rooted maps.Necessarily, extensive use is made of character theoretic results stated in [5].However, references to this paper have been confined, in the main, to the proofs of a few character theoretic results on which this extension rests.Notation and terminology are those used in [5], to which the reader is therefore referred for

Locations

• CiteSeer X (The Pennsylvania State University) - View - PDF
• Transactions of the American Mathematical Society - View - PDF