×

zbMATH — the first resource for mathematics

Counting maps on doughnuts. (English) Zbl 1301.05179
Summary: How many maps with \(V\) vertices and \(E\) edges can be drawn on a doughnut with \(G\) holes? I solved this problem for doughnuts with up to 10 holes, and my colleagues A. Giorgetti and A. Mednykh [Ars Math. Contemp. 4, No. 2, 351–361 (2011; Zbl 1237.05104)] counted maps by number of edges alone on doughnuts with up to 11 holes. This expository paper outlines, in terms meant to be understandable by a non-specialist, the methods we used and those used by other researchers to obtain the results upon which our own research depends.

MSC:
05C30 Enumeration in graph theory
Software:
Maple
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Lando, S. K.; Zvonkin, A. K., Graphs on surfaces and their applications, (2004), Springer-Verlag, XVI + 456 pages · Zbl 1040.05001
[2] Goulden, I. P.; Jackson, D. M., Combinatorial enumeration, (1983), J. Wiley New York, 569 pages · Zbl 0519.05001
[3] T.R.S. Walsh, Combinatorial enumeration of non-planar maps, Ph.D. Thesis, University of Toronto, 1971.
[4] Coxeter, H. S.M., Poincaré’s proof of euler’s formula, (Regular Polytopes, (1973), Dover New York), 165-172, (chapter 9)
[5] Jones, G. A.; Singerman, D., Theory of maps on orientable surfaces, Proc. Lond. Math. Soc. (3), 37, 2, 273-307, (1978) · Zbl 0391.05024
[6] Tutte, W. T., A census of planar maps, Canad. J. Math., 15, 249-271, (1963) · Zbl 0115.17305
[7] Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc., 74, 64-74, (1968) · Zbl 0157.31101
[8] Arquès, D., Une relation fonctionnelle nouvelle pour LES Cartes planaires pointées, J. Combin. Theory Ser. B, 39, 27-42, (1985) · Zbl 0571.05001
[9] 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
[10] Walsh, T. R., A polynomial algorithm for counting rooted toroidal maps, Ars Combin., 16, 49-56, (1983) · Zbl 0553.05041
[11] Bender, E.; Canfield, E., The asymptotic number of rooted maps on a surface, J. Combin. Theory Ser. A, 43, 244-257, (1986) · Zbl 0606.05031
[12] Arquès, D., Relations fonctionnelles et dénombrement des Cartes pointées sur le tore, J. Combin. Theory Ser. B, 43, 253-274, (1987) · Zbl 0628.05040
[13] Bender, E.; Canfield, E., The number of rooted maps on an orientable surface, J. Combin. Theory Ser. B, 53, 293-299, (1991) · Zbl 0751.05052
[14] A. Giorgetti, Combinatoire bijective et énumérative des cartes pointées sur une surface, Ph.D. Thesis, Université de Marne-la-Vallée, Institut Gaspard Monge, 1998.
[15] Arquès, D.; Giorgetti, A., Énumération des Cartes pointées de genre quelconque en fonction des nombres de sommets et de faces, J. Combin. Theory Ser. B, 77, 1-24, (1999) · Zbl 1029.05073
[16] A. Giorgetti, T.R.S. Walsh, Efficient enumeration of rooted maps of a given orientable genus by number of vertices and faces (submitted for publication). Available online at http://www.info2.uqam.ca/ walsh_t/pages/papers.html. · Zbl 1317.05090
[17] A. Giorgetti, A. Mednykh, Enumeration of genus four maps by number of edges, Ars Math. Contemp. 4 (2) (2011) (in press). Available online at http://amc.imfm.si. · Zbl 1237.05104
[18] J.-F. Béraud, A. Giorgetti, MAP: un package Maple pour compter les cartes pointées, Technical report 98-R-357, LORIA, 1998, 15 pages.
[19] Liskovets, V. A., Enumeration of nonisomorphic planar maps, Sel. Math. Sov., 4, 303-323, (1985) · Zbl 0578.05033
[20] Liskovets, V. A., A census of nonisomorphic planar maps, (Lovasz, L.; Sos, V. T., Algebraic Methods in Graph Theory, vol. II, (1981), North-Holland Amsterdam) · Zbl 0519.05040
[21] Neumann, P. M., A lemma that is not burnside’s, The Mathematical Scientist, 4, 2, 133-141, (1979) · Zbl 0409.20001
[22] Babai, L.; Imrich, W.; Lovász, L., Finite homeomorphism groups of the 2-sphere, (Colloq. Math. Soc. János Bolyai, Topics in Topology, vol. 8, (1974), North-Holland Amsterdam), 61-75 · Zbl 0305.57029
[23] Mednykh, A.; Nedela, R., Enumeration of unrooted maps of a given genus, J. Combin. Theory Ser. B, 96, 5, 706-729, (2006) · Zbl 1102.05033
[24] Liskovets, V. A., A multivariate arithmetic function of combinatorial and topological significance, Integers, 10, 155-177, (2010) · Zbl 1230.11007
[25] Harvey, W. J., Cyclic groups of automorphisms of a compact Riemann surface, Quart. J. Math. Oxford, 17, 86-97, (1966) · Zbl 0156.08901
[26] Bujalance, E.; Etayo, J. J.; Gamboa, J. M.; Gromadzki, G., Automorphism groups of compact bordered Klein surfaces, (1990), Springer-Verlag Berlin · Zbl 0709.14021
[27] J. Karabás, http://www.savbb.sk/ karabas/science.html#cycl.
[28] Walsh, T. R., Efficient enumeration of sensed planar maps, Discrete Math., 293, 263-289, (2005) · Zbl 1063.05070
[29] Wormald, N. C., On the number of planar maps, Canad. J. Math., XXXIII, 1, 1-11, (1981) · Zbl 0408.57006
[30] Wormald, N. C., Counting unrooted planar maps, Discrete Math., 36, 205-225, (1981) · Zbl 0467.05034
[31] Liskovets, V. A., A reductive technique for enumerating non-isomorphic planar maps, Discrete Math., 156, 197-217, (1996) · Zbl 0857.05044
[32] Walsh, T. R., Generating nonisomorphic maps without storing them, SIAM J. Algebr. Discrete Methods, 4, 161-178, (1983) · Zbl 0521.05034
[33] Cori, R.; Marcus, Michel, Counting non-isomorphic chord diagrams, Theoret. Comput. Sci., 204, 55-73, (1998) · Zbl 0913.68148
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.