2009/11/23 by Michael Drmota, Drmota, Michael, Omer Giménez +3 · 1 citation
Computer Science · Mathematics · #05A16 #05C30 #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.0911.4331
openalex publication_date 2009/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that for each k≥0, the probability that a root vertex in a random planar graph has degree k tends to a computable constant dk, so that the expected number of vertices of degree k is asymptotically dk n, and moreover that ∑k dk =1. The proof uses the tools developed by Gimenez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of the generating functions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function p(w)=∑k dk wk. From this we can compute the dk to any degree of accuracy, and derive the asymptotic estimate dk ∼ c⋅ k-1/2 qk for large values of k, where q ≈ 0.67 is a constant defined analytically.