## Abstract

We determine the limiting distribution of the maximum vertex degree Δ_{n} in a random triangulation of an n-gon, and show that it is the same as that of the maximum of n independent identically distributed random variables G_{2}, where G_{2} is the sum of two independent geometric(1/2) random variables. This answers affirmatively a question of Devroye, Flajolet, Hurtado, Noy and Steiger, who gave much weaker almost sure bounds on Δ_{n}. An interesting consequence of this is that the asymptotic probability that a random triangulation has a unique vertex with maximum degree is about 0.72. We also give an analogous result for random planar maps in general.

Original language | English |
---|---|

Pages (from-to) | 201-230 |

Number of pages | 30 |

Journal | Journal of Combinatorial Theory. Series A |

Volume | 89 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2000 |

Externally published | Yes |