# zbMATH — the first resource for mathematics

Enumeration of unrooted maps of a given genus. (English) Zbl 1102.05033
Authors’ abstract: Let $${\mathcal N}_g(f)$$ denote the number of rooted maps of genus $$g$$ having $$f$$ edges. An exact formula for $${\mathcal N}_g(f)$$ is known for $$g= 0$$ [W. T. Tutte, Can. J. Math. 15, 249–271 (1963; Zbl 0115.17305)], $$g=1$$ [D. Arquès, J. Comb. Theory, Ser B 43, 253–274 (1987; Zbl 0628.05040)], $$g=2,3$$ [E. A. Bender and E. R. Canfield, J. Comb. Theory, Ser. B 53, No. 2, 293–299 (1991; Zbl 0751.05052)]. In the present paper we derive an enumeration formula for the number $$\Theta_\gamma(e)$$ of unrooted maps on an orientable surface $$S_\gamma$$ of a given genus $$\gamma$$ and with a given number of edges $$e$$. It has a form of a linear combination $$\sum_{i,j} c_{i,j}{\mathcal N}_{g_j}(f_i)$$ of numbers of rooted maps $${\mathcal N}_{g_j}(f_i)$$ for some $$g_j\leq\gamma$$ and $$f_i\leq e$$. The coefficients $$c_{i,j}$$ are functions of $$\gamma$$ and $$e$$. We consider the quotient $$S_\gamma/ Z_\ell$$ of $$S_\gamma$$ by a cyclic group of automorphisms $$Z_\ell$$ as a two-dimensional orbifold $$O$$. The task of determining $$c_{i,j}$$ requires solving the following two subproblems:
(a) to compute the number $$Epi_{O}(\Gamma,Z_\ell)$$ of order-preserving epimorphisms from the fundamental group $$\Gamma$$ of the orbifold $$O=S_\gamma/Z_\ell$$ onto $$Z_\ell$$;
(b) to calculate the number of rooted maps on the orbifold $$O$$ which lifts along the branched covering $$S_\gamma\to S_\gamma/ Z_\ell$$ to maps on $$S_\gamma$$ with the given number $$e$$ of edges.
The number $$Epi_{O}(\Gamma,Z_\ell)$$ is expressed in terms of classical number-theoretical functions. The other problem is reduced to the standard enumeration problem of determining the numbers $${\mathcal N}_g(f)$$ for some $$g\leq\gamma$$ and $$f\leq e$$. It follows that $$\Theta_\gamma(e)$$ can be calculated whenever the numbers $${\mathcal N}_g(f)$$ are known for $$g\leq\gamma$$ and $$f\leq e$$. In the end of the paper the above approach is applied to derive the functions $$\Theta_\gamma(e)$$ explicitly for $$\gamma\leq 3$$. We note that the function $$\Theta_\gamma(e)$$ was known only for $$\gamma=0$$ [V. A. Liskovets, Colloq. Math. Soc. János Bolyai 25, 479–494 (1981; Zbl 0519.05040)]. Tables containing the numbers of isomorphism classes of maps with up to 30 edges for genus $$\gamma=1,2,3$$ are presented.

##### MSC:
 05C30 Enumeration in graph theory 05C10 Planar graphs; geometric and topological aspects of graph theory
##### Keywords:
surface; orbifold; Fuchsian group
OEIS
Full Text: