TY - GEN
T1 - Counting Cubic Maps with Large Genus
AU - Gao, Z.
AU - Kang, M.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Asymptotic enumeration
KW - Cubic graphs on surfaces
KW - Cubic maps
KW - Generating functions
KW - Local limit theorem
KW - Saddle-point method
KW - Triangulations
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-85091029693&partnerID=MN8TOARS
U2 - 10.4230/LIPIcs.AofA.2020.13
DO - 10.4230/LIPIcs.AofA.2020.13
M3 - Conference paper
SN - 18688969
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms
A2 - Drmota, Michael
A2 - Heuberger, Clemens
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
CY - Saarbrücken/Wadern
T2 - 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms
Y2 - 15 June 2020 through 19 June 2020
ER -