Sharp concentration of the number of submaps in random planar triangulations

Zhicheng Gao, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)467-486
Number of pages20
JournalCombinatorica
Volume23
Issue number3
DOIs
Publication statusPublished - 2003
Externally publishedYes

Cite this