×

zbMATH — the first resource for mathematics

Enumeration of hypermaps of a given genus. (English) Zbl 1404.05084
Summary: This paper addresses the enumeration of rooted and unrooted hypermaps of a given genus. For rooted hypermaps the enumeration method consists of considering the more general family of multirooted hypermaps, in which darts other than the root dart are distinguished. We give functional equations for the generating series counting multirooted hypermaps of a given genus by number of darts, vertices, edges, faces and the degrees of the vertices containing the distinguished darts. We solve these equations to get parametric expressions of the generating functions of rooted hypermaps of low genus. We also count unrooted hypermaps of given genus by number of darts, vertices, hyperedges and faces.

MSC:
05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] D. Arqu‘es, Relations fonctionnelles et d´enombrement des hypercartes planaires point´ees, in: G. Labelle and P. Leroux (eds.), Combinatoire ´enum´erative, Springer, Berlin, volume 1234 of Lecture Notes in Mathematics, pp. 5–26, 1986, doi:10.1007/bfb0072505.
[2] D. Arqu‘es, Hypercartes point´ees sur le tore: D´ecompositions et d´enombrements, J. Comb. Theory Ser. B43 (1987), 275–286, doi:10.1016/0095-8956(87)90003-7.
[3] D. Arqu‘es, Relations fonctionnelles et d´enombrement des cartes point´ees sur le tore, J. Comb. Theory Ser. B43 (1987), 253–274, doi:10.1016/0095-8956(87)90002-5.
[4] E. A. Bender and E. R. Canfield, The number of rooted maps on an orientable surface, J. Comb. Theory Ser. B53 (1991), 293–299, doi:10.1016/0095-8956(91)90079-y. A. Giorgetti and T. R. S. Walsh: Enumeration of hypermaps of a given genus249
[5] S. R. Carrell and G. Chapuy, Simple recurrence formulas to count maps on orientable surfaces, J. Comb. Theory Ser. A133 (2015), 58–75, doi:10.1016/j.jcta.2015.01.005. · Zbl 1315.05010
[6] G. Chapuy and W. Fang, Generating functions of bipartite maps on orientable surfaces, Electron. J. Comb.23 (2016), #P3.31,http://www.combinatorics.org/ojs/index. php/eljc/article/view/v23i3p31. · Zbl 1344.05012
[7] H. S. M. Coxeter, Regular Polytopes, Dover, New York, 3rd edition, 1973.
[8] P. Dunin-Barkowski, N. Orantin, A. Popolitov and S. Shadrin, Combinatorics of loop equations for branched covers of sphere, Int. Math. Res. Notices (2017), rnx047, doi:10.1093/imrn/ rnx047.
[9] B. Eynard, Formal matrix integrals and combinatorics of maps, in: J. Harnad (ed.), Random Matrices, Random Processes and Integrable Systems, Springer, New York, pp. 415–442, 2011, doi:10.1007/978-1-4419-9514-8 6. · Zbl 1257.81052
[10] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, New York, NY, USA, 1st edition, 2009,http://ac.cs.princeton.edu/home/.
[11] A. Giorgetti, Combinatoire bijective et ´enum´erative des cartes point´ees sur une surface, Ph.D. thesis, Universit´e de Marne-la-Vall´ee, Institut Gaspard Monge, 1998.
[12] A. Giorgetti and T. R. S. Walsh, Constructing large tables of numbers of maps by orientable genus, 2014,arXiv:1405.0615[math.CO].
[13] A. Jacques, Sur le genre d’une paire de substitutions, C. R. Acad. Sci. Paris Ser. A 267 (1968), 625–627. · Zbl 0187.20902
[14] G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc.37 (1978), 273–307, doi:10.1112/plms/s3-37.2.273. · Zbl 0391.05024
[15] M. Kazarian and P. Zograf, Virasoro constraints and topological recursion for Grothendieck’s dessin counting, Lett. Math. Phys. 105 (2015), 1057–1084, doi:10.1007/s11005-015-0771-0. · Zbl 1332.37051
[16] S. K. Lando and A. K. Zvonkin, Graphs on Surfaces and Their Applications, volume 141 of Encyclopaedia of Mathematical Sciences, Springer-Verlag, Berlin, 2004, doi:10.1007/ 978-3-540-38361-1, see especially chapter 2, “Dessins d’Enfants”, pp. 79–153.
[17] V. A. Liskovets, A multivariate arithmetic function of combinatorial and topological significance, Integers 10 (2010), 155–177, doi:10.1515/integ.2010.012. · Zbl 1230.11007
[18] A. Mednykh and R. Nedela, Enumeration of unrooted maps of a given genus, J. Comb. Theory Ser. B96 (2006), 706–729, doi:10.1016/j.jctb.2006.01.005. · Zbl 1102.05033
[19] A. Mednykh and R. Nedela, Counting hypermaps by Egorychev’s method, Anal. Math. Phys. 6 (2016), 301–314, doi:10.1007/s13324-015-0119-z. · Zbl 1353.05065
[20] A. Mednykh and R. Nedela, Recent progress in enumeration of hypermaps, J. Math. Sci. 226 (2017), 635–654, doi:10.1007/s10958-017-3555-5. · Zbl 06822075
[21] M. Planat, A. Giorgetti, F. Holweck and M. Saniga, Quantum contextual finite geometries from dessins d’enfants, Int. J. Geom. Methods Mod. Phys. 12 (2015), 1550067, doi:10.1142/ s021988781550067x. · Zbl 1327.11042
[22] W. T. Tutte, A census of slicings, Canad. J. Math. 14 (1962), 708–722, doi:10.4153/ cjm-1962-061-1. · Zbl 0111.35202
[23] T. R. S. Walsh, Hypermaps versus bipartite maps, J. Comb. Theory Ser. B 18 (1975), 155–163, doi:10.1016/0095-8956(75)90042-8. · Zbl 0302.05101
[24] T. R. S. Walsh, Space-efficient generation of nonisomorphic maps and hypermaps, J. Integer Seq.18 (2015), Article 15.4.3,https://cs.uwaterloo.ca/journals/JIS/ VOL18/Walsh/walsh3.html. 250Ars Math. Contemp. 15 (2018) 225–266
[25] T. R. S. Walsh and A. Giorgetti, Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices, Ars Math. Contemp. 7 (2014), 263–280,http:// amc-journal.eu/index.php/amc/article/view/190. · Zbl 1317.05090
[26] T. R. S. Walsh, A. Giorgetti and A. Mednykh, Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices, Discrete Math. 312 (2012), 2660–2671, doi: 10.1016/j.disc.2011.11.027. · Zbl 1246.05076
[27] T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus I, J. Comb. Theory Ser. B 13 (1972), 192–218, doi:10.1016/0095-8956(75)90050-7. · Zbl 0228.05108
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.