×

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
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apostol, T.M., Introduction to analytical number theory, (1976), Springer Berlin
[2] Arques, D., Relations fonctionelles et dénombrement des Cartes poinées sur le tore, J. combin. theory ser. B, 43, 253-274, (1987), (in French) · Zbl 0628.05040
[3] Arques, D.; Giorgetti, A., Énumération des Cartes pointées sur une surface orientable de genre quelconque en fonction des nombres de sommets et de faces, J. combin. theory ser. B, 77, 1-24, (1999) · Zbl 1029.05073
[4] Bender, E.A.; Canfield, E.A., The number of rooted maps on an orientable surface, J. combin. theory ser. B, 53, 293-299, (1991) · Zbl 0751.05052
[5] Bender, E.A.; Wormald, N.C., The number of loopless planar maps, Discrete math., 54, 235-237, (1985) · Zbl 0563.05032
[6] Bender, E.A.; Canfield, E.A.; Robinson, R.W., The enumeration of maps on the torus and on the projective plane, Canad. math. bull., 31, 257-271, (1988) · Zbl 0617.05036
[7] Bogopol’skii, O.V., Classifying the action of finite groups on oriented surface of genus 4, Siberian adv. math., 7, 4, 9-38, (1997)
[8] Bousquet, M.; Labelle, G.; Leroux, P., Enumeration of planar two-face maps, Discrete math., 222, 1-25, (2000) · Zbl 0993.05089
[9] Broughton, S.A., Classifying finite group actions on surface of low genus, J. pure appl. algebra, 69, 233-270, (1990) · Zbl 0722.57005
[10] Bujalance, E.; Etayo, J.J.; Gamboa, J.M.; Gromadzki, G., Automorphism groups of compact bordered Klein surfaces, (1990), Springer Berlin · Zbl 0709.14021
[11] Chalambides, Ch.A., Enumerative combinatorics, (2002), Chapman & Hall/CRC Boca Raton, FL
[12] Comtet, L., Advanced combinatorics, (1974), Reidel Dordrecht
[13] R. Cori, Bijective census of rooted planar maps: A survey, in: A. Barlotti, M. Delest, R. Pinzani (Eds.), Proceedings of the Fifth Conference on Formal Power Series and Algebraic Combinatorics, Florence, 1993, pp. 131-141
[14] Gross, J.L.; Tucker, T.W., Topological graph theory, (1987), Wiley New York · Zbl 0621.05013
[15] Harary, F.; Tutte, W.T., The number of plane trees with given partition, Mathematika, 11, 99-101, (1964) · Zbl 0193.53401
[16] Harary, F.; Prins, G.; Tutte, W.T., The number of plane trees, Indag. math., 26, 319-329, (1964) · Zbl 0126.19002
[17] Harvey, W.J., Cyclic groups of automorphisms of a compact Riemann surface, Quart. J. math. Oxford, 17, 86-97, (1966) · Zbl 0156.08901
[18] Jones, G.A., Enumeration of homomorphisms and surface-coverings, Quart. J. math. Oxford, 46, 2, 485-507, (1995) · Zbl 0859.57001
[19] Jones, G.A.; Singerman, D., Theory of maps on orientable surfaces, Proc. London math. soc., 37, 273-307, (1978) · Zbl 0391.05024
[20] Jordan, C., Traité des substitutions et des équationes algébriques, (1989), Éditions J. Gabay Paris, xvi+669 p · Zbl 0828.01011
[21] Kuribayashi, I.; Kuribayashi, A., Automorphism groups of compact Riemann surfaces of genera three and four, J. pure appl. algebra, 65, 277-292, (1990) · Zbl 0709.30036
[22] Labelle, G.; Leroux, P., Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Discrete math., 157, 227-240, (1996) · Zbl 0868.05030
[23] Liskovets, V.A., A census of nonisomorphic planar maps, (), 479-494
[24] Liskovets, V.A., Enumeration of nonisomorphic planar maps, Selecta math. sovietica, 4, 303-323, (1985) · Zbl 0578.05033
[25] Liskovets, V.A., A reductive technique for enumerating non-isomorphic planar maps, Discrete math., 156, 197-217, (1996) · Zbl 0857.05044
[26] Liskovets, V.A., Reductive enumeration under mutually orthogonal group actions, Acta appl. math., 52, 91-120, (1998), (Section 7) · Zbl 0908.05003
[27] Liskovets, V.A.; Walsh, T.R., The enumeration of non-isomorphic 2-connected planar maps, Canad. J. math., 35, 417-435, (1983) · Zbl 0519.05041
[28] Liu, Y.P., Some enumerating problems of maps with vertex partition, Kexue tongbao sci. bul., English ed., 31, 1009-1014, (1986) · Zbl 0604.05023
[29] Liu, Y.P., Enumerative theory of maps, (1999), Kluwer Academic London · Zbl 0990.05070
[30] Malnič, A.; Nedela, R.; Škoviera, M., Regular homomorphisms and regular maps, European J. combin., 23, 449-461, (2002) · Zbl 1007.05062
[31] Nicol, C.A.; Vandiver, H.S., A von sterneck arithmetical function and restricted partitions with respect to modulus, Proc. natl. acad. sci. USA, 40, 825-835, (1954) · Zbl 0056.04001
[32] Sloane, N.J.A.; Plouffe, S., The encyclopedia of integer sequences, (1995), Academic Press San Diego · Zbl 0845.11001
[33] Schulte, J., Über die jordansche verallgemeinerung der eulerschen funktion, Results math., 36, 354-364, (1999) · Zbl 0942.11006
[34] Tutte, W.T., A census of planar triangulations, Canad. J. math., 14, 21-38, (1962) · Zbl 0103.39603
[35] Tutte, W.T., A census of Hamiltonian polygons, Canad. J. math., 14, 402-417, (1962) · Zbl 0105.17601
[36] Tutte, W.T., A census of slicings, Canad. J. math., 14, 708-722, (1962) · Zbl 0111.35202
[37] Tutte, W.T., A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[38] Tutte, W.T., The number of planted plane trees with a given partition, Amer. math. monthly, 71, 64-74, (1964) · Zbl 0117.17403
[39] Walsh, T.R.S., Generating nonisomorphic maps without storing them, SIAM J. algebraic discrete methods, 4, 161-178, (1983) · Zbl 0521.05034
[40] Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus I, J. combin. theory ser. B, 13, 192-218, (1972) · Zbl 0228.05108
[41] Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus II, J. combin. theory ser. B, 13, 122-141, (1973) · Zbl 0228.05109
[42] Wong, C.K., A uniformization theorem for arbitrary Riemann surfaces with signature, Proc. amer. math. soc., 28, 2, 489-495, (1971) · Zbl 0218.30020
[43] Wormald, N.C., Counting unrooted planar maps, Discrete math., 36, 205-225, (1981) · Zbl 0467.05034
[44] Wormald, N.C., On the number of planar maps, Canad. J. math., 33, 1, 1-11, (1981) · Zbl 0408.57006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.