A pattern of asymptotic vertex valency distributions in planar maps
type: Item
instance of: scholarly article
title: A pattern of asymptotic vertex valency distributions in planar maps
zbMATH Open document ID: 0930.05050
author: Valery A. Liskovets
published in: Journal of Combinatorial Theory. Series B
publication date: 2000-02-09T00:00:00Z
review text: Let a vertex be selected at random in a set of \(n\)-edged rooted planar maps and \(p_k\) denote the limit probability (as \(n\to\infty\)) of this vertex to be of valency \(k\). For diverse classes of maps, including Eulerian, arbitrary, polyhedral and loopless maps as well as 2- and 3-connected triangulations, it is shown that non-zero \(p_k\) behave asymptotically in a uniform manner: \(p_k\sim c(\pi k)^{-1/2} r^k\), as \(k\to\infty\), with some constants \(r\) (``the connective valency constant'') and \(c\) depending on the class. In terms of the limit valency distribution of the root vertex \(\{q_k\}\), this basic asymptotic pattern is reformulated in a similar form with the critical valency exponent \(1/2\) instead of \(-1/2\): \(q_k\sim (c/\mu)(k/\pi)^{1/2} r^k\) where \(\mu\) denotes the limit mean vertex valency. By contrast, \(p_k= 2^{-k}\) for the class of arbitrary plane trees, and \(p_k= (k- 1)2^{-k}\) for the triangular dissections of convex polygons. The descriptions systemize numerous particular results obtained previously by various authors (see, e.g., \textit{E. A. Bender} and \textit{E. R. Canfield} [J. Comb. Theory, Ser. B 46, No. 1, 58-65 (1989; Zbl 0666.05005)] and \textit{Z. Gao} and \textit{L. B. Richmond} [Eur. J. Comb. 15, No. 5, 483-490 (1994; Zbl 0807.05026)]). Some additional interconnections between valency distributions are established and several open questions are posed.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 1347245
zbMATH Keywords: vertex degree
zbMATH Keywords: symptotics
zbMATH Keywords: random map
zbMATH Keywords: distribution pattern
zbMATH Keywords: Eulerian map
zbMATH Keywords: Catalan numbers
zbMATH Keywords: rooted planar maps
zbMATH Keywords: limit probability
zbMATH Keywords: asymptotic pattern
zbMATH Keywords: critical valency exponent
zbMATH Keywords: plane trees
zbMATH Keywords: triangular dissections
zbMATH Keywords: convex polygons
zbMATH Keywords: valency distributions
MaRDI profile type: Publication
OpenAlex ID: W2030997953
cites work: Face sizes of 3-polytopes
cites work: The Number of Degree-Restricted Rooted Maps on the Sphere
cites work: Submap Density and Asymmetry Results for Two Parameter Map Families
cites work: Almost all rooted maps have large representativity
cites work: Q4881085
cites work: A survey of the asymptotic behaviour of maps
cites work: The number of loopless planar maps
cites work: Analytical and numerical study of a model of dynamically triangulated random surfaces
cites work: Enumerations of ordered trees
cites work: Properties of random triangulations and trees
cites work: The distribution of nodes of given degree in random trees
cites work: A pattern for the asymptotic number of rooted maps on surfaces
cites work: Root vertex valency distributions of rooted maps and rooted triangulations
cites work: Equivalence of the two-dimensional directed animal problem to a one- dimensional path problem
cites work: Some Asymptotical Estimates for Planar Eulerian Maps
cites work: Q4693177
cites work: Q4552181
DOI: 10.1006/JCTB.1998.1870
description: scientific article; zbMATH DE number 1347245