A Central Limit Theorem for the Number of Degree-k Vertices in Random Maps

A Central Limit Theorem for the Number of Degree-k Vertices in Random Maps

0.00 Avg rating0 Votes
Article ID: iaor20133669
Volume: 66
Issue: 4
Start Page Number: 741
End Page Number: 761
Publication Date: Aug 2013
Journal: Algorithmica
Authors: ,
Keywords: probability, programming: probabilistic
Abstract:

We prove that the number of vertices of given degree in (general or 2‐connected) random planar maps satisfies a central limit theorem with mean and variance that are asymptotically linear in the number of edges. The proof relies on an analytic version of the quadratic method and singularity analysis of multivariate generating functions.

Reviews

Required fields are marked *. Your email address will not be published.