Asymptotic Enumeration of Constellations and Related Families of Maps on Orientable Surfaces

Abstract

We perform the asymptotic enumeration of two classes of rooted maps on orientable surfaces: m -hypermaps and m -constellations. For m = 2 they correspond respectively to maps with even face degrees and bipartite maps. We obtain explicit asymptotic formulas for the number of such maps with any finite set of allowed face degrees. Our proofs combine a bijective approach, generating series techniques related to lattice walks, and elementary algebraic graph theory. A special case of our results implies former conjectures of Z. Gao.