×

zbMATH — the first resource for mathematics

The asymptotic number of rooted maps on a surface. (English) Zbl 0606.05031
Let S be a connected compact 2-manifold without boundary. For an orientable S the type \(g=1-\chi /2\) agrees with the genus (\(\chi\) denotes the Euler characteristic of S). Let \(T_ g(n)\) \((P_ g(n))\) be the numbr of n-edged rooted maps on a (non-)orientable surface of type g; \(TS_ g(n)\), \((PS_ g(n))\) be the number of those not having any vertex of degree less than 2. Using systems of equations that in principle give exact generating functions for the quantities above, the authors prove the following asymptotics for g fixed: \[ \begin{aligned} T_ g(n) &\sim t_ gn^{5(g-1)/2}12^ n;\\ TS_ g(n) &\sim (3/2)^{5(g-1)/4}t_ gn^{5(g-1)/2}(5+2\sqrt{6})^ n; \\ P_ g(n) &\sim p_ gn^{5(g- 1)/2}12^ n \text{ when \(g>0;\)} \\ PS_ g(n) &\sim (3/2)^{5(g- 1)/2}p_ gn^{5(g-1)/2}(5+2\sqrt{6})^ n \text{ when \(g>0.\)} \end{aligned} \]
Reviewer: L.A.SzĂ©kely

MSC:
05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bender, E.A, Asymptotic methods in enumeration, SIAM rev., 16, 485-515, (1974) · Zbl 0294.05002
[2] \scE. A. Bender, E. R. Canfield, and R. W. Robinson, The enumeration of maps on the torus and the projective plane, preprint. · Zbl 0617.05036
[3] Massey, W.S, Algebraic topology: an introduction, (1967), Harcourt, Brace & World New York · Zbl 0153.24901
[4] Tutte, W.T, What is a map?, (), 309-325
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.