Volume 23, Number 3, 467-486, DOI: 10.1007/s00493-003-0028-x

Sharp Concentration of the Number of Submaps in Random Planar Triangulations

Zhicheng Gao* and NicholasC. Wormald†

View Related Documents

Abstract

We show that the maximum vertex degree in a random 3-connected planar triangulation is concentrated in an interval of almost constant width. This is a slightly weaker type of result than our earlier determination of the limiting distribution of the maximum vertex degree in random planar maps and in random triangulations of a (convex) polygon. We also derive sharp concentration results on the number of vertices of given degree in random planar maps of all three types. Some sharp concentration results about general submaps in 3-connected triangulations are also given.

AMS Subject Classification (2000):   05C30 - 05A16 - 05C80

* Research supported by NSERC and Australian Research Council
dagger Research supported by the Australian Research Council

Fulltext Preview

Image of the first page of the fulltext document