Document Open Access Logo

Counting Cubic Maps with Large Genus

Authors Zhicheng Gao, Mihyun Kang

PDF

File

Thumbnail PDF
PDF
LIPIcs.AofA.2020.13.pdf
  • Filesize: 0.88 MB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Generating functions
  • Mathematics of computing → Enumeration
Keywords
  • cubic maps
  • triangulations
  • cubic graphs on surfaces
  • generating functions
  • asymptotic enumeration
  • local limit theorem
  • saddle-point method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We derive an asymptotic expression for the number of cubic maps on orientable surfaces when the genus is proportional to the number of vertices. Let Σ_g denote the orientable surface of genus g and θ=g/n∈ (0,1/2). Given g,n∈ ℕ with g→ ∞ and n/2-g→ ∞ as n→ ∞, the number C_{n,g} of cubic maps on Σ_g with 2n vertices satisfies C_{n,g} ∼ (g!)² α(θ) β(θ)ⁿ γ(θ)^{2g}, as g→ ∞, where α(θ),β(θ),γ(θ) are differentiable functions in (0,1/2). This also leads to the asymptotic number of triangulations (as the dual of cubic maps) with large genus. When g/n lies in a closed subinterval of (0,1/2), the asymptotic formula can be obtained using a local limit theorem. The saddle-point method is applied when g/n→ 0 or g/n→ 1/2.

Cite As Get BibTex

Zhicheng Gao and Mihyun Kang. Counting Cubic Maps with Large Genus. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.AofA.2020.13

Author Details

Zhicheng Gao
  • School of Mathematics and Statistics, Carleton University, Ottawa, Canada
Mihyun Kang
  • Institute of Discrete Mathematics, Graz University of Technology, Austria

Funding

  • Gao, Zhicheng: Research supported by NSERC.
  • Kang, Mihyun: Research supported by the Austrian Science Fund (FWF): I3747, W1230.

Acknowledgements

Part of this research was carried out while the first author was visiting TU Graz. This visit was financially supported by TU Graz within the Doctoral Program "Discrete Mathematics".

References

  1. Omer Angel, Guillaume Chapuy, Nicolas Curien, and Gourab Ray. The local limit of unicellular maps in high genus. Electron. Commun. Probab., 18:paper no. 86, 8 pp., 2013. URL: https://doi.org/10.1214/ECP.v18-3037.
  2. Edward A. Bender. Central and local limit theorems applied to asymptotic enumeration. J. Combinatorial Theory Ser. A, 15:91-111, 1973. URL: https://doi.org/10.1016/0097-3165(73)90038-1.
  3. Edward A. Bender and E. Rodney Canfield. The asymptotic number of rooted maps on a surface. J. Combin. Theory Ser. A, 43(2):244-257, 1986. URL: https://doi.org/10.1016/0097-3165(86)90065-8.
  4. Edward A. Bender, E. Rodney Canfield, and L. Bruce Richmond. The asymptotic number of rooted maps on a surface. II. Enumeration by vertices and faces. J. Combin. Theory Ser. A, 63(2):318-329, 1993. URL: https://doi.org/10.1016/0097-3165(93)90063-E.
  5. Edward A. Bender, Zhicheng Gao, and L. Bruce Richmond. The map asymptotics constant t_g. Electron. J. Combin., 15(1):Research paper 51, 8, 2008. URL: http://www.combinatorics.org/Volume_15/Abstracts/v15i1r51.html.
  6. Thomas Budzinski and Baptiste Louf Louf. Local limits of uniform triangulations in high genus, 2019. URL: http://arxiv.org/abs/1902.00492v1.
  7. Guillaume Chapuy, Valentin Féray, and Éric Fusy. A simple model of trees for unicellular maps. J. Combin. Theory Ser. A, 120(8):2064-2092, 2013. URL: https://doi.org/10.1016/j.jcta.2013.08.003.
  8. C. Dowden, M. Kang, M. Mosshammer, and P. Sprüssel. The evolution of random graphs on surfaces of non-constant genus. Acta Math. Univ. Comenian. (N.S.), 88(3):631-636, 2019. Google Scholar
  9. Wenjie Fang, Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel. Cubic graphs and related triangulations on orientable surfaces. Electron. J. Combin., 25(1):Paper 1.30, 52, 2018. URL: https://doi.org/10.37236/5989.
  10. Zhicheng Gao. The number of rooted triangular maps on a surface. J. Combin. Theory Ser. B, 52(2):236-249, 1991. URL: https://doi.org/10.1016/0095-8956(91)90065-R.
  11. Zhicheng Gao. A pattern for the asymptotic number of rooted maps on surfaces. J. Combin. Theory Ser. A, 64(2):246-264, 1993. URL: https://doi.org/10.1016/0097-3165(93)90097-R.
  12. Zhicheng Gao and L. Bruce Richmond. Central and local limit theorems applied to asymptotic enumeration. IV. Multivariate generating functions. J. Comput. Appl. Math., 41(1-2):177-186, 1992. Asymptotic methods in analysis and combinatorics. URL: https://doi.org/10.1016/0377-0427(92)90247-U.
  13. Zhicheng Gao and Nicholas C. Wormald. Enumeration of rooted cubic planar maps. Ann. Comb., 6(3-4):313-325, 2002. URL: https://doi.org/10.1007/s000260200006.
  14. Ian P. Goulden and David M. Jackson. The KP hierarchy, branched covers, and triangulations. Adv. Math., 219(3):932-951, 2008. URL: https://doi.org/10.1016/j.aim.2008.06.013.
  15. Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel. Phase transitions in graphs on orientable surfaces, 2020. Accepted for publication in Random Structures and Algorithms. URL: https://doi.org/10.1002/rsa.20900.
  16. Colin McDiarmid. Personal communication, 2019. Google Scholar
  17. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001. Google Scholar
  18. Gourab Ray. Large unicellular maps in high genus. Ann. Inst. Henri Poincaré Probab. Stat., 51(4):1432-1456, 2015. URL: https://doi.org/10.1214/14-AIHP618.
  19. William T. Tutte. A census of planar maps. Canadian J. Math., 15:249-271, 1963. URL: https://doi.org/10.4153/CJM-1963-029-x.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact