2026-07-23T22:37:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12043 2024-03-06T10:49:15Z ddc:004 open_access

Counting Cubic Maps with Large Genus Gao, Zhicheng Kang, Mihyun cubic maps triangulations cubic graphs on surfaces generating functions asymptotic enumeration local limit theorem saddle-point method 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhicheng Gao and Mihyun Kang 2020 Is Part Of LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2020.13 urn:nbn:de:0030-drops-120437 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.13 eng https://creativecommons.org/licenses/by/3.0/legalcode