A pattern of asymptotic vertex valency distributions in planar maps
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.
scientific article; zbMATH DE number 1347245